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, Sep 8**__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, Sep 13**__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, Sep 15**__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, Sep 20**__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, Sep 22**__Read__: CLRS, section 4.1, optional 4.2.. Quicksort. Randomized Quicksort.**Lecture 06: Mon, Sep 27**__Read__: CLRS, section 7.1-7.3, optional 7.4.. Heaps. Heapsort. Priority Queues.**Lecture 07: Wed, Sep 29**__Read__: CLRS, section 6.. Lower Bound for Comparison based sorting. Beating the lower bound: counting sort, radix sort.**Lecture 08: Mon, Oct 4**__Read__: CLRS, section 8.1-8.3.. Medians and order statistics: randomized and worst-case selection.**Lecture 09: Wed, Oct 6**__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, Oct 13**__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, Oct 18**__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, Oct 20**__Read__: 2-3-Trees handout, CLRS, skim 14.1-14.2 (replace RB-trees by 2-3-trees).. MIDTERM.**Lecture 13: Mon, Oct 25**__Read__: everything so far.. Dynamic Programming, Rod Cutting.**Lecture 14: Wed, Oct 27**__Read__: CLRS, sec 15.1.. Longest common subsequence.**Lecture 15: Mon, Nov 1**__Read__: CLRS, 15.4.. More DP: matrix chain multiplication, text allignment.**Lecture 16: Wed, Nov 3**__Read__: CLRS, sec 15.4, Notes on Text Alignment (.pdf). Greedy algorithms. Activity selection.**Lecture 17: Wed, Nov 10**__Read__: CLRS, sec 16.1.. Greedy proof techniques: always stay ahead, local swap. Intro to Huffman Codes.**Lecture 18: Thu, Nov 11**__Read__: CLRS, sec 16.2-16.3.. Huffman Codes.**Lecture 19: Mon, Nov 15**__Read__: CLRS, sec. 16.3.. On-Line Prefix Free Codes (SOLE encoding).**Lecture 20: Wed, Nov 17**__Read__: Notes on PFEs (.pdf). Demo of SOLE. Graphs, their representations. Breadth-first search.**Lecture 21: Mon, Nov 22**__Read__: CLRS. 22.1-2.. BFS: analysis, properties, classification of edges. Depth-First Search.**Lecture 22: Tue, Nov 23**__Read__: CLRS: 22.2-3.. DFS analysis, parenthesis and white-path theorem, clasisfication of edges. Topological Sort.**Lecture 23: Mon, Nov 29**__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, Dec 1**__Read__: CLRS, sec. 23, 24 (before 24.1).. Dijkstra's algorithm (non-negative weights), BFS revisited (simple queue in Dijkstra).**Lecture 25: Mon, Dec 6**__Read__: CLRS, sec. 24.3, 24-5.. Bellman-Ford algorithm (no negative cycles), acyclic graphs. All-pairs shortest paths. Matric multiplications approach.**Lecture 26: Wed, Dec 8**__Read__: CLRS, sec 24.1-2, 25.1.. Floyd-Warshall. Transitive Closure. Johnson's algorithm. Final Review.**Lecture 27: Mon, Dec 13**__Read__: CLRS, sec 25.2-3.. Introduction to Number Theory and Cryptography. RSA encryption.**Lecture 28: Wed, Dec 15**__Read__: CLRS, sec 31.

Back to the course page