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.