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: Wed, Jan 21**__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: Mon, Jan 26**__Read__: CLRS, section 2.3, 3 (skip 3.2 for now), 4.1, 4.2.. Methods for solving recureences: recursion tree, guess-and-verify (induction).**Lecture 03: Wed, Jan 28**__Read__: CLRS, section 4 (skip complicated parts). Other methods: (domain/range) substitution, "master" theorem (for common case when T(n) = aT(n/b) + f(n)).**Lecture 04: Mon, Feb 2**__Read__: CLRS, section 4.1-4.3.. More on master theorem (intuition for proof). Quicksort. Idea for Randomized Quicksort.**Lecture 05: Wed, Feb 4**__Read__: CLRS, section 4.3-4.4, 7.1-7.2.. Randomized Quicksort. Methods for computing sums: bounding terms method, integral method.**Lecture 06: Mon, Feb 9**__Read__: CLRS, section 7.3, Appendix A.. Heaps. Heapsort. Priority Queues.**Lecture 07: Wed, Feb 11**__Read__: CLRS, section 6.. Lower Bound for Comparison based sorting. Beating the lower bound: counting sort, radix sort.**Lecture 08: Wed, Feb 18**__Read__: CLRS, section 8.1-8.3.. Medians and order statistics: randomized and worst-case selection.**Lecture 09: Mon, Feb 23**__Read__: CLRS, section 9.. Hash Tables. Hashing by Chaining. Universal Hash Functions.**Lecture 10: Wed, Feb 25**__Read__: CLRS, section 11.1-11.3.. Constructing Universal Hash Functions. Open Addressing. Linear, Quadratic, Double, Ideal hashing. Analysis under Ideal Hashing.**Lecture 11: Mon, Mar 2**__Read__: CLRS, section 11.3-11.4.. Binary Search Trees. Tree Walks (in-order, post-order, pre-order). Basic Ops (Insert, Delete, Search, Max, Min, Succ, Pred).**Lecture 12: Wed, Mar 4**__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 13: Mon, Mar 9**__Read__:*2-3-Trees handout, CLRS, section 12.4 (skip complicated parts).*. MIDTERM.**Lecture 14: Wed, Mar 11**__Read__: everything so far.. Dynamic Programming, longest common subsequence.**Lecture 15: Mon, Mar 23**__Read__: CLRS, sec 15.1,15.4.. More dynamic programming (text allignment, matrix chain multiplication).**Lecture 16: Wed, Mar 25**__Read__: CLRS, sec 15.2,15.3.. Greedy algorithms. Activity selection.**Lecture 17: Mon, Mar 30**__Read__: CLRS, sec 16.1-16.2.. Huffman Codes.**Lecture 18: Wed, Apr 1**__Read__: CLRS, sec 16.3.. More Huffman Codes. Fractional and 0-1 Knapsack. Aggregate analysis: multi-pop.**Lecture 19: Mon, Apr 6**__Read__: CLRS, sec. 16.3, 17.1, 17.2.. Incrementing binary counter, dynamic tables (expand/contract).**Lecture 20: Wed, Apr 8**__Read__: CLRS, 17.1-2, 17.4.. Graphs, their representations. Breadth-first search. BFS: analysis, properties, classification of edges.**Lecture 21: Mon, Apr 13**__Read__: CLRS. 22.1-2.. Depth-First Search: analysis, parenthesis and white-path theorem, clasisfication of edges.**Lecture 22: Wed, Apr 15**__Read__: CLRS: 22.3.. Topological Sort. Minimal spanning trees.**Lecture 23: Mon, Apr 20**__Read__: CLRS, 22.3-4, 23.1. Prim's and Kruskal's algorithms. Introduction to single-source shortest paths. Dijkstra's algorithm (start).**Lecture 24: Wed, Apr 22**__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 25: Mon, Apr 27**__Read__: CLRS, sec. 24.1-3.. All-pairs shortest paths. Matric multiplications approach, Floyd-Warshall.**Lecture 26: Wed, Apr 29**__Read__: CLRS, sec 25.1-2.. Introduction to Number Theory and Cryptography. RSA encryption.**Lecture 27: Mon, May 4**__Read__: CLRS, sec 31.

Back to the course page