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.