Computer Science 385
Design and Analysis of Algorithms
Spring 2026, Siena University
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
- lower bounds
- tight bounds
- trivial lower bounds
- information-theoretic lower bound
- decision trees