Class log: CS 6363.004: Design and analysis of computer algorithms (Spring 2019)

Lec	Date	Topics
 1	T 1/15	Introduction, RT analysis
 2      R 1/17  Order notation, sums of sequences
 3      T 1/22  Recurrences, Iteration/Substitution, Proof by induction
 4      R 1/24  Master method, Loop invariants, Approximating sum of sequences
 5	T 1/29	Divide and conquer: merge sort, multiplication of n-bit numbers, max subarray
 6	R 1/31	Convex hull: Jarvis, Graham, Kirkpatrick/Seidel, Closest pair of points

 7	T 2/5 	Quick sort, Selection problem
 8	R 2/7	O(n) algorithm for median, Linear-time sorts: Counting/Radix/Bucket
 9	T 2/12	nlogn lower bound for comparison sorts, Fast Fourier Transform (FFT) algorithm
10	R 2/14	Dynamic programming: Rod-cutting problem (RCP)
11	T 2/19	DP: RCP variants, Matrix-chain multiplication (MCM)
12	R 2/21	DP: Activity selection problem (ASP), LMIS
13	T 2/26	DP: Longest common subsequence (LCS), Knapsack, Memoization
14	R 2/28	Greedy algorithms: ASP, Huffman coding

15	T 3/5 	Graphs, Representation of graphs, Depth-first search (DFS) and its properties
16	R 3/7	Applications of DFS: topological order
17	T 3/12	DFS: bridges and cut vertices
18	R 3/14	Mid-term exam
19	T 3/26	DFS: strongly connected components
20	R 3/28	Minimum spanning trees (MST), Correctness of MST algorithms

21	T 4/2 	
22	R 4/4 	
23	T 4/9	
24	R 4/11	
25	T 4/16	
26	R 4/18	
27	T 4/23
28	R 4/25
29	T 4/30

30	R 5/2

Final exam: As announced by the registrar:  Thu, May 9: 11:00 AM-1:00 PM.