# 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