October 9, 2024
Wednesday of Week 7
Topics of the day
- Graphs
- Pathfinding
- Brute-force search
Suggested readings
- Sections 3.1, 3.2 from George Luger, Artificial Intelligence, 5e
- Sections 3.1, 3.2 from George Luger, Artificial Intelligence, 6e
- Sections 9.1, 9.3.1, 9.6 from Mark Allen Weiss, Data structures and algorithm analysis in C++, 3e
Online references
- Graph (en.wikipedia.org)
- Tree (en.wikipedia.org)
- Depth-first search (en.wikipedia.org)
- Breadth-first search (en.wikipedia.org)
- Iterative deepening depth-first search (en.wikipedia.org)
- Iterative deepening vs depth-first search (stackoverflow.com)
Questions and exercises
- Draw a graph that is not also a tree. What is it that makes it not a tree? (Or, what property of a graph makes that graph a tree?)
- Draw a tree (with a clearly labelled root) and at least six nodes in at least three levels. Give an order the nodes might be visited in a depth-first search, and an order the nodes might be visited in a breadth-first search.
Consider the graph in the image to the right. Give three different orders for visiting the nodes that correspond to possible depth-first searches, and three different orders that correspond to possible breadth-first searches.
Assignments
Upcoming
- Exam 1 due (14 Oct)
- Project 3: A* out (14 Oct)
