CS 206: Data Structures
Assignment#8

Due in class by 10:10a on Tuesday, May 2
NO LATE SUBMISSIONS ALLOWED

Carefully study the files puzzle.py, Graph.py, and Node.py

Together they implement the Graph data type and two blind searches Breadth-first and Depth-First (file: Graph.py). The class Node (file: Node.py) implements a graph search node that is used by the search algorithms. The file: puzzle.py contains a program that inputs a data file of the entire map of the USA (states and their neighbors) and constructs a graph (using the Graph class provided in Graph.py). The data file can be downloaded from here: Map.data. puzzle.py also shows how to use the search algorithms: Given a start state and a destination state, the algorithms will output a path, if it exists.

The search algorithm also uses the Stack class (file: Stack.py) and the Queue class (file:myQueue.py): Both of which have the functions insert and remove defined for adding and removing items from the structure).

Do:

1. Run the puzzle program provided to search for a path from California to Pennsylvania using depth-first and breadth-first searches.
2. Run the program to search for a path from Pennsylvania to California using the two searches.
3. Modify the program to solve the W-O-M-A-N puzzle: the goal is to go from Washington state to Washington, DC travelling only through states whose names begin with the letters in the word W-O-M-A-N. Run your program to use both searches. Also, try reversing the start and destinations (i.e. Washington-DC to Washington).

What to Hand-in:

1. The outputs from 1 and 2 above.
2. The outputs from 3.
3. A printout of the final versions of your program resulting from 3. ONLY hand in the files that were modified by you. Highlight the changes you made to the original programs.
   

Back to CS206 Course

Materials