Class log: CS 4349.003: Advanced Algorithm Design and Analysis (Spring 2017)
Lec Date Topics
1 T 1/10 Introduction, Running time (RT) analysis
2 R 1/12 Sums of arithmetic sequences, Order notation, Amortized cost
3 T 1/17 Sums of geometric and harmonic sequences, Recursion, Solving recurrences
4 R 1/19 Loop invariants, Divide and conquer: Merge sort, Binary search
5 T 1/24 D&C: Quick sort, kth smallest element of unsorted array
6 R 1/26 RT of Quick sort and kth smallest element algorithm, Multiplication of n-bit numbers
7 T 1/31 More D&C examples
8 R 2/2 Closest pair, Counting and radix sorts
9 T 2/7 Sorting lower bound, Dynamic programming: Fibonacci numbers
10 R 2/9 DP: Rod-cutting problem (RCP), Quiz
11 T 2/14 Variations of RCP, Matrix chain multiplication (MCM)
12 R 2/16 Dynamic program for MCM, Knapsack problems, LMIS
13 T 2/21 Longest common subsequence (LCS), Activity selection problem
14 R 2/23 Greedy algorithms: ASP, Huffman coding
15 T 2/28 Greedy algorithms, Problem solving session
16 R 3/2 Mid-term Exam (was Feb 23 in original plan)
17 T 3/7 Graphs, Encoding of graphs, Simple algorithms: BFS, DFS
18 R 3/9 Applications of DFS: Topological ordering of DAGs
19 T 3/21 DFS: Strongly connected components
20 R 3/23 Bridges and cut vertices, Minimum spanning trees
21 T 3/28 Implementation of Prim's algorithm
22 R 3/30 Implementation of Kruskal's algorithm, Basics of shortest paths
23 T 4/4 Bellman-Ford algorithm, DAG-shortest paths
24 R 4/6 Quiz
25 T 4/11 Dijkstra's algorithm, APSP: Floyd-Warshall algorithm
26 R 4/13 APSP examples, Fibonacci heaps
27 T 4/18 Maximum flow problem
28 R 4/20
29 T 4/25 NP-completeness
30 R 4/27
Final exam: Thu May 4, 2:15-4:15 PM.