[SOLVED] algorithm School of Computing and Information Systems

School of Computing and Information Systems
COMP90038 Algorithms and Complexity Tutorial Week 12

1519 October 2018

Plan
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. Floyds algorithm sometimes works even if we allow negative weights in a dag.

a b

4

-3

a b

3

-4

For example, for the left graph above, it will produce these successive distance matrices:

D0 = D1 = D2 =

[
0 4
3 0

]
What happens for the right graph above? What do D0, D1 and D2 look like? Explain why
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.

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. That is, find a set I S such that

iI w(i) W and so that

iI v(i) is

maximised.
Define the benefit of an item i to be the rational number v(i)/w(i). Consider the following
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
while k 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 Prims 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?

a b

c d e

f g

2

4 1 3 9

2 7

5 8 4 6

1

83. Use Dijkstras algorithm to find the shortest paths for node e in the previous questions 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 graphs minimum spanning tree?

84. Lemuel Gulliver wishes to compress the string allbigendiansandallsmallendians. 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:

a b d e g i l m n s
6 1 3 2 1 3 6 1 5 3 6

How many bits are required for the encoded string?