Date 
Topic 
Notes / Reading Material 
Mon, Aug 26 
Introduction 
 Chapter 3 (Growth of Functions), Introduction to Algorithms (3rd Edition) by Cormen et al.

Wed, Aug 28 
Introduction (continued) 
 
Mon, Sep 2 
No Class (Labor Day) 
 
Wed, Sep 4 
Introduction (continued)
Integer Multiplication & Karatsuba's Algorithm 
 Chapter 2 (DivideandConquer 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:169183, 1995.

Fri, Sep 6 
Prerequisites Review (Correctness of Algorithms)
Merge Sort
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.
 Chapter 2 (Getting Started), Section 2.3 (Designing Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.

Mon, Sep 9 
Integer Multiplication & Karatsuba's Algorithm
Matrix Multiplication & Strassen's Algorithm 
 Chapter 2 (DivideandConquer 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:169183, 1995.
 Chapter 4 (DivideandConquer), Section 4.2 (Strassen’s Algorithm for Matrix Multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al.

Wed, Sep 11 
Matrix Multiplication & Strassen's Algorithm (continued)
Polynomial Multiplication & the Fast Fourier Transform 
 [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:354356, 1969.
 Chapter 2 (DivideandConquer 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.

Fri, Sep 13 
Prerequisites Review
Deterministic Quicksort and Average Case Analysis 
 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 
Polynomial Multiplication & the Fast Fourier Transform (continued) 

Wed, Sep 18 
Class Canceled 
 
Fri, Sep 20 
Prerequisites Review
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.

Mon, Sep 23 
Polynomial Multiplication & the Fast Fourier Transform (continued) 

Wed, Sep 25 
Polynomial Multiplication & the Fast Fourier Transform (continued)
The Master Theorem 
 Chapter 4 (DivideandConquer), Section 4.5 (The Master Method for Solving Recurrences), Introduction to Algorithms (3rd Edition) by Cormen et al.

Fri, Sep 27 
Prerequisites Review
Heaps and Heapsort (continued) 
 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, Sep 30 
The Master Theorem (continued) 
 Chapter 4 (DivideandConquer), Section 4.6 (Proof of the Master Method), Introduction to Algorithms (3rd Edition) by Cormen et al.

Wed, Oct 2 
The Master Theorem (continued)
AkraBazzi Recurrences 
 Chapter 9 (Medians and Order Statistics), Section 9.3 (Selection in Worstcase Linear Time), Introduction to Algorithms (3rd Edition) by Cormen et al.

Fri, Oct 4 
Prerequisites Review
Dynamic Programming 
 Chapter 15 (Dynamic Programming), Section 15.1 (Rod Cutting), Introduction to Algorithms (3rd Edition) by Cormen et al.

Mon, Oct 7 
AkraBazzi Recurrences (continued) 

Wed, Oct 9 
AkraBazzi Recurrences (continued)
Linear Recurrences with Constant Coefficients (selfstudy)
Generating Functions 
 [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.

Fri, Oct 11 
Prerequisites Review
Dynamic Programming (continued) 
 Chapter 15 (Dynamic Programming), Section 15.2 (Matrixchain 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 SolarLezama,
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.

Mon, Oct 14 
No Class (Fall Break) 
 
Wed, Oct 16 
Exam 1 
 
Mon, Oct 21 
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 23 
Amortized Analysis
Binomial Heaps 
 Chapter 17 (Amortized Analysis), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 6 (Heapsort), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Jean Vuillemin, “A data structure for manipulating priority queues”, Communications of the ACM, 21(4):309315, 1978.

Fri, Oct 25 
Prerequisites Review
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, “Cacheoblivious Dynamic Programming”, Proceedings of the 17th annual ACMSIAM symposium on Discrete algorithm, pp. 591600, 2006.

Mon, Oct 28 
Binomial Heaps (continued) 
 [optional] Chapter 8 (Binomial Heaps), The Design and Analysis of Algorithms (1992) by Dexter Kozen.

Wed, Oct 30 
Binomial Heaps (continued) 
 [optional] Chapter 19 (Binomial Heaps), Introduction to Algorithms (2nd Edition) by Cormen et al.

Fri, Nov 1 
Prerequisites Review
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.

Mon, Nov 4 
Binomial Heaps (continued)
Dijkstra's SSSP & Fibonacci Heaps 
 Chapter 19 (Fibonacci Heaps), Introduction to Algorithms (3rd Edition) by Cormen et al.

Wed, Nov 6 
Dijkstra's SSSP & Fibonacci Heaps (continued) 

Fri, Nov 8 
Prerequisites Review
Greedy Algorithms (continued) 
 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.
 Chapter 24 (SingleSource 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 TR0754, Oct. 2007.

Mon, Nov 11 
Dijkstra's SSSP & Fibonacci Heaps (continued)
High Probability Bounds and Randomized Algorithms 
 Appendix C (Counting and Probability), Introduction to Algorithms (3rd Edition) by Cormen et al.

Wed, Nov 13 
High Probability Bounds and Randomized Algorithms (continued) 
 [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 MinCut Algorithm), Randomized Algorithms (1st Edition) by Rajeev Motwani and Prabhakar Raghavan.

Fri, Nov 15 
Prerequisites Review
Greedy Algorithms (continued) 
 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 FordFulkerson method), Introduction to Algorithms (3rd Edition) by Cormen et al.

Mon, Nov 18 
High Probability Bounds and Randomized Algorithms (continued) 

Wed, Nov 20 
High Probability Bounds and Randomized Algorithms (continued) 

Fri, Nov 22 
Prerequisites Review
Greedy Algorithms (continued)
More Graph Algorithms: Basic and Beyond 
 Chapter 26 (Maximum Flow), Section 26.3 (Maximum bipartite matching), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 22 (Elementary Graph Algorithms), Section 22.2 (Breadthfirst search), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 22 (Elementary Graph Algorithms), Section 22.3 (Depthfirst 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.

Mon, Nov 25 
Analyzing Parallel Algorithms 
 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.

Wed, Nov 27 
No Class (Thanksgiving Break) 
 
Mon, Dec 2 
Exam 2 
 
Wed, Dec 4 
Analyzing Parallel Algorithms (continued) 
 [optional] Gordon E. Moore, “Cramming more components onto integrated circuits”, Electronics, 38(8), pp. 114117, 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. 483485, 1967.

Fri, Dec 6 
Prerequisites Review
More Graph Algorithms: Basic and Beyond (continued) 
 Chapter 22 (Elementary Graph Algorithms), Section 22.5 (Strongly connected components), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 24 (SingleSource Shortest Paths), Section 24.1 (The BellmanFord algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 24 (SingleSource Shortest Paths), Section 24.2 (Singlesource shortest paths in directed acyclic graphs), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 25 (AllPairs Shortest Paths), Section 25.1 (Shortest paths and matrix multiplication), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 25 (AllPairs Shortest Paths), Section 25.2 (The FloydWarshall algorithm), Introduction to Algorithms (3rd Edition) by Cormen et al.

Mon, Dec 9 
Approximation Algorithms (Guest Lecturers: Zhi Li, Harsh Ranjan, Sunny Shah) 
 Chapter 35 (Approximation Algorithms), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 35 (Approximation Algorithms), Section 35.1 (The VertexCover Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 35 (Approximation Algorithms), Section 35.2 (The TravelingSalesman Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 35 (Approximation Algorithms), Section 35.2.1 (The TravelingSalesman Problem with the Triangle Inequality), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 35 (Approximation Algorithms), Section 35.2.2 (The General TravelingSalesman Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 35 (Approximation Algorithms), Section 35.3 (The SetCovering Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
 Chapter 35 (Approximation Algorithms), Section 35.5 (The SubsetSum Problem), Introduction to Algorithms (3rd Edition) by Cormen et al.
