Homework 10: Search and Hashing

Implement search from scratch and measure what it costs. You will write linear and binary search, identify the assumption binary search depends on, and time lookups across lists, dictionaries, and sets to see for yourself why hash-based lookup wins — your first empirical look at efficiency tradeoffs.

Related session: Session 11 — Search and Hashing

Topics Covered

• Search as a fundamental operation
• Linear versus binary search and the assumptions each requires
• Hashing intuition: why dictionary and set lookup is fast
• Timing code and comparing approaches empirically
• Introductory efficiency tradeoffs

Instructions

The detailed tasks, starter notebook, and submission instructions for this assignment have not been posted yet. Please check back after the November 4 session.