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).**Lecture 01: Tue, Sep 2**__Read__: CLRS, skim section 1, read section 2.1, 2.2.. Better sorting: merge sort. Analysis of its running time (recursion tree + substitution methods). Comparison. Back to asymptotics notation. Introduction to Recurrences.**Lecture 02: Thu, Sep 4**__Read__: CLRS, section 2.3, 3 (skip 3.2 for now), 4.1, 4.2.. 4 methods for solving recureences: guess-and-verify (induction), recursion tree, (domain/range) substitution, "master" theorem (for common case when T(n) = aT(n/b) + f(n)).**Lecture 03: Tue, Sep 9**__Read__: CLRS, section 4 (skip complicated parts). More on Master Theorem (including its proof). Methods for computing sums: bounding terms method, integral method. Some examples of divide-and-conquer algorithms.**Lecture 04: Thu, Sep 11**__Read__: CLRS, section 4.3, 4.4.. Quicksort. Randomized Quicksort.**Lecture 05: Tue, Sep 16**__Read__: CLRS, section 7.. Heaps. Heapsort. Priority Queues.**Lecture 06: Thu, Sep 18**__Read__: CLRS, section 6.. Lower Bound for Comparison based sorting. Beating the lower bound: counting sort, radix sort.**Lecture 07: Tue, Sep 23**__Read__: CLRS, section 8.. Lower bound for Element Uniqueness. Medians and order statistics: randomized and worst-case selection.**Lecture 08: Thu, Sep. 25**__Read__: CLRS, section 9.. Hash Tables. Hashing by Chaining. Universal Hash Functions.**Lecture 09: Tue, Sep. 30**__Read__: CLRS, section 11.. Constructing Universal Hash Functions. Perfect hashing. Open Addressing. Analysis under Ideal Hashing.**Lecture 10: Thu, Oct. 2**__Read__: CLRS, section 11.. Binary Search Trees. Tree Walks (in-order, post-order, pre-order). Basic Ops (Insert, Delete, Search, Max, Min, Succ, Pred). Application to Sorting. Randomly Built Binary Search Trees.**Lecture 11: Tue, Oct. 7**__Read__: CLRS, section 12 (skip analysis of random binary tree).. Balanced Search Trees with O(log n) worst case Ops. 2-3-Trees, Red-Black Trees. Rotations.**Lecture 12: Thu, Oct. 9**__Read__:*2-3-Trees handout, CLRS, section 13.*. MIDTERM.**Lecture 13: Tue, Oct. 14**__Read__: everything so far.. Dynamic Programming, longest common subsequence.**Lecture 14: Thu, Oct. 16**__Read__: CLRS, sec 15.. More dynamic programming (text allignment, matrix chain multiplication, optimal search trees).**Lecture 15: Tue, Oct. 21**__Read__: CLRS, sec 15.. Greedy algorithms. Activity selection. Huffman Codes.**Lecture 16: Thu, Oct 23**__Read__: CLRS, sec 16.. Huffman Codes, fractional and 0-1 Knapsack. Aggregate analysis: multi-pop.**Lecture 17: Tue, Oct 28**__Read__: CLRS, sec 16.2, 16.3, 17.1, 17.2.. Incrementing binary counter, dynamic tables. Graphs, their representations. Breadth-first search.**Lecture 18: Thu, Oct 30**__Read__: CLRS, sec. 17.1-2, 22.1-2.. BFS: analysis, properties, classification of edges. Depth-First Search.**Lecture 19: Tue, Nov 4**__Read__: CLRS. 22.2-3.. DFS: analysis, parenthesis theorem, clasisfication of edges. Topological Sort.**Lecture 20: Thu, Nov 6**__Read__: CLRS: 22.2-3.. Strongly Connected Components, minimal spanning trees.**Lecture 21: Tue, Nov 11**__Read__: CLRS, 22.4, 23.1. Prim's and Kruskal's algorithms. Introduction to single-source shortest paths. Properties of shortests path.**Lecture 22: Thu, Nov 13**__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 23: Tue, Nov 18**__Read__: CLRS, sec. 24.1-3.. All-pairs shortest paths. Matric multiplications approach, Floyd-Warshall.**Lecture 24: Thu, Nov 20**__Read__: CLRS, sec 25.. More on all-pairs shortest paths. Examples. Transitive Closure. Johnson's algorithm.**Lecture 25: Tue, Nov 25**__Read__: CLRS, sec 25.. Maximum Flow. Definition, examples, basic properties. Residual Graphs, augmenting paths. Cuts, mincut=maxflow theorem.**Lecture 26: Tue, Dec 2**__Read__: CLRS, sec. 26.1-2.. More on mincut=maxflow. Ford-Fulkerson algorithm. Edmonds-Karp algorithm.**Lecture 27: Thu, Dec 4**__Read__: CLRS, sec. 26.2.. Application to maximum matching. Hall's marriage theorem. A telepathic card trick.**Lecture 28: Tue, Dec 9**__Read__: CLRS 26-3.

Back to the course page