Note:
a) This assignment must be done individually.
c) For each question requiring a C++ program you must document the algorithm and show any test cases you used. Only submit a single Word document containing the documentation for all questions.
• Is vertex v connected to vertex u?
• Produce a list of all vertices connected to v.
However, the advent of very large graphs (> 50,000,000 vertices and > 100,000,00) prevents the memory storage of the adjacency matrix and standard adjacency lists for these graphs. Design and implement in C++ a data structure for storing such graphs that is able to effectively perform the 2 operations listed above. Demonstrate the efficiency of your data structure.
a. Can store integers in the range 0 .. n where n is some upper bound.
b. Duplicate integers are not allowed in the list.
c. Is O(1) for add, delete, test for being in the list and iterating through the list.
1
d. Is O(k) (where k is the number of integers in the list) for clearing the list.
Results for C++ Implementation
Word Num. Seq. CPU CPU Word Num. Seq. CPU CPU
Length Words Length Found Total Length Words Length Found Total
4 3,862 92 0.02 0.20
5 8,548 3,122 65.46 70.75
6 14,383 5,436 61.80 200.20
7 21,730 8,398 233.15 384.28
8 26,447 10,304 422.09 548.45 9 18,844 5,223 204.81 265.65 10 12,308 2,412 95.46 112.55
11 7,850 1,578 41.24 41.55
12 5,194 917 13.28 16.38
13 3,275 503 0.88 5.26
14 1,775 253 1.35 1.40
15 954 98 0.20 0.30
Analyse in detail the problem and the performance of each of your algorithms. You must produce a detailed Latex/Word paper containing an Introduction, Algorithm Description, Experimental Results and Comparisons and a Conclusion.
2
