CS 5633 Analysis of Algorithms

1. Weeks 1 and 2: Preliminaries (CLR Chapters 1-6):
   • What is an algorithm?
   • Algorithm growth, Big-Oh and similar notations.
   • Recurrence equations, and their solution. Applications of recurrences.
   • Review of series and sets
   • A little probability
2. Week 3: Sorting (CLR Chapters 7-10):
   • Algorithms (Heapsort, quicksort, mergesort, radixsort).
   • Proof that sorting (by comparisons) takes O(n log(n)) time.
   • Medians and order statistics.
3. Week 4: Divide and conquer techniques (Chapter 8, and Section 31.2):
   • For mergesort.
   • For quicksort.
   • Strassen's algorithm for matrix multiplication.
4. Weeks 5 and 6: Trees and hashing (CLR Chapters 11-14 and 19):
   • Stacks, queues, linked lists.
   • Hashing techniques and functions.
   • Binary search trees.
   • Balanced trees.
   • B-trees.
5. Week 7: Dynamic programming (CLR Chapter 16) and Midterm Exam:
   • Examples and principles.
6. Week 8: Greedy algorithms (CLR Chapters 17 and 24);
   • Huffman codes.
   • Minimal spanning tree.
7. Weeks 9 and 10: Graph algorithms (CLR Chapters 23-27):
   • Graph representations.
   • Graph traversals.
   • Spanning trees or forests.
   • Shortest paths.
   • Maximum flow.
8. Week 11: String matching (CLR Chapter 34):
   • Rabin-Karp and KMP algorithms.
   • Use of finite automata.
9. Weeks 12 and 13: NP-completeness (CLR Chapter 36):
   • The classes P, NP, NP-complete, NP-hard.
   • An initial NP-complete problem.
   • Reductions and proofs that other problems are NP-complete, e.g., Hamiltonian Circuit, Traveling Salesman, and Vertex Cover.
10. Weeks 14 and 15: Miscellaneous topics and review

References Algorithms, by Cormen, Leiserson, and Rivest (CLR) (the "white" book).