Lectures

Date Lecture Lecture Readings
01/25/17 Introduction to algorithms and data structures. Euclidean algorithm. Lecture 1 CRLS 31.3
01/30/17 Warm-up: Insertion sort and merge sort. Lecture 2 CRLS 2
02/01/17 Analysis of algorithms and asymptotic notation. Lecture 3 CRLS 3
02/06/17 Divide and conquer I: Maximum subarray. Lecture 4 CRLS 4.1
02/08/17 Divide and conquer II: Strassen’s algorithm. Lecture 5 CRLS 4.2
02/13/17 Solving recurrences with Master theorem and substitution method. Lecture 6 CRLS 4.3 and CLRS 4.5
02/15/17 Randomized algorithms I: Karger’s algorithm for minimum cut. Lecture 7 See here
02/20/17 Randomized algorithms II: Balls and bins; Freivald’s algorithm for matrix product verification. Lecture 8 See here and 5.2 from here
02/22/17 Sorting I: Heapsort. Lecture 9 CLRS 6
02/27/17 Sorting II: Sorting in linear time: Counting sort and bucket sort. Lecture 10 CLRS 8
03/01/17 Sorting III: Quicksort. Lecture 11 CLRS 7 and see 3.4.1 from here for the analysis
03/06/17 Sorting IV: Quicksort (continued). Lecture 12 CLRS 7 and see 3.4.1 from here for the analysis
03/08/17 Selection in expected linear time. Lecture 13 CLRS 9.1 and CLRS 9.2
03/13/17 Selection in worst-case linear time. Lecture 14 CLRS 9.3
03/15/17 MIDTERM EXAM. no lecture.  
03/20/17 SRPING BREAK. no lecture.  
03/22/17 SPRING BREAK. no lecture.  
03/27/17 Stacks, queues, linked lists. Lecture 15 CLRS 10
03/29/17 Hash tables I: Universal hashing. Lecture 16 CLRS 11.1-11.3
04/03/17 Hash tables II: Open addressing and perfect hashing. Lecture 17 CLRS 11.4-11.5
04/05/17 Binary search trees. Lecture 18 CLRS 12.1-12.3
04/10/17 Red-black trees. Lecture 19 CLRS 13.1-13.2 and see here (except pages 5, 6, 7) for the insertion and deletion algorithms
04/12/17 Dynamic programming: Rod cutting and longest common substring. Lecture 20 CLRS 15.1 and see here
04/17/17 Graph algorithms I: BFS and DFS. Lecture 21 CLRS 22.2 and CLRS 22.3. For the BFS proof of correctness see here
04/19/17 Graph algorithms II: Shortest paths and Dijkstra’s algorithm. Lecture 22 CLRS 24.3
04/22/17 Graph algorithms III: Minimum spanning trees. Lecture 23 CLRS 23
04/24/17 Number-theoretic algorithms and RSA. Lecture 24 CLRS 31
05/01/17 Polynomial multiplication using FFT. Lecture 25 For this lecture see Chapter 2.6 from here
05/03/17 NP-completeness. Lecture 26 See here
05/08/17 Special topics I: Computational geometry (convex hull and 2D closest pair). Lecture 27 See page 5 from here and here
05/11/17 Special topics II: Approximation algorithms (vertex cover and geometric TSP). Lecture 28 CLRS 35.1-35.2