In this assignment students work either individually or in pairs to write a function that finds the shortest path between two cities in a graph. Using recursion, students must find the length of the shortest path (and optionally the path itself) between two given cities using a dictionary representing a graph of cities that only have paths from east to west. This assignment reviews one form of graph representation and a basic shortest path algorithm. It is useful for students who are new to graphs.
Integrate pair programming when it is appropriate for students to collaborate on a lab, assignment, or project. Have the “driver” controls the mouse and the keyboard, while the “navigator” makes suggestions, points out errors, and asks questions. Partners routinely switch roles to gain the benefits of each role.
Relates the CS topics to concepts from students' own experience to Employ Meaningful and Relevant Content.