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: Tue, Sep 4**__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: Tue, Sep 11**__Read__: CLRS, section 4.3-4.5 (skim 4.5).*Introductory Notes (.pdf)*. "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: Tue, Sep 18**__Read__: CLRS, sections 4.5-4.6 (4.6 optional), 4.1-2.. Quicksort. Randomized Quicksort. Heaps. Heapsort. Priority Queues.**Lecture 04: Tue, Sep 25**__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: Tue, Oct 2**__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: Tue, Oct 9**__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: Tue, Oct 23**__Read__: everything so far.. Dynamic Programming. Rod Cutting, Longest Common Subsequence, Text Alignment.**Lecture 08: Nov 6**__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. Greedy always stay ahead technique.**Lecture 09: Tue, Nov 13**__Read__: CLRS, sec 15.2-3, 16.1.. Greedy algorithms. Activity selection. Greedy proof techniques: always stay ahead, local swap. Huffman Codes. On-Line algorithms: Prefix Free Codes (SOLE encoding).**Lecture 10: Tue, Nov 20**__Read__: CLRS, sec 16.1-3. Notes on Greedy Algorithms (.pdf), Notes on PFEs (.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: Tue, Nov 27**__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: Tue, Nov 27**__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: Tue, Dec 4**__Read__: CLRS, sec 24.1-2, 25.1-3.. Introduction to Number Theory and Cryptography. RSA encryption. Final Review.**Lecture 14: Tue, Dec 11**__Read__: CLRS, sec 31.

Back to the course page