Lectures

LectDateTopicReference
1 01/12 Introduction, history of algorithms, models of computation [DPV:0]
2 01/17 Asymptotic Analysis, worst-case and average-case analysis, randomized algorithms [DPV:0][KT:2]
3 01/19 Divide and conquer: sorting, polynomial multiplication, recurrence relations [DPV:2][KT:5][Ed:2]
4 01/24 Divide and conquer: median selection, more on recurrences (Assignment 1) [DPV:2][KT:5][Ed:3]
5 01/26 Graph representation, graph search [DPV:3][KT:3][Ed:13]
6 01/31 Directed graphs, strongly connected components, topological sort [DPV:3][KT:3][Ed:13]
7 02/02 Shortest paths in graphs (Assignment 1 due) [DPV:4][KT:6.8][Ed:14]
8 02/07 Binary search trees, red-black trees (Assignment 2) [Ed:7]
9 02/09 I/O-efficiency and B-trees
  • slides
  • notes
  • 10 02/14 Skip list
  • Notes
  • 11 02/16 Amortized analysis (Assignment 2 due) [Er:14,15]
    12 02/21 Maintaining disjoint sets (Assignment 3) [Er:16; Ed:16]
    13 02/23 Greedy techniques [Ed:5; Er:7]
    02/28 Exam 1 (Lectures 1-12)
    14 03/01 Dynamic programming (Assignment 3 due) [DPV:6]
    15 03/13 Dynamic programming [DPV:6]
    16 03/15 Minimum spanning tree [DPV:5]
    17 03/20 Shortest paths revisited (Assignment 4) [DPV:4.6][CLRS:23,24]
    18 03/22 Linear Programming [DPV:7]
    19 03/27 Simple Algorithm and Linear Programming [DPV:7.5,7.6], [CLRS:29]
    20 03/29 Polynomial multiplication & FFT (Assignment 4 due) [DPV:2.6],[KT:5.6]
    21 04/03 Cryptography & RSA (Assignment 5) [CLRS:31.7]
    22 04/05 Hashing [Er:12]
    23 04/10 NP Completeness: Definition of NP, 3SAT [DPV:8,Ed:23]
    24 04/12 Reduction between NP-Complete Problems (Assignment 5 due) [DPV:8,Ed:24]
    04/17 Exam 2 (Lectures 13-24) (Assignment 6)
    25 04/19 Examples of NP-Complete Problems [DPV:9,Ed:25]
    26 04/24 Approximation algorithms: TSP, set cover [DPV:9,Ed:25]
    04/26 Assignment 6 due
    04/30 Final Exam (All lectures) 7:00-10:00pm

    page top