CSCI 404/504
Design and Analysis of Algorithms
Spring, 2009

We will address the following topics in approximately the order listed. Note the chapters in Dasgupta, Papadimitriou, and Vazirani corresponding to each.

• Mathematical essentials, including big-O. Chapter 0.
• Numerical algorithms. Chapter 1.
• Divids-and-conquer. Chapter 2.
• Graph algorithms: search, connected components, path lengths. Chapter 3 and 4.
• Greedy algorithms. Chapter 5.
• Dynamic programming and some canonical problems. Chapter 6.
• Linear programming. Chapter 7.
• NP-completeness and NP-complete problems. Chapters 8 and 9.
• (If time) Quantum algorithms. Chapter 10.