Plan
School of Computing and Information Systems COMP90038 Algorithms and Complexity Tutorial Week 12
15–19 October 2018
Sadly this is the last tutorial session; but at least there is still the exam to look forward to. You will find a list of examinable topics on the LMS, under “exam information”. We have also made the cover page of the 2018 semester 2 exam paper available, for a sneak preview.
The exercises
79. Floyd’s algorithm sometimes works even if we allow negative weights in a dag.
43
ab ab
-3 -4
For example, for the left graph above, it will produce these successive distance matrices:
[]
D2 ends up giving an incorrect result in this case (but not in the previous case).
80. We are given a sequence of “connection points” spaced out evenly along a straight line. There
are n white, and n black points, in some (random) order.
The points are spaced out evenly, so that the distance between two adjacent points is 1.
The points need to be connected, so that each white point is connected to exactly one black point and vice versa. However, the total length of wire used must be kept as small as possible.
Consider the following (greedy) algorithm to solve the problem:
k←1
while there are still unconnected points do
create all possible connections of length k k←k+1
Argue the correctness of this algorithm, or, alternatively, devise an example that proves that it may not produce an optimal wiring.
D0 = D1 = D2 =
What happens for the right graph above? What do D0, D1 and D2 look like? Explain why
04 −3 0
81. Recall the definition of the knapsack problem. Given a set of items S = {i1, i2, . . . in} with • weights: w(i1),w(i2),…,w(in)
• values: v(i1),v(i2),…,v(in)
and a knapsack of capacity W, find the most valuable selection of items that will fit in the
knapsack. Thatis,findasetI⊆Ssuchthat∑ w(i)≤Wandsothat∑ v(i)is
i∈I i∈I
Define the benefit of an item i to be the rational number v(i)/w(i). Consider the following
maximised.
greedy approach to the problem:
Let A[1]…A[n] hold the items from S, in decreasing order of benefit val ← 0
weight ← 0
k←1
whilek≤n∧weight+w(A[k])≤W do select A[k]
val ← val + v(A[k])
weight ← weight + w(A[k]) k←k+1
That is, at each step, from the remaining items we simply pick the one that has the greatest benefit. Give a simple example to show that this greedy algorithm does not solve the knapsack problem.
82. Work through Prim’s algorithm for the graph below. Assume the algorithm starts by selecting node a. Which edges are selected for the minimum spanning tree, and in which order?
2
a
b
4139 c2d7e
5846
g
83. Use Dijkstra’s algorithm to find the shortest paths for node e in the previous question’s graph. That is, run the algorithm to determine the length of the shortest path from e to v, for all seven nodes v. Is the shortest path from e to b part of the graph’s minimum spanning tree?
84. Lemuel Gulliver wishes to compress the string “all␣big␣endians␣and␣all␣small␣endians”. Help him by building a Huffman tree for the string (there may be several valid trees) and assign a binary code accordingly, to each of the eleven characters involved (we have used ␣ to make each space character visible). The frequencies are:
abdegilmns␣ 61321361536
f
1
How many bits are required for the encoded string?