October 20, 2025
Monday of Week 9
Topics of the day
- A and A*
- Implementing best-first search
- Using hash tables
Suggested readings
- Sections 4.2, 4.3 from George Luger, Artificial Intelligence, 5e
- Sections 4.2, 4.3 from George Luger, Artificial Intelligence, 6e
Online references
- Admissibility (en.wikipedia.org)
- A* (en.wikipedia.org)
- Dijkstra's and A* (www.redblobgames.com)
- unordered_set in C++ (en.cppreference.com)
- HashSet in Java (docs.oracle.com)
Questions and exercises
- Why is best-first search an improvement over Dijkstra's algorithm?
- What is the problem with using greedy best-first search?
- In a brief definition: what makes a heuristic admissible?
- What can/can't a hash table guarantee about how its data is stored and how it is retrieved? You can be thinking in terms of both correctness and speed.
Assignments
Today
- Homework 4 due
Upcoming
- Project 3: A* prep due (22 Oct)
- Project 3: A* design due (27 Oct)
- Homework 4 revision (27 Oct)