Due September 26 at 2 PM.
You will be writing three main programs for this assignment.
For each part you will hand in a copy of your source code and
the output generated by your program.
All source code should be printed 2-up using prtext.
For the last part you will also be handing in some graphs.
All pages should be numbered
consecutively and stapled or securely clipped together as a single unit.
The cover page should be a printed copy of the postscript file
/usr/local/courses/cs3343/fall96/assign1/cover1.ps
Fill in your name and the index entries so I can easily find
the parts of your assignment. Check the appropriate box for each
part of the assignment. If a part did not work perfectly, explain what
progress you made in completing it.
Each main program should start by printing a line in the form
This program was written by ...
All output from your programs should go to standard output.
You can create files for printing out and handing in by redirecting
the output of your programs.
A makefile for compiling all parts of this project can be found in
/usr/local/courses/cs3343/fall96/assign1
Write a C function:
double shortest_path(int n, double *C, double D[], int P[])
You pass the size, n, and the adjacency matrix, C.
C is an n by n matrix.
Since you cannot use 2-dimensional arrays
whose size is not known at compile time you will have to do the
indexing into the array yourself. The one-dimensional index of the entry
at row i and column j is i*n+j.
C, D, and P are allocated by the
calling program.
Assume that the nodes are
labeled 0 to n-1 and you are to find the shortest paths starting from node 0.
The function fills in the D array with the lengths of the shortest path
and the P array with the predecessor of each node along the shortest path.
The predecessor of node 0 should be -1. The function returns the running time
in seconds calculated using gethrtime. The function (after it is debugged)
should not do any I/O. Put the function in a file called
shortest_path.c
Write a main program called shorttest1 which reads in n and then C (in row-major order) from standard input, calls shortest_path, and prints out the time and the shortest path for each node (a sequence of nodes) with its length.
Devise input to test your program. Start by using the example from the text and make sure you get the correct answer. Make up additional test data to convince yourself that the program is working correctly.
Write a second main program called shorttest2 which calls the function
double *generate_test(int n)
You pass to this function a positive integer which represents the size
of a square 2-dimensional array and it returns a 2-dimensional array
filled with doubles. You will use this as the adjacency matrix for
you shortest_path function.
The function generate_test will be provided for you in the file
/usr/local/courses/cs3343/fall96/assign1/dijkstra_test.o.
Your main program will call generate_test(100) and then your
shortest_path
function with the adjacency matrix generated. Print out the time and the
shortest path as in Part I. Then call the function
void verify_shortest_path(int n, double *C, double D[], int P[])
with the same value of n and C and the D and
P calculated by your
shortest_path function.
This function is also in the dijkstra_test object
file and will generate some output which will tell
me if your program is working correctly.
Write a function
void generate_adjacency(int n, double *C, double max)
which fills the n by n matrix C with
uniformly distributed random numbers
in the range from 0 to max.
Put this in a file called generate_adjacency.c.
Use drand48 to generate the random numbers.
Write a main program called shorttest3 which uses this function and your shortest_path function form Part I to print out a table with 2 columns, one with the value of n, and the other the time in microseconds divided by n squared. Use values of n starting with 2 and doubling for each iteration. Go as far as you can without using more than a few minutes of CPU time. Your main program will allocate space for C, D and P in each iteration and free C, D, and P before the start of the next iteration. It should print out an error message and terminate if the allocation fails.
Run this on one of the clients of the network. Most of these have 32 Meg of memory. Record the name of the machine on which the tests were run. You will get the best results when you are the only user. Do not run it on any of the servers, ringer, pandora, or medusa.
Now change the OPS in the makefile from -g to -O. Do a make clean and the compile again. Rerun shorttest3 on the same machine.
Make a third run on the same machine with OPS set to -xO4.
Draw graphs of the time in microseconds divided by n squared verses the value of n for your three runs. If your graphs are not close to a straight lines, explain why.