Bill's 6.046 Recitations, Fall 2004

These materials are for my 6.046 sections. They are held Fri 12pm and 1pm in 36-153.

My office hours are Sat 1-3pm in 36-153.

Please send anonymous feedback about recitation.

Exam Preparation

• Practice questions

Recitation Notes

• Recitation 1 Notes: Proving correctness.
• Recitation 2 Notes: Recurrences.
• Recitation 3 Notes: Heaps.
• Recitation 4 Notes: Quiz review.
• Recitation 5 Notes: Binary search trees.
• Recitation 6 Notes: Augmenting data structures.
• Recitation 7 Notes: Competitive analysis.
• Recitation 8 Notes: Dynamic programming vs. greedy.
• Recitation 9 Notes: Depth-first search.
• Recitation 10 Notes: Convex hull.
    - Supplement 1: Why Graham-Scan needs to sort (also in PowerPoint)
    - Supplement 2: Great slides from Iowa State (also in PowerPoint: Part 1, Part 2)
• Recitation 11 Notes: Network flow, String Matching.

Recitation Handouts

• Recitation 2: Master Theorem Practice and Solutions
• Recitation 7: Sleator and Tarjan paper on Self-Organizing Lists (need MIT IP address to download)
• Recitation 7: George Savvides's notes (pages 1, 2, 3, 4, 5, 6) on competitive analysis (ask me for hardcopy, easier to read)
• Sketch of Problem Set 7 Solutions

Links

• More goodies at David's recitation.
• It pays to know about convex hull.