### 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.