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.
- (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 thatthe 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.
- (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).
00:00 London
00:00 Madrid
00:00 Rome
07:00
09:00
09:30
11:00
11:00
10:30
11:00
23:59
23:59
23:59
08:30
12:30 13: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.