Date |
Topic |
Notes / Reading Material |
Mon, Aug 26 |
Introduction |
- [optional] Algorithmic Puzzles by Anany Levitin and Maria Levitin, Oxford University Press, 2011.
|
Wed, Aug 28 |
Asymptotic Analysis of Algorithms |
- Chapter 3 (Growth of Functions), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Mon, Sep 2 |
No Class (Labor Day) |
- |
Wed, Sep 4 |
Integer Multiplication & Karatsuba's Algorithm
Matrix Multiplication & Strassen's Algorithm |
- Chapter 2 (Divide-and-Conquer Algorithms), Section 2.1 (Multiplication), Algorithms (1st Edition) by Dasgupta et al.
- [optional] Anatolii A. Karatsuba, “The Complexity of Computations”, Proceedings of the Steklov Institute of Mathematics, 211:169-183, 1995.
- Chapter 4 (Divide-and-Conquer), Section 4.2 (Strassen’s Algorithm for Matrix Multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al.
- [optional] Chapter 9 (Algebraic and Numeric Algorithms), Section 9.5.2 (Strassen’s Algorithm), Introduction to Algorithms - A Creative Approach (1st Edition) by Udi Manber.
- Volker Strassen, “Gaussian Elimination is not Optimal”, Numerische Mathematik, 13:354-356, 1969.
|
Mon, Sep 9 |
Correctness of Algorithms: Insertion Sort and Selection Sort |
- Chapter 2 (Getting Started), Section 2.1 (Insertion Sort), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 2 (Getting Started), Section 2.2 (Analyzing Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Wed, Sep 11 |
Correctness of Algorithms: Merge Sort
Deterministic Quicksort and Average Case Analysis |
- Chapter 2 (Getting Started), Section 2.3 (Designing Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 7 (Quicksort), Section 7.1 (Description of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 7 (Quicksort), Section 7.2 (Performance of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Mon, Sep 16 |
Deterministic Quicksort and Average Case Analysis (continued)
Polynomial Multiplication & the Fast Fourier Transform |
- Chapter 2 (Divide-and-Conquer Algorithms), Section 2.6 (The Fast Fourier Transform), Algorithms (1st Edition) by Dasgupta et al.
- Chapter 30 (Polynomials and the FFT), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Wed, Sep 18 |
Polynomial Multiplication & the Fast Fourier Transform (continued) |
|
Mon, Sep 23 |
The Master Theorem |
- Chapter 4 (Divide-and-Conquer), Section 4.5 (The Master Method for Solving Recurrences) and Section 4.6 (Proof of the Master Method), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Wed, Sep 25 |
Akra-Bazzi Recurrences
Linear Recurrences with Constant Coefficients (self-study)
Generating Functions |
- Chapter 9 (Medians and Order Statistics), Section 9.3 (Selection in Worst-case Linear Time), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Mohamad Akra and Louay Bazzi, “On the Solution of Linear Recurrence Equations”, Computational Optimization and Applications, 10(2):195–210, 1998.
- Tom Leighton, “Notes on Better Master Theorems for Divide-and-Conquer Recurrences”, 1996.
- [optional] Chapter 7 (Advanced Counting Techniques), Section 7.2 (Solving Linear Recurrence Relations), Discrete Mathematics and its Applications (6th Edition) by Kenneth Rosen.
- [optional] Chapter 7 (Generating Functions), Concrete Mathematics (2nd Edition) by Ronald Graham, Donald Knuth, and Oren Patashnik.
|
Mon, Sep 30 |
Generating Functions (continued) |
- [optional] Chapter 10 (Ordinary Generating Functions), Section 10.3 (Manipulating Generating Functions), Example 10.12 (The Average Time for Quicksort), Foundations of Combinatorics with Applications by Edward A. Bender and S. Gill Williamson.
|
Wed, Oct 2 |
Dynamic Programming |
- Chapter 15 (Dynamic Programming), Section 15.1 (Rod Cutting), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Mon, Oct 7 |
Dynamic Programming (continued) |
- Chapter 15 (Dynamic Programming), Section 15.2 (Matrix-chain Multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Rezaul Chowdhury, Pramod Ganapathi, Steven Tschudi, Jesmin Jahan Tithi, Charles Bachmeier, Bradley C. Kuszmaul, Charles E. Leiserson, Armando Solar-Lezama,
and Yuan Tang, “AutoGen: Automatic Discovery of Efficient Recursive Divide-&-Conquer
Algorithms for Solving Dynamic Programming Problems”, ACM Transactions on Parallel Computing, 4(1):4, 2017.
|
Wed, Oct 9 |
Dynamic Programming (continued) |
- Chapter 15 (Dynamic Programming), Section 15.3 (Elements of Dynamic Programming), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 15 (Dynamic Programming), Section 15.4 (Longest Common Subsequence), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 15 (Dynamic Programming), Section 15.5 (Optimal Binary Search Trees), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Rezaul Chowdhury and Vijaya Ramachandran, “Cache-oblivious Dynamic Programming”, Proceedings of the 17th annual ACM-SIAM symposium on Discrete algorithm, pp. 591-600, 2006.
|
Mon, Oct 14 |
No Class (Fall Break) |
- |
Wed, Oct 16 |
Heaps and Heapsort |
- Chapter 6 (Heapsort), Section 6.1 (Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 6 (Heapsort), Section 6.2 (Maintaining the Heap Property), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 6 (Heapsort), Section 6.3 (Bulding a Heap), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 6 (Heapsort), Section 6.4 (The Heapsort Algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 6 (Heapsort), Section 6.5 (Priority Queues), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Mon, Oct 21 |
Midterm |
- |
Wed, Oct 23 |
Greedy Algorithms |
- Chapter 16 (Greedy Algorithms), Section 16.1 (An Activity Selection Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 16 (Greedy Algorithms), Section 16.2 (Elements of the Greedy Strategy), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 23 (Minimum Spanning Trees), Section 23.1 (Growing a Minimum Spanning Tree), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 23 (Minimum Spanning Trees), Section 23.2 (The Algorithms of Kruskal and Prim), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Mon, Oct 28 |
Greedy Algorithms (continued) |
- Chapter 24 (Single-Source Shortest Paths), Section 24.3 (Dijkstra's Algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Mo Chen, Rezaul Chowdhury, Vijaya Ramachandran, David Lan Roche, and Lingling Tong, “Priority Queues and Dijkstra's Algorithm”, UT Austin, Department of Computer Sciences, Technical Report TR-07-54, Oct. 2007.
|
Wed, Oct 30 |
Amortized Analysis
Binomial Heaps |
|
Mon, Nov 4 |
Binomial Heaps (continued) |
- [optional] Chapter 8 (Binomial Heaps), The Design and Analysis of Algorithms (1992) by Dexter Kozen.
|
Wed, Nov 6 |
Binomial Heaps (continued)
Dijkstra's SSSP & Fibonacci Heaps |
- [optional] Chapter 19 (Binomial Heaps), Introduction to Algorithms (2nd Edition) by Cormen et al.
- Chapter 19 (Fibonacci Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Mon, Nov 11 |
Dijkstra's SSSP & Fibonacci Heaps (continued) |
|
Wed, Nov 13 |
More Graph Algorithms: Basic and Beyond |
- Chapter 22 (Elementary Graph Algorithms), Section 22.2 (Breadth-first search), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 22 (Elementary Graph Algorithms), Section 22.3 (Depth-first search), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 22 (Elementary Graph Algorithms), Section 22.4 (Topological sort), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 22 (Elementary Graph Algorithms), Section 22.5 (Strongly connected components), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 24 (Single-Source Shortest Paths), Section 24.1 (The Bellman-Ford algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 24 (Single-Source Shortest Paths), Section 24.2 (Single-source shortest paths in directed acyclic graphs), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Mon, Nov 18 |
Network Flow |
- Chapter 26 (Maximum Flow), Section 26.1 (Flow networks), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 26 (Maximum Flow), Section 26.2 (The Ford-Fulkerson method), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Wed, Nov 20 |
Network Flow (continued)
All-Pairs Shortest Paths |
- Chapter 26 (Maximum Flow), Section 26.3 (Maximum bipartite matching), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 25 (All-Pairs Shortest Paths), Section 25.1 (Shortest paths and matrix multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 25 (All-Pairs Shortest Paths), Section 25.2 (The Floyd-Warshall algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
Mon, Nov 25 |
Backtracking |
- Chapter 2 (Backtracking), Algorithms (1st Edition) by Jeff Erickson
|
Wed, Nov 27 |
No Class (Thanksgiving Break) |
- |
Mon, Dec 2 |
Randomized Algorithms and High Probability Bounds |
- Appendix C (Counting and Probability), Introduction to Algorithms (3rd Edition) by Cormen et al.
- [optional] Chapter 6 (Algorithms Involving Sequences and Sets), Section 6.9.2 (A Coloring Problem), Introduction to Algorithms - A Creative Approach (1st Edition) by Udi Manber.
- [optional] Chapter 1 (Introduction), Section 1.1 (A Min-Cut Algorithm), Randomized Algorithms (1st Edition) by Rajeev Motwani and Prabhakar Raghavan.
- [optional] Torben Hagerup and Christine Rüb, “A Guided Tour of Chernoff Bounds”, Information Processing Letters, 33(6), pp. 305-308, 1990.
- [optional] Chapter 7 (Quicksort), Section 7.4 (Analysis of Quicksort), Introduction to Algorithms (3rd Edition) by Cormen et al.
- William Pugh, “Skip lists: a probabilistic alternative to balanced trees”, Communications of the ACM, 33(6):668-676, 1990.
|
Wed, Dec 4 |
NP-Completeness |
- Chapter 8 (NP-Complete Problems), Algorithms (1st Edition) by Dasgupta et al.
|
Mon, Dec 9 |
Analyzing Parallel Algorithms (Guest Lecturer: Zafar Ahmad) |
- [optional] Chapter 5 (Analytical Modeling of Parallel Programs), Introduction to Parallel Computing (2nd Edition) by Grama et al.
- Chapter 27 (Multithreaded Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
- [optional] Gordon E. Moore, “Cramming more components onto integrated circuits”, Electronics, 38(8), pp. 114-117, April 19, 1965.
- Gene Amdahl, “Validity of the Single Processor Approach to
Achieving Large Scale Computing Capabilities”, Reprinted from the proceedings of the Spring Joint Computer Conference, AIFPS vol 30, pp. 483-485, 1967.
|
[Slides on BB] |
Approximation Algorithms |
- Chapter 35 (Approximation Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 35 (Approximation Algorithms), Section 35.1 (The Vertex-Cover Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 35 (Approximation Algorithms), Section 35.2 (The Traveling-Salesman Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 35 (Approximation Algorithms), Section 35.2.1 (The Traveling-Salesman Problem with the Triangle Inequality), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 35 (Approximation Algorithms), Section 35.2.2 (The General Traveling-Salesman Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 35 (Approximation Algorithms), Section 35.3 (The Set-Covering Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Chapter 35 (Approximation Algorithms), Section 35.5 (The Subset-Sum Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
|
[Slides on BB] |
The Inverse Ackermann Function, Union-Find, and Partial Sums |
- Chapter 21 (Data Structures for Disjoint Sets), Introduction to Algorithms (3rd Edition) by Cormen et al.
- Raimund Seidel and Micha Sharir, “Top-Down Analysis of Path Compression”, SIAM Journal on Computing, 34(3):515-525, 2005.
- [optional] Andrew C. Yao, “Space-Time Tradeoff for Answering Range Queries”,
Proceedings of the 14th Annual ACM Symposium on Theory of Computing (STOC), pp. 128-136, 1982.
- [optional] Bernard Chazelle and Burton Rosenberg, “Computing Partial Sums in Multidimensional Arrays”, Proceedings of the 5th Annual Symposium on Computational Geometry (SCG), pp. 131-139, 1989.
|
[Slides on BB] |
Analyzing I/O and Cache Performance |
- Alok Aggarwal and Jeffrey S. Vitter, “The input/output complexity of sorting and related problems”, Communications of the ACM, 31(9), pp. 1116-1127, 1988.
- Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran, “Cache-Oblivious Algorithms”, Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 285-298, 1999.
- Jeffrey S. Vitter, “Algorithms and Data Structures for External Memory”, Series on Foundations and Trends in Theoretical Computer Science, Now Publishers, Hanover, MA, 2008.
|