Lecture 31

Lecture 31: Using Hashing; Limitations of Algorithms
Date: Monday, April 20, 2026

Agenda

Announcements
- Academic Showcase Project
  - all groups should be signed up through the formal Academic Showcase system
  - one more progress report this Friday
  - then the event the following Friday (time yet TBD)
  - then the writeup is due on the last day of classes
- Problem Set 5: [PDF] any remaining hard copies must be in now
- Problem Set 6: [PDF] due last day of classes
- Lab 9: Prim's Algorithm, Dijkstra's Algorithm, Traversals any stragglers who still need a checkpoint, tag me on anything remaning before your lab tomorrow so I can finalize those
- Lab 10: Backtracking tomorrow includes a programming component so bring your computers if you want to use your own
- RSVP for the end-of-semester/Vandenberg retirement dinner
Revisiting a problem where hashing can improve time efficiency: Problem Set 4, Question 10
Limitations of Algorithms
- lower bounds
  - trivial lower bounds
  - decision trees

Terminology