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: Mon, Sep 12**__Read__: CLRS, skim section 1, read sections 2-3 (skim 3.2).. Analysis of merge sort (recursion tree).Methods for solving recureences: recursion tree, guess-and-verify (induction), (domain/range) substitution, intro to "master theorem" (MT) for common case when T(n) = aT(n/b) + f(n).**Lecture 02: Mon, Sep 19**__Read__: CLRS, section 4.3-4.5 (skim 4.5).. "Master theorem" (MT) for common case when T(n) = aT(n/b) + f(n). Intuition for proof of MT. Other examples of divide-and-conquer: binary search, stock profit (same as maximum subarray), Karatsuba multiplication, matrix multiplication, VLSI layouts.**Lecture 03: Wed, Sep 21**__Read__: CLRS, sections 4.5-4.6 (4.6 optional), 4.1-2.. Quicksort. Randomized Quicksort. Heaps. Heapsort. Priority Queues.**Lecture 04: Mon, Oct 3**__Read__: CLRS, section 7.1-7.3, optional 7.4, section 6.. Lower Bound for Comparison based sorting. 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: Mon, Oct 17**__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. Connection with Red-Black Trees. Augmenting Data Structures. Maintaining number of nodes, application to dynamic order statistics (rank(T,k), myrank(T,node)).**Lecture 06: Wed, Oct 26**__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).*. MIDTERM.**Lecture 07: Mon, Oct 31**__Read__: everything so far.. Dynamic Programming. Rod Cutting, Longest Common Subsequence, Text Alignment.**Lecture 8: Nov 7**__Read__: CLRS, sec 15.1, 15.4, Notes on Text Alignment (.pdf). DP techniques (overlapping subproblems, memorization, smal->large ordering). Matrix chain multiplication. Introduction to Greedy Algorithms: DP for Activity Selection.**Lecture 9: Wed, Nov 14**__Read__: CLRS, sec 15.2-3, 16.1.. Greedy algorithms. Activity selection. Greedy proof techniques: always stay ahead, local swap. Huffman Codes.**Lecture 10: Wed, Nov 21**__Read__: CLRS, sec 16.1-3.. 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: Mon, Nov 28**__Read__: CLRS. 22.1-3. Start 22.4.. Topological Sort. Minimal spanning trees. Prim's and Kruskal's algorithms. Introduction to single-source shortest paths. Dijkstra's algorithm (non-negative weights), BFS revisited (simple queue in Dijkstra).**Lecture 12: Mon, Dec 5**__Read__: CLRS, 22.4, 23, 24 (before 24.1), 24.3, 24.5.. 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: Mon, Dec 12**__Read__: CLRS, sec 24.1-2, 25.1-3.. Introduction to Number Theory and Cryptography. RSA encryption. Final Review.**Lecture 14: Mon, Dec 14**__Read__: CLRS, sec 31.

Back to the course page