Outline:

1. ADTs: Map and Set
2. Implementing a map or a set
   • naive approach via a list
   • better approach via hash tables
   • handling collisions
   • trade-offs

What’s next

Upcoming events/assessments:

• Quiz 5 will be on Friday and cover the following Quiz Learning Objectives:
  • Core:
    • SH 1: sets/hash tables
    • SH 2: core hashing time complexity
  • Advanced:
    • SQ 7: using stacks/queues
    • SH 3: hashing time complexity
  • Repeats from before (not guaranteed, but likely):
    • LT 1: array-based lists (CR)
    • LT 2: core array-based list time complexity (CR)
    • LT 3: linked lists (CR)
    • LT 4: core linked-list time complexity (CR)
• CS Bits and Bytes tomorrow from 4:30pm-5:30pm in Olin 149: John Clapp ‘91 from Deriva Energy
• Carleton Undergraduate Research Symposium: Friday Oct. 17 from 4:30pm-5:30pm in the Rec Center
• Assignment 4 is due tomorrow
• No new assignments over midterm break – work on any resubmissions of A3 and A4

What you should do now:

• The readings (see below)
• Finish and submit Assignment 4
• Look at CS Courses on Workday and fill out your Match form

Reading assignment (to be completed by the next class):

Hashing (from today):

• Hash tables

Hashing (for next time):

• More on hashing