Algorithms, Fall 1998

Lecturer

Time and place

Course description

• Graph algorithms:
  • Strongly connected componenets
  • Max flow
• String matching: Knuth-Morris-Pratt algorithm
• Computational geometry: convex hulls, Voronoi diagrams
• Data structures:
  • Hashing a' la Carter-Wegman
  • Amortized analysis: binomial heaps, Fibonacci heaps
• Numerical algorithms:
  • Finding best way to multiply matrices (dynamic programming)
  • Solving systems of linear eq's
  • FFT (and integeger multiplication via FFT)
• Randomization:
  • Miller's primality test
  • Computing maximal independent sets in parallel
  • Skip lists, treaps
• Competitive analysis of paging heuristics
• Lower bounds:
  • Sorting

Schedule

Literature

• Susanne Albers, Competitive Online Algorithms, BRICS LS-96-2, 1996.
• Timothy M. Chan, Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete and Computational Geometry, 16, pages 361-368, 1996 .
• Siu Wing Cheng and Ravi Janardan, New Results on Dynamic Planar Point Location, SIAM Journal of Computing 21(5):972-999, 1992.
• Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, MIT Press, 1990.
• Edsger D. Dijkstra: A Discipline of Programming, Prentice-Hall, 1976.
• Andrew V. Goldberg, Recent Developments in Maximum Flow Algorithms, 6th Skandinavian Workshop on Algorithm Theory (SWAT '98), LNCS 1432, pages 1-10, 1998.
• Dexter C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, 1992.
• Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.

Handouts

1. [Cormen et al., Chap. 23]
2. [Dijkstra, Chap. 25]
3. [Kozen, Lectures 5, 8-9]
4. [Kozen, Lectures 16-18]
5. [Goldberg]
6. [Cormen et al., Chap. 35]
7. [Chan]
8. [Cheng and Janardan]
9. [Cormen et al., Chap. 34]
10. [Motwani and Raghavan, Chap. 8-9.2]
11. [Kozen, Lectures 36-37]
12. [Kozen, Lectures 38-39]
13. [Albers]

Homework

Takehome exam

Evaluation