Special collaboration policy for Spring '03: for this assignment, you are permitted to work jointly with one classmate. If you choose to do so, you and your partner should submit your code and the readme.txt jointly (under one login name only). You and your partner will receive the same grade.
|
|
What if there are multiple shortest paths? Print out any one you like.
What's a good way to check my answers? Use the client program distances.c which only prints out the shortest path distances. You can diff the results against the ones produced by our reference solutions.
What should I do if the two vertices are not connected? Print that their distance is "infinity" or print out that they are not connected.
Is it OK to print the shortest path in reverse order. Yes. One hack to print it in the correct order is to switch s and d. Otherwise you could use a stack. But don't worry about it on this assignment.
The turtle graphics output doesn't view properly with turtle.c. Please use the version of turtle.c supplied in the map directory. We've customized it to print things out in landscape.
I can't see the blue dots that are supposed to represent the vertices that the algorithm examines. You might need to zoom in. Or you can change the value of SIZE in point.h.
How fast should my algorithm be? Fast.
|
|
Input and output. Here are a number of sample input files. The file usa.txt contains no queries, only a map description. The file usa-10.txt contains the same map description and 10 queries. The files named "usa-#short.txt" (where # is some number) contain the same map with # queries of relatively short distance. The files named "usa-#long.txt" contain queries of relatively long distances. If while debugging your program you would like to input queries "on the fly" (without having to change the input files), here is a useful Unix trick that might help you (you can replace "directions" with any other client):
cat usa.txt - | directions
The "-" argument for "cat" will read input from standard input after it with the file usa.txt, and you can type in the queries there. (If you don't know what "cat" does, type "man cat" on arizona.)
Extra credit. Create your own map file. If it's sufficiently interesting, we'll award extra credit and post them for other students to use. It can be of the US, Princeton, or any other recognizable region. For example, delete all roads in Nebraska from the US map (perhaps, for drivers who have an unpaid speeding ticket in the state).
|
|
Submit everything along with the client program distances.c. (Don't submit paths.c or plotit.c.) We'll jointly compile with "gcc *.c" and execute with "a.out < usa-5000.txt". We may also substitute a different client for distances.c, e.g., paths.c.
Here is a template readme.txt file. It should contain the following information:
Unix users may find the shell script timeit.csh useful for computing a table of CPU times.
|
|