CS 809: Mathematical Techniques for the Analysis of Algorithms

Instructor: Eric Bach

     Office : 4391 CS
     Phone : 262 7997
     E-mail : famous baroque composer at cs dot wisc dot edu
     Office Hours: MWF 11:00-12:00

General Course Information

• Course Description
• Reserve Books
• Topics List

Homework Assignments

• Homework 0 (due Sept 7)
• Homework 1 (due Sept 21)
• Homework 2 (due Oct 1)
• Homework 3 (due Oct 12)
• Homework 4 (due Oct 26)
• Homework 5 (submit Nov 9--16)
• Homework 6 (due Dec 10)

Course Log

• Course Log

Readings and Handouts

• Margulus on Chisox home run records
• David and Barton on Frechet's trick for indicator sums
• Mosteller on hypergeometric waiting times
• Roy on hypergeometric summation
• Niven on formal power series
• Wilf on the snake oil method
• Nodine on ladder network recurrences
• Moment formulas for duration of play
• Talk slides on nonlinear recurrences and height functions
• Protter and Morrey on Stieltjes integrals
• Analysis of a parking problem
• McCabe, Arnold, and Harris on the birthday problem
• Louchard on Brownian motion and algorithms
• Erdos and Renyi on random graph evolution
• Rosenkrantz on probabilistic counting
• Analysis of the monopolist game
• Karp and Pearl on tree search

Some Lecture Notes (to be edited as we proceed)

• Course Notes