## Transcribed Text

1. (10%) Explain whether each of the following statements is true or false.
(a) In the Bellman-Ford algorithm, if there are no changes to the table of distance
valuesafter a particular iteration of the outer i for-loop, then we can stop the algorithm
immediately and skip the remaining iterations.
(b) In the Floyd-Warshall algorithm, if there are no changes to the values of
distancematrices after a particular iteration of the outermost k for-loop (i.e. the two
matrices D(k−1) and D(k) are identical for some k), then we can stop the algorithm
immediately and skip the remaining iterations.
2. (15%) Consider the London Underground (Tube) network where there are several lines
and many stations. You are given the travel time between adjacent stations on any line.
Some stations are interchange stations between different lines, and the change incurs extra
time which is dependent on the specific station, the specific lines being changed from/to
and also the direction of travel. For example, there is a particular changing time at King’s
Cross St. Pancras station between the Piccadilly line westbound platform and the Victoria
line southbound platform. You are also given all these changing times. All these travel and
changing times are undirectional, i.e. the time from u to v is the same as the time from v to
u. As sometimes there are more than one way to travel between two stations, we want to
find the shortest time needed to travel between two given stations. Ignore waiting times
(assume they are somehow factored into the travel times or changing times).
Describe how this can be modelled as a graph problem and how this can be solved
efficiently.
(Hint: Model the changing times by ‘expanding’ a station into many vertices and add extra
edges between them.)
3. (30%) Consider the subset sum problem, where you are given a set S of n integers {x1,x2,...,xn}
and a target sum T (a positive integer). Your task is to determine whether it is possible to
find a subset of S so that their sum is exactly T. For example, if S = {4,7,10,12,15} and T = 20,
then the answer is no, but if T = 19 then the answer is yes (either 4+15 or 7+12).
(a) Consider the following greedy algorithm. Select the largest number not exceedingour
target T, and subtract this number from T to obtain a new target. Then repeat the
procedure on this smaller target using the remaining set of numbers, until either a
target of 0 is reached (in which case the answer is yes) or no numbers can be chosen
(in which case the answer is no).
Give a counterexample to show that the algorithm does not always return the correct
answer.
1
(b) Let F(i,t) denote whether it is possible (true or false) to find a sum of exactly t from the
first i numbers x1,...,xi. Our problem becomes finding F(n,T).
Give a recursive formula for F(i,t). Also, write down the base case. (Note that since F()
records either true or false, your formula will need to use logical operators like AND,
OR rather than the usual +, max, min etc.)
(c) Hence, give a dynamic programming algorithm for solving the subset sum
problem.Your algorithm should run in O(nT) time.
(d) Illustrate how your algorithm works by solving the problem with S = {2,3,4,5},
T = 5. It is sufficient to show the final contents of the dynamic programming table.
4. (25%) You are going on a long road trip with starting point H0 and destination Hn. Along the
road there are n − 1 hotels H1,H2,...,Hn−1 where you can potentially stop and stay overnight.
You can only stop at these hotels, and you must stop at Hn (your destination). The distance
between H0 and Hi along the road is di miles.
Ideally you would like to drive 300 miles per day; but this may not be possible due to the
distances between the hotels. If you drive x miles in a day, the penalty that you incur for that
day is (300 − x)
2. You cannot drive more than 600 miles a day. You want to decide which
hotel(s) to stop at so that the total penalty over all travel days is minimised. Assume a
feasible solution exists, i.e., any two hotels are at most 600 miles apart on the road.
(a) Let P(i) denote the total penalty of the optimal solution travelling from H0 and finishing
(stopping) at Hi. Give a recursive formula for P(i). (Hint: consider all the possible
locations for the last stop before Hi.)
(b) Give an efficient algorithm for this problem. Analyse the time and space complexityof
your algorithm.
5. (20%) Given a flow network, an edge is called a bottleneck edge if increasing its capacity
increases the maximum flow of the network. An edge is called a critical edge if decreasing
its capacity decreases the maximum flow of the network.
(a) Give an example of a flow network such that there is a critical edge that is not
abottleneck edge.
(b) Show that any bottleneck edge of any flow network must also be a critical edge.(Hint:
consider the residual network of the maximum flow. If (u,v) is a bottleneck edge, then
there must be a path with residual capacities from s to u, and from v to t, but (u,v) itself
has no residual capacity (why?). Then recall how a min cut can be found.)

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.

Problem 1

a). The claim is TRUE and leads to a more efficient implementation of the Bellman-Ford algorithm (for both running time and space complexity). Compared to the algorithm presented in class it is required to be operated some minor modifications (given below). Instead of one two-dimensional array can be used two one-dimensional arrays, namely d[v] holding the cost of the cheapest v -> t path found so far and successor [v] holding the next node from a v->t path. In this case the pseudo-code will be:

Bellman-Ford (G(V,E), dist, t)

For all nodes v from V do

d[v]=+∞, successor[v]= NULL

d[t]=0;

for i=1 to n-1 do

for each node w from V do

if d[w] was updated during the previous outer loop iteration then

for all edges (v,w) from E do

if (d[v] > d[w]+ dist(v,u)) then

d[v]=d[w]+dist(v,u)

successor[v]=w

if all d[w] have the same values as in the previous iteration, then Stop execution...