SUNY Geneseo Department of Computer Science
CSci 240, Spring 2007
Prof. Doug Baldwin
Due Tuesday, March 6
Loop invariants and their role in algorithm design are described in section 8.1 of our textbook. This material was also discussed in the February 26 lecture.
Design, and code in Java, algorithms for solving each of the following problems. For each problem, I describe the problem and then hint at an algorithm by describing a loop invariant that the algorithm's main loop can maintain. Your algorithms should be based on these invariants. You may code the algorithms in a single program, if you wish -- I envision such a program containing a main method that demonstrates the algorithms, and various other methods and/or classes that actually implement the algorithms.
(A warm-up problem, to help you get a sense for what I'm asking you to do in this lab. I expect that the algorithm you devise to solve this problem will be pretty obvious, the interesting thing to concentrate on is how that algorithm relates to the loop invariant I give you.)
The problem is to search a one-dimensional array, A, for a value, x. You may assume the array contains whatever type of value you find convenient (e.g., you could work on an array of int, or an array of String, etc.) The algorithm should return a boolean value, true if some element of A equals x, and false if no element of A equals x.
The algorithm should work by stepping an index, i, through A, maintaining the loop invariant that elements 0 through i-1 (inclusive) of A are known not to equal x. This invariant holds at the beginning of every iteration of the loop.
The problem is to find the shortest distances on a map from a given starting point to other points. This is essentially the problem that Web sites such as MapQuest solve when planning a trip for you, and the algorithm you will develop to solve the problem is representative of the algorithms those Web sites use.
More precisely, the "map" consists of a number of points (e.g., street intersections on a high-resolution map, towns on a lower resolution map, etc.) with roads between them. There is a distance associated with every pair of adjacent points (i.e., every pair of points such that there is a road with no intermediate intersections between those points). Given a point at which a trip is to start, you are to find the shortest distances from that point to all other points (i.e., if you want to go from one point to another, there are generally several sequences of roads you can take; you want to find the total length of the shortest such sequences from the starting point to each other point).
One way to solve this problem is to divide the points in the map into two sets: points whose shortest distance to the starting point is known, and points whose shortest distance to the starting point is only estimated. Call the points with known distances "finalized," and the others "unfinalized." You can then step through the unfinalized points, finalizing them one by one, while maintaining the loop invariant that the estimated distance for each unfinalized point is the shortest distance from the starting point to that unfinalized point if you follow a route that passes only through finalized points. It turns out that this loop invariant implies that at any iteration of the loop, the unfinalized point with the shortest estimated distance is actually finalized -- i.e., its estimated distance is really the shortest possible distance from the starting point. This fact makes it easy to figure out which point to finalize in each iteration of the loop.
To actually code this algorithm you will need a way to represent maps and points within them. A simple table representation works well: if there are a total of n points in the map, use a two-dimensional array, A, to store distances between points, such that A[i][j] is the length of the road from the ith point to the jth point. If there is no direct road between points i and j, A[i][j] is as nearly infinite as you can make it (i.e., a number larger than any reasonable real distance). Note that "direct road" means a road with no intermediate intersections. For example, if there is a road from a to b and then from b to c, A[a][c] would be infinite, even though it is possible to travel a lesser distance from a to c -- discovering this distance (and other, less obvious, ones) is the goal of the algorithm you are developing here. With this representation of maps, it is natural to represent individual points as integers between 0 and n-1 (i.e., indices to the map).
In addition to a representation for the map, you will also need some auxiliary data structures. In particular, you will need to keep track of final and estimated distances from the starting point to each point in the map, and you will need to keep track of which points are finalized and which are unfinalized. It is easy to keep track of both of these things in one-dimensional arrays: an array of distances, whose ith element is the distance (either estimated or actual) to point i, and an array of boolean flags, whose ith element is true if and only if point i is finalized.
Finally, I expect that the main loop in your algorithm will contain several short inner loops. For each of these loops, identify and state a loop invariant that captures how the loop works. You can state these loop invariants in comments in your code.
I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office.
I would like to read and run your program during our meeting. To do this, you can either bring the program to my office on a laptop computer, or we can go to a lab during the meeting.