Lectures and Recitations

Revision as of 15:14, 18 October 2007

• Lecture 1: Introduction, Document Distance
  • Document Distance
  • Readings: CLRS, chapters 1, 2, 3.
• Recitation 1: Document Distance; Python Lists

• Lecture 2: Document Distance (2)
  • Document Distance Program Version 3, Document Distance Program Version 4, Document Distance Program Version 5
  • Readings: CLRS, chapter 11, sections 1 and 2.
  • Resources: Python Cost Model
• Recitation 2: Document Distance; Flatten

• Lecture 3: Document Distance (3)
  • Document Distance Program Version 6, mergesort.py
  • Python log from lecture
• Recitation 3: Maximum Contiguous Subarray

• Lecture 4: Binary Search Trees
  • Readings: CLRS, chapter 10, and chapter 12, sections 1–3.
• Recitation 4: BST Augmentation; Python OO

• Lecture 5: Balanced Binary Search Trees
  • See references page for papers with proofs relating to balanced BSTs.
  • Readings: CLRS, chapter 13, sections 1 and 2 (warning: red-black trees -- read for culture).
• Recitation 5: Rotations; Balanced BSTs

• Lecture 6: Hashing (1)
  • Readings Lecture slides from OCW, CLRS, chapter 11, sections 1 and 2.
• Recitation 6: Hashing; hash()

• Lecture 7: Hashing (2)
  • Readings: CLRS, 11.3 and 32.2.
• Recitation 7: String Matching; Rabin-Karp

• Lecture 8: Hashing (3)
  • Readings: CLRS, chapter 11, section 4.
• Recitation 8: Hash Tables

• Lecture 9: Dynamic Programming (1)
  • Readings: CLRS, 15.1–15.3.
• Recitation 9: Image Resizing; Matrix Chain Multiplication
• Recitation 10: Stamps; Longest Increasing Subsequence; Knapsack

• Lecture 10: Dynamic Programming (2)
  • Image Compression Handout
• Recitation 11: Shortest vs. Longest Path; 1 Dimensional Image compression

• Lecture 11: Dynamic Programming (3)

• Lecture 12: Dynamic Programming (4)