3805ICT Advanced Algorithms – Assignment 2 (100 Marks)
Note:
a) This assignment must be done individually.
b) The programming language to be used is C++ but you may use Python to generate
graphs for your reports.
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.
d) The submission time and date are as specified in the Course Profile and the
submission method will be communicated during semester.
QUESTION 1 [10 MARKS]
A very large number of random numbers are added to a list. Design and implement an efficient data
structure that will maintain a separate list of the k smallest numbers that are currently in the list.
Space efficiency must be O(k + n). How would you handle deletions? Perform an amortised analysis
of your data structure.
QUESTION 2 [10 MARKS]
A simple algorithm for maze generation is to start, apart from entry and exit points, with all walls present
and randomly knock down walls until the entry and exit points are connected. Write a C++ program to
implement this algorithm for an arbitrary sized maze – test with a 50 by 88 rectangular maze.
QUESTION 3 [10 MARKS]
Using C++ software obtained from the internet analyse and compare the performance of Red-Black
Trees and Van Emde Boas Trees using a large number of integers. This should be done for add, find,
delete and sequential access.
QUESTION 4 [20 MARKS]
The object of the Kevin Bacon Game is to link a movie actor to Kevin Bacon via shared movie roles.
The minimum number of links is an actor’s Bacon number. For instance, Tom Hanks has a Bacon
number of 1; he was in Apollo 13 with Kevin Bacon. Sally Fields has a Bacon number of 2, because
she was in Forrest Gump with Tom Hanks, who was in Apollo 13 with Kevin Bacon. Almost all wellknown
actors have a Bacon number of 1 or 2. Given a list of actors, with roles, write a C++ program
that does the following:
(a) Finds an actor’s Bacon number.
(b) Finds the actor with the highest Bacon number.
(c) Finds the minimum number of links between two arbitrary actors.
QUESTION 5 [50 MARKS]
Design an algorithm and write a program to identify the minimum vertex covers within the complement
graphs of the supplied graphs. The table below shows the output from a current minimum vertex cover
solver for these complement graphs.
(a) You must actually design your own algorithm and write all program code submitted. The
program must be able to be run from the command line passing the target minimum vertex
cover size as an argument. The naming convention for your program file is
_mvc (without the <>) and try and keep the program within a single file.
2
(b) As this a computationally intensive algorithm, you must use C/C++, written using all possible
optimisations.
(c) You must produce a detailed Latex/Word paper containing an Introduction, Literature Review,
Algorithm Description, Experimental Results and Comparisons and a Conclusion.
(d) You must produce a Power-point presentation summarising your algorithms, implementation,
testing and the results of the problem and performance analysis. Do not include any code in
your powerpoint presentation.
Graph Minimum Vertex Cover Successful Trials Average CPU Time
brock800_1 777 86 84.54
brock800_2 776 98 74.90
brock800_3 775 100 45.30
brock800_4 774 100 26.75
c2000.9 1,922 1 36.28
c4000.5 3,982 100 142.02
MANN_a45 691 100 88.76
p_hat1500-1 1,488 100 1.39