46-927 Assignment #3

Due: November 13, 1997, 6:45 PM

Grading:

Your assignment will be compiled and executed. Seventy-Five points will be earned in Stage 1. In the Stage 1 code, you will earn 60 points if your program generates valid shortest paths from city to city for 10 random queries. The additional 15 points in Stage 1 will be earned if the code implements the memoizing strategy described in the objective.

The final 25 points will be earned in Stage 2. You will earn the full 25 points if you are able to generate valid paths (not neccessarily shortest) using interleaved planning and search once the map has been randomly changed. The Stage 2 methods MUST use the memoized information from Stage 1 to plan a route. If that route is invalid, the memoizing table information must be updated for the start to goal state path.

Your grade will be determined by summing the points you earned on each method.

Extra Credit: 15 points extra credit can be earned if your Stage 2 methods update the entire memoizing table when a route is discovered to be invalid. For example, if your program recieved Phoenix as a start state and Olympia as a goal state (large map), and Olympia is no longer accessible from Salem your program must:

1. Find an alternate route to Olympia that doesn't include Salem (required by normal-credit assignment).
2. Update the memoizing table so that the alternate route is stored for the Phoenix to Olympia query (required by normal-credit assignment).
3. Update all of the paths in the memoizing table that included the invalid Salem to Olympia transition, for example, Sacremento to Olympia. (required only for 10 points extra credit).
4. In a comment at the top of the file discuss the complexity of your extra credit updating algorithm using O notation.

Revised on Thursday, November 6, 1997