CS 445a/544a: Analysis of Algorithms II

Contents (tentative)

• Greedy algorithms
• Maximum flows
• Linear programming
• Approximation algorithms
• Randomized algorithms
• Advanced algorithm analysis techniques
• Online algorithms

Course material

• Quick introduction
  • slides.
• Flows and cuts
  • slides (.pdf) and slides x4 (.ps).
  • references and problems.
• Greedy algorithms
  • slides (.pdf) and slides x4 (.ps).
  • references and problems.
• Linear programming
  • slides (.pdf) and slides x4 (.ps).
  • references and problems.
• P and NP
  • slides (.pdf) and slides x4 (.ps).
• Approximation algorithms
  • slides (.pdf) and slides x4 (.ps).

News

• Nov. 2: Project page up.
• Oct. 30: First version of approximation algorithms slides, bug fix in P-NP slides (definition of topological order).
• Oct. 26: Update of P-NP slides.
• Oct. 19: First version of P-NP slides posted.
• Oct. 13: Assignment 3 posted.
• Oct. 11: Update of linear programming slides.
• Oct. 4: First version of linear programming slides.
• Sept. 27: Update on greedy algorithms slides; references, problems and assignment 2 posted.
• Sept. 19: First version of greedy algorithms slides; postscript version of slides for printing (4x1).
• Sept. 14: Fixed the typo in the dynamic shipping problem and posted the assignement.
• Sept. 12: All of those who have not done so should send me an email to confirm they plan to take the course.
• Sept. 12: Updated slides for flow algorithms, including Edmonds-Karp's algorithm.

References

• Introduction to algorithms, by Cormen, Leiserson, Rivest and Stein. The MIT Press, second edition, 2001.
• Algorithm design, by Kleinberg and Tardos. Addison Wesley, 2005.
• Randomized algorithms, by Motwani and Raghavan. Cambridge University Press, 1997.
• An introduction to the analysis of algorithms, by Sedgewick and Flajolet. Addison Wesley, 1996.
• A first course in combinatorial optimization, by Lee. Cambridge University Press, 2004.
• Online computation and competitive analysis, by Borodin and El-Yaniv. Cambridge University Press, 1998.
• Fundamental problems of algorithmic algebra, by Chee Keng Yap. Oxford University Press, 2000.

Schedule

• Assignment 1, due September 26
• Assignment 2, due October 10
• Assignment 3, due October 24
• The project is due on December 4
• Midterm Exam on November 9

Assignments

• Assignment 1, due September 26: solve problems 1 to 6 on the problem sheet.
• Assignment 2, due October 10: solve problems 1 to 6 on the second problem sheet.
• Assignment 3, due October 24: solve problems 1, 2, 4 on the third problem sheet.

Projects