Priority Queue Tests -- Random Problems

Here's what you have to do to run the Random problems for Priority Queue tests in DIMACS Challenge 5. This implementation is by Ben Chang, with modifications by C. McGeoch.

Send Cathy a note if you have questions or need help.

• Get the compressed tar file.

• Unbundle and compile:

     uncompress pq_random.tar     (if your browser hasn't already)
     tar -xf pq_random.tar
     cd pq_random 
     gcc pq.c dimacs_input.c PQ_Random.c -o pqrandom
     sort_tests
     

• Typing sort_tests will cause 9 priority queue trace files to appear in the directory. These represent 3 random trials at each of 3 problem sizes (1K, 10K, 100K).

  For problem size N, the program generates N inserts of random priorities, followed by N delete-mins. The priorities are random integers from [0..N-1], each with a decimal timestamp added (from reals in (0,1)) to ensure unique priorities.

  When the pqsort. trace files are ready, give them to your test driver to perform the priority queue tests.

• Typing dcr_tests will cause another 27 priority queue trace files to appear in the directory. These represent 3 random trials at each of 9 problem sizes. (N=1K, 10K, 100K and M= N, 2N, 4N). For problem size (N,M), the program generates N initial inserts, followed by M repetitions of dcr. To do a decrease-key, the program selects a random item in the priority queue. Let P be the priority of that item, and let R be the priority of the root (the integer parts). The new integer priority for the item is uniformly selected from the range [R,P].

  When the pq.dcr trace files are ready, give them to your test driver to perform the priority queue tests.

• Now type id_tests to get 27 more trace files. These represent 3 random trials at each of 9 problem sizes (same as above). The program generates N initial inserts, followed by M repetitions of the pair [ins dmn], totaling N+2M operations.

  When the pq.id. trace files are ready, give them to your test driver to perform the priority queue tests.

Back to the Challenge.

Back to the Priority Queue Tests.