algo home

• Before you start
  • Review discrete math and data structures. (Resources: section 1)
  
  

• Week 1
  September 3-5
  • Insertion sort. Big-O notation. (Resources: section 2)
  
  
• Week 2
  September 8-12
  • Merge sort. Analyzing recurrences: (i) with trees; (ii) by induction; (iii) via master method (Resources: section 3.1 & 3.2)
  
  
• Week 3
  September 15-19. (add/drop on 16)
  • Heap building and heap sort (Resources: section 4.3)
  • The sorting lower bound (Resources: section 4.4)
  • Counting sort and Radix sort. (Resources: section 4.5)
  
  
• Week 4
  September 22-26
  • Deterministic Selection. (Resources: section 6.3)
  • RandSelect (Resources: section 8.2, without the longer derivation)
  • Quicksort (Resources: section 8.1.a) -- You don't need to focus on the details of how to partition in-place.
  • Exam 1, Friday the 26th, covering weeks 1,2,3.
  
  
• Week 5
  September 29 - October 3
  • Hashing. (Resources: section 5)
  • Binary search tree (BST) intro. (Resources: section 9.1)
  • Expected time to build a random BST, and expected depth of a BST. (Resources: section 9.2)
  
  
• Week 6
  October 6-10
  • Red-black trees (Resources: section 9.3) -- The objective here is not so much to memorize the various cases, it's to understand why these trees are balanced, and that it's possible to keep them balanced.
  • Augmenting BSTs (Resources: section 10)
  
  
• Week 7
  October 14-17 (holiday on 13)
  • Amortized analysis (Resources: section 11)
  
  
• Week 8
  October 20-24
  • Exam 2, Monday the 20th, covering weeks 4,5,6.
  • Continue: Amortized analysis (Resources: section 11)
  • Start dynamic programming (Resources: section 12)
  
  
• Week 9
  October 27-31
  • Continue dynamic programming (Resources: section 12)
    
  
  
• Week 10
  November 3-7
  • Graphs: Intro, BFS & DFS (Resources: 13.1, 13.2)
  • Topological sort (Resources: 13.3)
  
  
• Week 11
  November 10-14
  • Exam 3, Monday the 10th, covering weeks 7,8,9.
  • Minimum spanning trees (MST). (Resources: section 14)
  
  
• Week 12
  November 17-21
  • Single-source shortest paths (SSSP) (Resources: section 15)
  
  
• Week 13
  November 24-25 (holiday during 26-28)
  • Continue SSSP (Resources: section 15)
  
  
• Week 14
  December 1-5
  • Review
  • Exam 4, Friday the 5th, covering weeks 10,11,12,13.
  
  
  
  
  
  
  

  ---

  ---

• Topics from the Resources page that we won't cover
  • Indicator random variables (Resources: section 7)
  • Strongly connected components. (SCC; Resources: 13)
  • P vs NP (Resources: section 16)
    • I recommend taking a look at P vs NP at some point. Nobody should get a CS degree without knowing some of the basic concepts. Ideally it will be covered in greater detail in another course (on theory of computation).
  
  
  
  
  
  

  ---

  ---

• Topics that you might find in other intro to Algorithms courses, that we probably won't cover.
  Not to imply that this course is easier; we emphasize some things that others don't.
  • Network flow
  • Linear programming
  • Approximation algorithms
  • All-pairs shortest paths
  • String matching
  • ...