home

This course is divided in 3 parts:

• Intro and sorting. Exam 1.
• Data structures, dynamic programming, and amortization. Exam 2.
• Graph algorithms and NP-completeness. Exam 3.

NOTE: Section numbers below refer to the linked "Reading" page, not CLRS.

• Lecture 9: Tuesday, February 12
  • Expected time analysis of Quicksort.
  • Reading: Section 4.4 b and c.
  
  
• Lecture 7: Thursday, February 7
  • IRV, and beginning of Quicksort
  • Reading: Section 4.4a and Section 15
  
  
• Lecture 6: Tuesday, February 5
  • Sorting lower bound; Counting sort and Radix sort.
  • Reading: Sections 4.5 and 4.6
  
  
• Lecture 5: Thursday, January 31
  • (Selection continued). Heaps
  • Reading: Section 4.3
  
  
• Lecture 4: Tuesday, January 29
  • Details of Master Method, and deterministic selection (median-finding)
  • Reading: section 5.1
  
  
• Lecture 3: Thursday, January 24
  • More recurrences by trees and substitution. Master method.
  • Reading: Section 3.1, and Section 3.2.
  
  
• Lecture 2: Tuesday, January 22
  • big-O proofs, mergesort and its recurrence
  • Reading: All of Section 2, Section 4.2, and the beginning of Section 3.1 (including the recursion tree method; we will do substitution on Thursday.)
  
  
• Lecture 1: Thursday, January 17
  • Intro, Insertion sort
  • Reading: Section 4.1.