代写3805ICT、代写C++编程语言

日期：2022-06-01 09:45

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

<student_number>_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