Class log: CS 4349.003: Advanced algorithm design and analysis (Spring 2018)

Lec	Date	Topics
 1	T 1/9	Course introduction, RT analysis
 2	R 1/11	Asymptotic notation, sums of sequences, RT analysis, amortized cost
 3	T 1/16	Logs, recurrences: iteration/master/substitution methods, approximating sums by integrals, approximate upper and lower bounds by splitting sums
 4	R 1/18	Divide and conquer: power, binary search, merge sort, n-bit multiplication, proof by induction
 5	T 1/23	Loop invariants
 6	R 1/25	Quicksort, Selection problem and median
 7	T 1/30	O(n) algorithm for kth smallest, External k largest, Sorting lower bound

 8	R 2/1	Geometric algorithms: convex hull, Counting sort
 9	T 2/6	Radix and bucket sorts, Quiz 1
10	R 2/8	Dynamic programming: Rod-cutting problem (RCP), Activity selection problem (ASP)
11	T 2/13	DP: Activity selection problem (ASP)
12	R 2/15	DP: ASP, Longest monotonic increasing subsequence (LMIS), Matrix chain multiplication (MCM)
13	T 2/20	DP: MCM, Longest common subsequence (LCS)
14	R 2/22	Mid-term Exam
15	T 2/27	Memoization, Optimal BST, Knapsack.  Greedy algorithms: ASP

16	R 3/1	Greedy: LMIS, Huffman coding.  Graphs: Depth-first search (DFS)
17	T 3/6	Properties of DFS, Classification of edges, Topological ordering of vertices of DAGs
18	R 3/8	DFS: finding bridges, cut vertices; Strongly connected components
19	T 3/20	Minimum spanning trees
20	R 3/22	Correctness of MST algorithms, Quiz 2 (all topics covered in class up to and including DFS: Lec 1-18)
21	T 3/27	MST, Shortest paths
22	R 3/29	Bellman-Ford Algorithm, DAG-shortest-paths algorithm

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

Final exam: May 3, 2:00-4:00 PM.