CS 5633 Analysis of Algorithms
- 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
- 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.
- Week 4: Divide and conquer techniques (Chapter 8, and Section 31.2):
- For mergesort.
- For quicksort.
- Strassen's algorithm for matrix multiplication.
- 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.
- Week 7: Dynamic programming (CLR Chapter 16) and Midterm Exam:
- Week 8: Greedy algorithms (CLR Chapters 17 and 24);
- Huffman codes.
- Minimal spanning tree.
- Weeks 9 and 10: Graph algorithms (CLR Chapters 23-27):
- Graph representations.
- Graph traversals.
- Spanning trees or forests.
- Shortest paths.
- Maximum flow.
- Week 11: String matching (CLR Chapter 34):
- Rabin-Karp and KMP algorithms.
- Use of finite automata.
- 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.
- Weeks 14 and 15: Miscellaneous topics and review
Algorithms, by Cormen, Leiserson, and Rivest (CLR) (the "white" book).