CS代考程序代写 AI algorithm CONFIDENTIAL EXAM PAPER
CONFIDENTIAL EXAM PAPER
This paper is not to be removed from the exam venue Information Technologies
EXAMINATION
Semester 1 – Main, 2019
COMP3027/COMP3927 Algorithm Design EXAM WRITING TIME: 2.5 hours
READING TIME: 10 minutes EXAM CONDITIONS:
This is a CLOSED book examination – no material permitted During reading time – writing is not permitted at all
MATERIALS PERMITTED IN THE EXAM VENUE:
(No electronic aids are permitted e.g. laptops, phones)
None
MATERIALS TO BE SUPPLIED TO STUDENTS:
None
INSTRUCTIONS TO STUDENTS:
The paper comprises 18 pages. Space is provided for your answers. If you need more space use the blank pages at the end of the paper.
This exam contains 7 questions.
Students enrolled in COMP3027 should answer problems 1-6 (six questions). Students enrolled in COMP3927 should answer problems 1-5 and 7 (six questions).
Please tick the box to confirm that your examination paper is complete.
For Examiner Use Only
Room Number
Seat Number
Student Number
ANONYMOUSLY MARKED
(Please do not write your name on this exam paper)
________
________ |__|__|__|__|__|__|__|__|__|
Q
Mark
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Page 1 of 18
Total ________
DO NOT WRITE ABOVE THIS LINE
Problem 1 [18 marks]
Consider the following edge weighted undirected graph G:
bc
9742
agf
6135
d
e
Your task is to compute the minimum weight spanning tree T of G using Prim’s algorithm starting at a:
(a) [9 marks] Draw the edges of T in the space provided below.
(b) [9 marks] Indicate the order in which the algorithm adds these edges to the solution.
bc
agf
Other potential questions:
d
e
Draw a minimum spanning tree (MST) of G using Kruskal’s algorithm. Label each node to indicate the order in which they were added to the MST.
Run Dijkstra’s Algorithm on G starting from node a, to calculate the length of the shortest path between a and each other node. Write down the order in which each vertex was extracted from the priority queue.
Page 2 of 18
DO NOT WRITE ABOVE THIS LINE
Problem 2 [18 marks]
Consider the network flow instance (G, c) on the left and s-t flow f on the right.
ab ab
30
3130
s51ts30t
4303
63
cd cd c : E → Z+ (edge capacities) f : E → Z+ (current flow)
(a) [6 marks] What is the value of this flow?
(b) [6 marks] Is this a maximum s−t flow in this graph? If not, find a maximum s−t flow.
(c) [6 marks] Find a minimum s − t cut. (Specify which vertices belong to the sets of the cut.)
Other potential questions:
Draw the residual graph with respect to this flow. Find an augmenting path in the residual graph. Draw the updated flow.
Page 3 of 18
DO NOT WRITE ABOVE THIS LINE
Problem 3 [18 marks]
Given an array A holding n objects, a majority element is an object that appears in more than n/2 positions of A. Assume we can test equality of two objects in O(1) time, but we cannot use a dictionary indexed by the objects. Your task is to design an O(n log n) time algorithm for determining if there is a majority element.
(a) [6 marks] Describe your algorithm in plain English. (b) [6 marks] Justify the correctness of your algorithm.
(c) [6 marks] Analyse the time complexity of your algorithm.
Page 4 of 18
DO NOT WRITE ABOVE THIS LINE
(solution to Problem 3 continues here)
Page 5 of 18
DO NOT WRITE ABOVE THIS LINE
Problem 4 [18 marks]
Consider the problem of finding change using as few coins as possible. Formally, we are given as input a non-negative integer n, and we have unlimited quantities of 3 types of coins: 1c, 2c, 5c. The goal is to determine the minimum number of coins that add up to nc.
Your task is to design an O(n) time algorithm for solving this problem using dynamic programming:
(a) [6 marks] Clearly define your DP states (subproblems).
(b) [6 marks] State and justify the recurrence (base and recursive cases).
(c) [6 marks] Analyze the time complexity of your algorithm.
Page 6 of 18
DO NOT WRITE ABOVE THIS LINE
(solution to Problem 4 continues here)
Page 7 of 18
DO NOT WRITE ABOVE THIS LINE
Problem 5 [18 marks]
Consider the 3-partition problem. Given integers a1, . . . , an, we want to determine whether it is possible to partition {1,…,n} into three disjoint sets I, J and K such that
1n
i∈I
Your task is to show that 3-partition is NP-complete:
ai =
aj = ak = 3 ai. k∈K l=1
j∈J
(a) [6 marks] Show that 3-partition belongs to the class NP.
(b) [12 marks] Prove that 3-partition is NP-hard by showing that the subset-sum prob- lem can be reduced in polynomial time to 3-partition; that is, prove that
subset-sum≤P 3-partition.
Page 8 of 18
DO NOT WRITE ABOVE THIS LINE
(solution to Problem 5 continues here)
Page 9 of 18
DO NOT WRITE ABOVE THIS LINE
Problem 6 [10 marks]
[COMP3027 only] Hard problem for COMP3027 only.
(a) [4 marks] Describe your algorithm in plain English. (b) [3 marks] Justify the correctness of your algorithm.
(c) [3 marks] Analyse the time complexity of your algorithm.
Page 10 of 18
DO NOT WRITE ABOVE THIS LINE
(solution to Problem 6 continues here)
Page 11 of 18
DO NOT WRITE ABOVE THIS LINE
Problem 7 [10 marks]
[COMP3927 only] Hard problem for COMP3927 only.
(a) [4 marks] Describe your algorithm in plain English. (b) [3 marks] Justify the correctness of your algorithm.
(c) [3 marks] Analyse the time complexity of your algorithm.
Page 12 of 18
DO NOT WRITE ABOVE THIS LINE
(solution to Problem 7 continues here)
Page 13 of 18
DO NOT WRITE ABOVE THIS LINE
–THIS PAGE IS INTENTIONALLY LEFT BLANK– —END OF EXAMINATION—
Page 14 of 18
DO NOT WRITE ABOVE THIS LINE
EXTRA PAGE FOR ROUGH WORK ANYTHING ON THIS PAGE WILL NOT BE MARKED
Page 15 of 18
DO NOT WRITE ABOVE THIS LINE
EXTRA PAGE FOR ROUGH WORK ANYTHING ON THIS PAGE WILL NOT BE MARKED
Page 16 of 18
DO NOT WRITE ABOVE THIS LINE
EXTRA PAGE FOR ROUGH WORK ANYTHING ON THIS PAGE WILL NOT BE MARKED
Page 17 of 18
DO NOT WRITE ABOVE THIS LINE
EXTRA PAGE FOR ROUGH WORK ANYTHING ON THIS PAGE WILL NOT BE MARKED
Page 18 of 18
