# 程序代写代做代考 algorithm School of Computing and Information Systems

School of Computing and Information Systems

COMP90038 Algorithms and Complexity Tutorial Week 12

15–19 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. Floyd’s 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

∑

i∈I w(i) ≤ W and so that

∑

i∈I 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 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?

a b

c d e

f g

2

4 1 3 9

2 7

5 8 4 6

1

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:

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?