Class log: CS 6363.004: Design and analysis of computer algorithms (Spring 2019)
Lec Date Topics
1 T 1/15 Introduction, RT analysis
2 R 1/17 Order notation, sums of sequences
3 T 1/22 Recurrences, Iteration/Substitution, Proof by induction
4 R 1/24 Master method, Loop invariants, Approximating sum of sequences
5 T 1/29 Divide and conquer: merge sort, multiplication of n-bit numbers, max subarray
6 R 1/31 Convex hull: Jarvis, Graham, Kirkpatrick/Seidel, Closest pair of points
7 T 2/5 Quick sort, Selection problem
8 R 2/7 O(n) algorithm for median, Linear-time sorts: Counting/Radix/Bucket
9 T 2/12 nlogn lower bound for comparison sorts, Fast Fourier Transform (FFT) algorithm
10 R 2/14 Dynamic programming: Rod-cutting problem (RCP)
11 T 2/19 DP: RCP variants, Matrix-chain multiplication (MCM)
12 R 2/21 DP: Activity selection problem (ASP), LMIS
13 T 2/26 DP: Longest common subsequence (LCS), Knapsack, Memoization
14 R 2/28 Greedy algorithms: ASP, Huffman coding
15 T 3/5 Graphs, Representation of graphs, Depth-first search (DFS) and its properties
16 R 3/7 Applications of DFS: topological order
17 T 3/12 DFS: bridges and cut vertices
18 R 3/14 Mid-term exam
19 T 3/26 DFS: strongly connected components
20 R 3/28 Minimum spanning trees (MST), Correctness of MST algorithms
21 T 4/2 Disjoint set Union/Find algorithm, Kruskal's MST algorithm
22 R 4/4 Breadth-first search (BFS), Shortest paths, Structure of shortest paths
23 T 4/9 Properties of shortest paths, Bellman-Ford algorithm
24 R 4/11 DAG-shortest-paths, Dijkstra's algorithm, All-pairs shortest paths
25 T 4/16 Floyd-Warshall's algorithm for APSP, Maximum flow problem
26 R 4/18 Edmonds-Karp algorithm, Max-flow min-cut theorem, Preflow-push algorithm for flow
27 T 4/23 Min-cost flow, Matching in bipartite graphs, Graph connectivity, Max-flow min-cut theorem
28 R 4/25 NP-Completeness, Decision problems, P, NP
29 T 4/30 Polynomial-time reductions, NP-completeness of Clique, Independent set, Vertex cover, Subset sum, Graph coloring
30 R 5/2 Conclusions, Exam review
Final exam: As announced by the registrar: Thu, May 9: 11:00 AM-1:00 PM.