Approximate Lecture Outline, Fundamental Algorithms, Fall 97

Week 1. Introduction. Algorithm running time.

Week 2. Algorithm running time cont. Sorting (quicksort).

Week 3. Sorting cont. (heapsort, radix sort, lower bounds).

Week 4. Sorting cont. (lexicographic sort.) Trees; 2-3 trees.

Week 5. 2-3 trees cont. Random search trees.

Week 6. Hashing.

Week 7. Graphs (connected components, Dijkstra's algorithm).

Week 8. Graphs cont. Floyd/Warshall algorithm. Reductions among graph problems.

Week 9. Graphs cont. Reductions cont. Merge-Find.

Week 10. Graphs cont. Merge-Find cont. Minimum spanning trees.

Week 11. Graphs cont. Topological sort, strong components.

Week 12. Divide and conquer.

Week 13. Dynamic programming.

Week 14. Greedy algorithms; NP-complete problems, undecidability.

There will be more or less weekly homeworks.

Course Home Page (Richard Cole)
Last modified: Aug 26, 1997