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.