Class log: CS 6363.004: Design and analysis of computer algorithms (Spring 2018)

Lec	Date	Topics
 1	T 1/9	Course introduction, RT analysis
 2	R 1/11	Asymptotic notation, sums of sequences, RT analysis
 3	T 1/16	Logs, recurrences: iteration/master/substitution methods, approximating sums by integrals, proof by induction
 4	R 1/18	Divide and conquer: power, binary search, merge sort, multiplication of n-bit numbers, max subarray sum
 5	T 1/23	Loop invariants
 6	R 1/25	Quicksort, Selection problem and median
 7	T 1/30	Selection problem and median: O(n) algorithms, randomized and deterministic

 8	R 2/1	Polynomial multiplication and FFT, Master method (full)
 9	T 2/6	Lower bound for comparison sorts, Counting/Radix/Bucket sorts, Convex hull
10	R 2/8	Closest pair, Dynamic programming: Rod-cutting problem (RCP)
11	T 2/13	DP: RCP, Activity selection problem (ASP)
12	R 2/15	Exam 1
13	T 2/20	DP: ASP, Matrix-chain multiplication (MCM)
14	R 2/22	DP: Longest common subsequence (LCS)
15	T 2/27	Memoization, Knapsack.  Greedy algorithms: ASP

16	R 3/1	Greedy: ASP, LMIS.  Graphs: Depth-first search (DFS) and its properties
17	T 3/6	DFS: Topological ordering in DAGs, Bridges and cut vertices in undirected graphs
18	R 3/8	DFS: Strongly connected components
19	T 3/20	Minimum spanning trees
20	R 3/22	Correctness of MST algorithms, Analysis of Disjoin-set Union/Find
21	T 3/27	MST, Shortest paths, BFS
22	R 3/29	Exam 2

23	T 4/3	BFS, structure theorem of shortest paths, Bellman-Ford Algorithm
24	R 4/5	Bellman-Ford Algorithm, Properties of shortest paths, DAG-shortest-paths
25	T 4/10	Dijkstra's algorithm, APSP
26      R 4/12  Maximum flow problem: Ford-Fulkerson, Edmonds-Karp algorithms
27	T 4/17	Preflow-push algorithms for maximum flow
28	R 4/19
29	T 4/24
30	R 4/26

Final exam: Thu, May 3, 11:00 AM - 1:00 PM.