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. Asymptotic notation (O, o, Omega, omega, Theta). Divide-and-conquer (recursion). Introduction to Recurrences. Better sorting: merge sort. Analysis of its running time (recursion tree).**Lecture 01: Wed, Sep 7**__Read__: CLRS, skim section 1, read sections 2-3 (skim 3.2).. Methods for solving recureences: recursion tree, guess-and-verify (induction), (domain/range) substitution, "master theorem" (MT) for common case when T(n) = aT(n/b) + f(n). Intuition for proof of MT.**Lecture 02: Wed, Sep 14**__Read__: CLRS, section 4.3-4.5 (skim 4.5, 4.6 optional).*Introductory Notes (.pdf)*. Examples of divide-and-conquer: binary search, stock profit (same as maximum subarray), raising to power, Fibonachi numbers, Karatsuba multiplication, matrix multiplication, VLSI layouts. Intro to Quicksort.**Lecture 03: Wed, Sep 21**__Read__: CLRS, sections 4.5-4.6 (4.6 optional), 4.1-2, MIT Notes.. Quicksort. Randomized Quicksort. Heaps. Heapsort. Priority Queues.**Lecture 04: Wed, Sep 28**__Read__: CLRS, section 7.1-7.3, optional 7.4, section 6.. Lower Bound for Comparison based sorting. Lower bound for Element Uniqueness. Beating the lower bound: counting sort, radix sort. Medians and order statistics: randomized and worst-case selection. Introduction to Binary Search Trees. Tree Walks (in-order, post-order, pre-order).**Lecture 05: Wed, Oct 5**__Read__: CLRS, sections 8.1-8.3, 9, 12.1.. Binary Search Trees. Basic Ops (Insert, Delete, Search, Max, Min, Succ, Pred). BST Sorting. Connection with Quicksort. Randomly Built Binary Search Trees. Balanced Search Trees with O(log n) worst case Ops: 2-3-Trees. Insertion, deletion. Augmenting Data Structures. Maintaining number of nodes, application to dynamic order statistics (rank(T,node), select(T,k)).**Lecture 06: Wed, Oct 12**__Read__: CLRS, section 12.1-3, 12.4 (skip complicated parts), 2-3-Trees handout, CLRS, skim 14.1-14.2 (replace RB-trees by 2-3-trees).. Dynamic Programming. Rod Cutting, Longest Common Subsequence, Text Alignment.**Lecture 07: Wed, Oct 19**__Read__: CLRS, sec 15.1, 15.4, Notes on Text Alignment (.pdf). MIDTERM.**Lecture 08: Wed, Oct 26**__Read__: everything so far (not including dynamic programming).. DP techniques (overlapping subproblems, memorization, small->large ordering). Matrix chain multiplication, Optimal Search Trees. Introduction to Greedy Algorithms: Trivial Text Alignment.**Lecture 09: Wed, Nov 2**__Read__: CLRS, sec 15.2-3, 15.5, 16.1.. Activity Selection. Greedy algorithms and proof techniques: greedy always stay ahead, local swap. Huffman Codes.**Lecture 10: Wed, Nov 9**__Read__: CLRS, sec 16.1-3. Notes on Greedy Algorithms (.pdf).. Graphs, their representations. Breadth-first search: analysis, properties, classification of edges. Depth-First Search: analysis, parenthesis and white-path theorem, clasisfication of edges. Test for acyclicity (no back edges).**Lecture 11: Wed, Nov 16**__Read__: CLRS. 22.1-3.. Topological Sort. Strongly Connected Componenets. Minimal spanning trees. Prim's and Kruskal's algorithms.**Lecture 12: Wed, Nov 30**__Read__: CLRS, 22.4, 23.. Introduction to single-source shortest paths. Dijkstra's algorithm (non-negative weights), BFS revisited (simple queue in Dijkstra). Bellman-Ford algorithm (no negative cycles), acyclic graphs. Solving difference constraints. All-pairs shortest paths. Matric multiplications approach. Floyd-Warshall. Transitive Closure. Johnson's algorithm.**Lecture 13: Wed, Dec 7**__Read__: CLRS, sec 24.1-3, 25.1-3.. FINAL EXAM.**Lecture 14: Wed, Dec 14**

Back to the course page