Lectures and Recitations

• 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)
  • Readings: CLRS, 15.3–15.4.

• Lecture 12: Dynamic Programming (4)
• Recitation 12: Quiz review; Tris

• Lecture 13: Sorting (1) Heaps
  • Readings: CLRS, 6.1, 6.2.
• Recitation 13: Max-heapify, Building a heap

• Lecture 14: Sorting (2) Heaps
  • Readings: CLRS, 6.3, 6.4.
• Recitation 14: Priority Queues (CLRS 6.5)

• Lecture 15: Sorting (3) Counting Sort
  • Readings: CLRS, 8.1, 8.2
• Recitation 15: Gas Simulation

• Lecture 16: Sorting (4) Radix Sort
  • Sorting algorithms race
  • Readings: CLRS, 8.3, 8.4
• Recitation 16: Quick sort; Bucket Sort

• Lecture 17: Search (1)
  • Readings: CLRS, 22.1, 22.2, Appendix B.4
• Recitation 17: Graph representations; Rubik's cube representations.

• Lecture 18: Search (2) BFS
  • Readings: CLRS, 22.2, 10.1 (Queues)
• Recitation 18: Breadth First Trees; 2-way BFS.

• Lecture 19: Search (3) DFS
  • Readings: CLRS, 22.3, 22.4
• Recitation 19: BFS and DFS; Articulation Points

• Lecture 20: Shortest Paths (1)
  • Readings: CLRS, 24 intro
• Recitation 20 Shortest Path Properties

• Lecture 21: Shortest Paths (2) Bellman-Ford
  • Readings: CLRS, 24.1

• Lecture 22: Shortest Paths (3) Dijkstra
  • Readings: CLRS, 24.2, 24.3

• Lecture 23: Shortest Paths (4) Dijkstra & Potentials
  • Readings: Dijsktra speedups paper, Dijkstra speedups corrections
• Recitation 21 Dijkstra homework problem; detailed review of priority queue/heaps.

• Lecture 24: Numerics (1)
• Recitation 22 Strassen Matrix Multiplication; Master Method

• Lecture 25: Numerics (2)
  • sqrt.py
• Recitation 23 Newton's Method with fractions; Radix Conversion

• Lecture 26: Future classes