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.