algo home

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

• Week 1
  Sep. 7-9
  • Insertion sort. Big-O notation. (Resources: section 2)
    Until page 41 of bigO.pdf
  
  
• Week 2
  Sep. 12-16
  • More Big-O.
  • Merge sort. Analyzing recurrences: (i) with trees; (ii) by induction (Resources: section 3.1)
  
  
• Week 3
  Sep. 19-23
  • Analyzing recurrences with the master method. (Resources: section 3.2)
  • Heap building and heap sort (Resources: section 4.3)
  • Decision trees and the sorting lower bound (Resources: section 4.4)
  
  
• Week 4
  Sep. 26-30
  • Deterministic Selection. (Resources: section 6)
  • Counting sort and Radix sort. (Resources: section 4.5)
  
  
• Week 5
  Oct. 3-7
  • Indicator random variables (Resources: section 7)
  • Hashing. (Resources: section 5)
  
  
• Week 6
  Oct. 11-14 (class on 11 instead of 10)
  • RandSelect (Resources: section 8.2)
  • Quicksort (Resources: section 8.1.a)
    The analysis in section 8.1.b is similar to 8.2, and might be left for self-study.
    You don't need to focus on the details of how to partition in-place.
  
  
• Week 7
  Oct. 17-21
  • 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)
  • Red-black trees (Resources: section 9.3)
  • Note: on Wednesday the 19th, I will be teaching at 2pm in JABS 473, and prof. Reeves will teach at 5pm in our usual classroom.
  
  
• Week 8
  Oct. 24-28
  • Monday: Review for exam, discuss problem set. (on Zoom)
  • Tuesday, Oct. 25, 12:30pm - 1:50pm: EXAM 1       (Covering weeks 1-5, i.e. 9 lectures)
  • Augmenting BSTs. (Resources: section 10)
  
  
• Week 9
  Oct. 31 - Nov. 4
  • Amortized analysis (Resources: section 11)
  
  
• Week 10
  Nov. 7-11
  • Dynamic programming (Resources: section 12)
  
  
• Week 11
  Nov. 14-18
  • Graphs: Intro, BFS & DFS, topological sort, strongly connected components (SCC). (Resources: 13)
  • For SCC you only need to understand the definitions (slides 1-10), and what the algorithm does (relevant parts of slides 34-45). You don't need to understand all the intuition for the proof of correctness.
  
  
• Week 12
  Nov. 21-22. (no class on 23)
  • Monday: Review for exam, discuss problem set. (on Zoom)
  • Tuesday, Nov. 22, 12:30pm - 1:50pm: EXAM 2       (Covering weeks 6-10, i.e., 9 lectures)
  
  
• Week 13
  Nov. 28 - Dec. 2
  • Minimum spanning trees (MST). (Resources: section 14)
  
  
• Week 14
  Dec. 5-9
  • Single-source shortest paths (SSSP) (Resources: section 15)
    Note that we already covered the first 16 of 33 slides from section 15.1, in Week 13.
  
  
• Week 15
  Dec. 12-16
  • P vs NP (Resources: section 16)
    This topic will represent at most 10% of the points on exam 3. Only basic questions might be asked. You will not need to prove that some brand new problem is NP-hard.
  • Wednesday: Review for exam, discuss problem set.
  • Friday, Dec.16, 1pm: EXAM 3 (Covering weeks 11 & 13-15, i.e., 7 lectures).