(Fall Semester 2002)

LEDA Assignment 1: Hello, LEDA!

(Due: 26 September 2002)

(Updated: 5-Sept, changed in
RED)

In part (a), your task is to compile and run a given LEDA program that implements Dijkstra's algorithm for computing shortest path in a graph. The purpose of this excercise is to give you a feel of how your choice of data structures may affect the performances of Dijkstra's algorithm. No coding is involved, unless you choose to do so on your own accord.

In part (b), you are required to complete an "almost completed" LEDA program. This is to give you some hands-on LEDA programming, as well as to demonstrate how algorithms can be quickly prototyped by using LEDA.

All the files needed for this assignment can be found in this archive.

In this assignment, you are given a LEDA program
`LEDAdijkstra.cc`
(also an automated version,
`LEDAdijkstra2.cc`)
that contains different
implementations of Dijkstra's algorithm for shortest path in a
graph. In particular, this program will first create a random
directed weighted graph G, and then call the LEDA default
Dijkstra's algorithm to solve the one-to-all shortest path problem G.
Following that, it allows the user to choose a different
implementation of Dijkstra's algorithm among
seven implementations --
` 0:f_heap 1:k_heap 2:m_heap 3:list_pq
4:p_heap 5:r_heap 6:bin_heap.`

Compile LEDAdijkstra (`make LEDAdijkstra`)
and run it a few times to get familiar with the interface
of the program.
After you get a hang of it, compile the automated version of this
program (`make LEDAdijkstra2`) for your performance evaluation.
Besides being non-interactive, the
automated version also generates 100 graphs so that an averaged value
for each data structure can be obtained.

Your first job is to compare the performance of Dijkstra's algorithm on graph of different sizes -- n=2000, 4000, 8000, 16000, 32000. For each n, run it on different edge sparsity, i.e., for m=5n, 10n, 15n, 20n (for all your problems, you can use the same max-edge-cost=30000). Plot out the graphs of running time against the different graph sizes.

Write a brief report on your comparisons and observations. Submit your comparison graphs together with your report (you don't have to include the data tables in the report).

You are provided with an "almost completed" program, dna.cc. You should:

- Complete the program. If you are careful, you will find that you only need to add a few lines.
- Find (all) the most repeated patterns of length 8 in
this file.

- Submit the results together with your completed program.

Optional:

Analyse the order of runtime of your program. You can assume that each call to
`_get_next_string()` takes O(seglen) time.

LEDA provides many implementations of priority queues. The
implementations include Fibonacci heaps (f_heap), pairing heaps (p_heap),
k-nary heaps (k_heap) and binary heaps (bin_heap), redistributive heaps
(r_heap), lists (list_pq) and buckets (b_heap) [**See Note**],
and monotone heaps (m_heap). Fibonacci heaps are the default implementation
and other implementations acan be selected using the implementation
parameter mechanism. Following is a list of related biography

- [Fibonacci heap] M. L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34:596-615, 1987.
- [pairing heaps] J.S. Vitter J.T. stasko. Pairing heaps: Experiments and analysis. Communications of the ACM, 30:234-249, 1987.
- [k-nary and binary heaps] K. Mehlhorn. DataStructures and Algorithms 1: Sorting and Searching. III.5.3.1. Springer Verlag, 1984.
- [redisributive heaps] R. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan. Faster algorithms for the shortest path problem. JACM, 3(2):213-223, 1990.
- [monotone heaps] K. Mehlhorn. DataStructures and Algorithms 2: Graph Algorithms and NP-Completeness. IV.7.2 Springer Verlag, 1984.

**Note: ** In the list implementation the items of the
queue are stored as an unordered list. This makes *delete_min* and
*find_min* linear time process (linear serach through the entire
list) and trivalizes all other operations. In the bucket implementation
we have an array of linear lists; the list with index *i* contains
all items whose priority is equal to *i*. This scheme requires the
priorities to be integers from a prespecified range.

LEDA Assignment 1