算法代写 | COMP3027 Algorithm Design

这个作业是完成图、矩阵相关的算法测试题
COMP3027 Algorithm Design
(Please do not write your name on this exam paper)
Problem 1 [10 marks]
Consider the following edge weighted undirected graph G:
a
b c
d
e
g f
9
6
7
1
4 2
3 5
Your task is to compute the minimum weight spanning tree T of G using Prim’s
algorithm starting at a:
(a) State the edges of T, in the order that the algorithm adds them to the solution.
Other potential questions:
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
Page 2 of 8
Problem 2 [10 marks]
Consider the network flow instance (G, c) on the left and s-t flow f on the right.
s
a
c
b
d
t
3
4
5
6
3
1
3
1
c : E → Z
+ (edge capacities)
s
a
c
b
d
t
3
0
3
3
0
0
3
0
f : E → Z
+ (current flow)
(a) What is the value of this flow?
(b) Is this a maximum s − t flow in this graph? If not, find a maximum s − t flow.
(c) 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 8
Problem 3 [10 marks]
The product of two n × n matrices X and Y is a third n × n matrix Z = XY , where the
(i, j) entry of Z is Zij =
Pn
k=1 XikYkj . This definition immediately leads to an O(n
3
)
time algorithm for matrix multiplication. Here we explore the option of designing an
alternative algorithm using divide and conquer. Suppose that X and Y are divided into
four n/2 × n/2 blocks each:
X =

A B
C D 
and Y =

E F
G H 
.
Using this block notation we can express the product of X and Y as follows
XY =

AE + BG AF + BH
CE + DG CF + DH 
.
In this way, one multiplication of n×n matrices can be expressed in terms of 8 multiplications and 4 additions that involve n/2×n/2 matrices. It is straightforward to translate
this insight into a divide and conquer algorithm for matrix multiplication; unfortunately,
this new algorithm’s time complexity is again O(n
3
).
Suppose that instead of 8 recursive multiplications of n/2 × n/2 matrices, we could
compute the product using only 7 such matrix multiplications and a constant number of
matrix addition operations. Let T(n) be the time complexity of multiplying two n × n
matrices using this improved recursive algorithm. Your task is to
(a) Derive the recurrence for T(n). (Assume that adding two k×k matrices takes O(k
2
)
time.)
(b) Solve the recurrence by unrolling it.
Other potential questions: Provide a counter-example which shows that a given algorithm does not produce a correct solution.
Page 4 of 8
Problem 4 [20 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) Describe your algorithm in plain English.
(b) Justify the correctness of your algorithm.
(c) Analyse the time complexity of your algorithm.
Page 5 of 8
Problem 5 [20 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) Clearly define the DP subproblems.
(b) State and justify the recurrence and base cases.
(c) Analyze its time complexity.
Page 6 of 8
Problem 6 [20 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
X
i∈I
ai =
X
j∈J
aj =
X
k∈K
ak =
1
3
Xn
`=1
ai
.
Your task is to show that 3-partition is NP-complete:
(a) Show that 3-partition belongs to the class NP.
(b) Prove that 3-partition is NP-hard by showing that the subset-sum problem can be
reduced in polynomial time to 3-partition; that is, prove that
subset-sum ≤P 3-partition.
Page 7 of 8