*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 |