I   Background

• Introduction (3; 1, 2):
• Analysis techniques (4; 3, 4, Appendix A): approximating functions asymptotically, (big-O, Omega, Theta). some common recurrenc e formulas.

II   Sorting and Data-Structures

• Counting Sort and Radix Sort (8).
• QuickSort in O(n log n) expected time.
• Omega(n log n) bounds on Sorting (8).

III   Graph algorithms

• Basic Algorithms : (2; 22): depth- and breadth-first search, topological sorting, strongly-connected components.
• Minimum spanning trees (2; 23): Prim's and Kruskal's algorithms.
• Single-source shortest paths (2; 24): Dijkstra's and Bellman-Ford's algorithms.
• All-pairs shortest paths (1; 25): Johnson's algorithm.
• Maximum flow and maximum bi-partite matching (3; 26)
• Stable marriage (from a different textbook)

IV   String algorithms

• On-line string matching (2; 32): Knuth-Morris-Pratt's algorithm. Rabin's Algorithm
• Off-line string matching (2 ): suffix trees.

V   Geometric algorithms

• Fundamental algorithms (4; 33): Line-segment intersection, convex hull, line-sweeping

VI   Approximation Algorithms

• The need for approximation algorithms (4; 37): vertex cover , traveling salesman, set cover.
• Branch and bound (3; outside material): traveling salesman, maximum cut.

VII   Linear programming

• Modeling and solution (4; 29): applications, duality, simplex algorithm.