CO3002/7002 Assignment 2
Released Mar 6, 2018 Deadline Mar 28, 2018 5:00 pm
Submit your solutions to the convenor directly during classes, or to his office (F6, Informatics building).
Your submission must also include a completed “Cover sheet for individual coursework” available from
the module webpage. Please observe further instructions on the module webpage concerning anonymous
marking.
1. (20%) Consider an undirected connected graph G with positive edge weights. Suppose T
is a minimum spanning tree of G, and P is a shortest path between two given vertices
s and t in G. Two new graphs are constructed from G by changing the edge weights
(keeping the same set of vertices and edges) as follows:
G1: replace the weight w(e) of each edge e by M + w(e)
G2: replace the weight w(e) of each edge e by M − w(e)
Here M is a constant larger than any edge weight in G, so that all new edge weights are
positive. Two of the following statements are false. Identify which two are false, and give
a counterexample to each of them. (For a 5% bonus mark, give a formal correctness proof
for the two true statements.)
(i) T must be a minimum spanning tree of G1.
(ii) T must be a maximum spanning tree (i.e., a tree connecting all vertices such that
the total edge weight is as large as possible) of G2.
(iii) P must be a shortest path between s and t in G1.
(iv) P must be a longest path between s and t in G2.
2. (20%) Consider a directed graph that models flights between cities. An example with
three cities and five flights is shown below. Each city has a horizontal ‘line’ of vertices
and edges: a vertex whenever there is an arriving/departing flight (and two special 00:00
and 23:59 vertices), and edges (called timeline edges) joining successive vertices in the
timeline. A flight is represented by an edge (called flight edge) joining the departure
city/time vertex to the arrival city/time vertex. All times are in GMT. Assume we are
only interested in a 24-hour period from 00:00 to 23:59. Assume connecting flights are
possible as long as the second flight departs after the first flight arrives (i.e., no minimum
connection time is required).
07:00
08:30
11:0009:00
10:30
11:00
12:30 13:00
09:30
11:00
23:59
23:59
23:59
00:00
London
00:00
Madrid
Rome
00:00
We want to find the ‘best’ way of travel from a given source city to a given destination
city (possibly requiring connecting flights). For each of the following meanings of ‘best’,
explain how the problem can be solved by assigning suitable edge weights to the graph
and solving a suitable shortest path problem. The first one is done for you as an example.
(Earliest arrival time) We want to arrive at the destination as early as possible. In the
given example, from London to Rome, we would choose the flights (London 07:00,
Madrid 08:30) connecting to (Madrid 09:30, Rome 11:00).
Solution: For timeline edges of the destination, assign a weight of 0. For all other
edges, assign a weight equal to the time difference between the two endpoints. Then
find the shortest path from (source, 00:00) to (destination, 23:59).
(Shortest travel time) We want to spend the minimum amount of time between de-
parture at source city and arrival at destination city.
(Shortest transit time) We want to spend the minimum amount of time waiting be-
tween connecting flights. (The transit time of a direct flight is 0.)
(Fewest connections) We want to make the fewest number of connections.
3. (25%) You have some amount of money to be invested over an n-year period. In the
beginning of the i-th year, there are two investment options: (1) shares in the stock
market, which give a return rate of si; (2) government bonds, which give a return rate
of bi. The return rate is defined as: if an amount of D is invested for a year at a rate
of r, then at the end of the year the amount becomes Dr (so r > 1 represents a gain
and r < 1 represents a loss; r is always positive). The full amount must be invested in
one of the options (i.e., not split between them). At the end of each year we may change
the investment option for the following year. If we change the investment (from bonds to
shares or vice versa), there is a fixed fee of f ; if we do not change there is no fee. The full
amount (including returns and after fees) are always reinvested. For example, if n = 4
and we decide to invest in bonds in years 1 and 4, and shares in years 2 and 3, then with
an initial amount of 1, the final amount is (((b1 − f)× s2 × s3)− f)× b4.
Assume f and all the return rates b1, . . . , bn and s1, . . . , sn are known. Our objective is to
find the investment strategy (i.e., whether to invest in bonds or shares in any given year)
that results in the greatest amount at the end of the n-year period.
(a) Let B(i) be the optimal amount at the end of the i-th year (after return during
the i-th year is accrued but before any fees for switching in the next year) if the
investment of the i-th year is in bonds; similarly let S(i) be the corresponding value
but if the investment of the i-th year is in shares. Give a formula that expresses B(i)
in terms of B(i− 1) and S(i− 1). Give a similar formula for S(i).
(b) Give an efficient algorithm for finding the amount obtained by the optimal strategy
at the end of n years. Analyse the time and space complexity of your algorithm.
4. (35%) The following is an alternative dynamic programming formulation of the coin chang-
ing problem (Exercise 9-5 in the lecture notes). Recall that we want to make an exact
amount of n using the minimum number of coins from a set of k coin denominations
c1, c2, . . . , ck, where 1 = c1 < c2 < · · · < ck.
(a) Let N(i) denote the minimum number of coins required to make an exact amount of
i. Give a recursive formula for N(i). Hence give a dynamic programming algorithm
for the problem. (Hint: there are (at most) k choices for the first coin. Once a coin
is chosen, the problem is reduced to a smaller subproblem.)
(b) Analyse the time and space complexity of the algorithm, in terms of n and k.
(c) Illustrate how your algorithm works with n = 6 and coin denominations {1, 3, 4}.
Show the contents of the dynamic programming table.