Lecture Summaries

These lecture summaries can be viewed as the "past tense" course syllabus. They are intended for people who missed the class, or would like to briefly recall what was going on. Occasionally, I will include brief plan for future lectures, but do not count on it. Suggested reading from CLRS will be given after each summary.

. Administrivia, introduction. Sorting. Insertion Sort. Analysis of its running time.**Lecture 01: Wed, Jan 20**__Read__: CLRS, skim section 1, read section 2.1, 2.2.. Asymptotic notation (O, o, Omega, omega, Theta). Divide-and-conquer (recursion). Introduction to Recurrences. Better sorting: merge sort.**Lecture 02: Mon, Jan 25**__Read__: CLRS, 3 (skip 3.2 for now), start 2.3, 4 (before 4.1).. Analysis of merge sort (recursion tree + substitution methods). Comparison. Methods for solving recureences: recursion tree, guess-and-verify (induction).**Lecture 03: Wed, Jan 27**__Read__: CLRS, section 2.3, 4.3-4.4.. Other methods: (domain/range) substitution, "master theorem" (MT) for common case when T(n) = aT(n/b) + f(n). Intuition for proof of MT.**Lecture 04: Mon, Feb 1**__Read__: CLRS, section 4.3, 4.5, optional 4.6. Other examples of divide-and-conquer: binary search, stock profit (same as maximum subarray), Karatsuba multiplication, matrix multiplication, VLSI layouts.**Lecture 05: Wed, Feb 3**__Read__: CLRS, section 4.1, optional 4.2.. Quicksort. Randomized Quicksort.**Lecture 06: Mon, Feb 8**__Read__: CLRS, section 7.1-7.3, optional 7.4.. Heaps. Heapsort. Priority Queues.**Lecture 07: Wed, Feb 10**__Read__: CLRS, section 6.. Lower Bound for Comparison based sorting. Beating the lower bound: counting sort, radix sort.**Lecture 08: Wed, Feb 17**__Read__: CLRS, section 8.1-8.3.. Medians and order statistics: randomized and worst-case selection.**Lecture 09: Mon, Feb 22**__Read__: CLRS, section 9.. Binary Search Trees. Tree Walks (in-order, post-order, pre-order). Basic Ops (Insert, Delete, Search, Max, Min, Succ, Pred).**Lecture 10: Wed, Feb 24**__Read__: CLRS, section 12.1-3.. BST Sorting. Connection with Quicksort. Randomly Built Binary Search Trees. Balanced Search Trees with O(log n) worst case Ops: 2-3-Trees**Lecture 11: Mon, Mar 1**__Read__:*2-3-Trees handout, CLRS, section 12.4 (skip complicated parts).*. 2-3-trees: insertion, deletion. Connection with Red-Black Trees. Augmenting Data Structures. Maintaining number of nodes, application to dynamic order statistics (rank(T,k), myrank(T,node)).**Lecture 12: Wed, Mar 3**__Read__: 2-3-Trees handout, CLRS, skim 14.1-14.2 (replace RB-trees by 2-3-trees).. MIDTERM.**Lecture 13: Mon, Mar 8**__Read__: everything so far.. Dynamic Programming, Rod Cutting.**Lecture 14: Wed, Mar 10**__Read__: CLRS, sec 15.1.. Rod cutting (top down and bottom-up), longest common subsequence.**Lecture 15: Mon, Mar 22**__Read__: CLRS, sec 15.1,15.4.. More DP: Longest common subsequence, text allignment.**Lecture 16: Wed, Mar 24**__Read__: CLRS, sec 15.4, Notes on Text Alignment (.pdf). Greedy algorithms. Activity selection.**Lecture 17: Mon, Mar 29**__Read__: CLRS, sec 16.1-16.2.. Huffman Codes.**Lecture 18: Wed, Mar 31**__Read__: CLRS, sec 16.3.. More Huffman Codes. One-line prefix-free encodings.**Lecture 19: Mon, Apr 5**__Read__: CLRS, sec. 16.3. Notes on PFEs (.pdf). On-Line Prefix Free Codes (SOLE encoding).**Lecture 20: Wed, Apr 7**__Read__: Notes on PFEs (.pdf). Recap of SOLE. Graphs, their representations. Breadth-first search.**Lecture 21: Mon, Apr 12**__Read__: CLRS. 22.1-2.. BFS: analysis, properties, classification of edges. Depth-First Search**Lecture 22: Wed, Apr 14**__Read__: CLRS: 22.2-3.. DFS analysis, parenthesis and white-path theorem, clasisfication of edges. Topological Sort.**Lecture 23: Mon, Apr 19**__Read__: CLRS, 22.3-4.. Minimal spanning trees. Prim's and Kruskal's algorithms. Introduction to single-source shortest paths. Dijkstra's algorithm (start).**Lecture 24: Wed, Apr 21**__Read__: CLRS, sec. 23, 24 (before 24.1).. Dijkstra's algorithm (non-negative weights), Bellman-Ford algorithm (no negative cycles), BFS revisted (simple queue in Dijkstra), acyclic graphs.**Lecture 25: Mon, Apr 26**__Read__: CLRS, sec. 24.1-3.. All-pairs shortest paths. Matric multiplications approach, Floyd-Warshall. Transitive Closure. Johnson's algorithm.**Lecture 26: Wed, Apr 28**__Read__: CLRS, sec 25.1-2, 25.3.. Introduction to Number Theory and Cryptography. RSA encryption.**Lecture 27: Mon, May 3**__Read__: CLRS, sec 31.

Back to the course page