Implement one of the following problems in a programming language that is available on CoC machines.
This algorithm will be presented in class. Report the running time of your algorithm on the instances that will be provided.
Use two different ways of implementing the union/find operations, for example linked lists with the weighted-union heuristic (Sec. 22.2) and rooted trees with union-by-rank and path compression (Sec 22.3). Compare the running time of the two implementations.
Use two different ways of implementing the priority queue, for example binary heaps (Sec. 7.1) and unsorted arrays. Compare the running time of the two implementations.
Use two different ways of implementing the priority queue, for example binary heaps (Sec. 7.1) and unsorted arrays. Compare the running time of the two implementations.
Sample graphs will be posted on the web page in a self-explanatory format; you should write your own routine that reads the graphs and converts them into your internal representation. Internally, graphs should be represented with adjacency lists; the adjacency-matrix representation will not be able to handle some of the large instances that will be provided (see Sec. 23.1 for a discussion of the two representations).
You should run your program on each graph instance and report the running time. Please take care to exclude the time spent for input and output, report only the time spent by the actual algorithm. This means that your language should provide some mechanism of accessing the system time. If you use C under Unix you may use either gettimeofday or the set of routines that will be provided on the web page (based on interval timers). The use of these routines is recommended since they report user time, not only absolute time, making the results less dependent on the machine load.
The programming project is due on Friday, August 28. Turn in your source code (in electronic format) and a one page report describing your work and the timing results. Grading will be based on correctness (80%), programming style (15%), and quality of the report (5%).