Transcribed TextTranscribed 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.)

Solution PreviewSolution Preview

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

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
if all d[w] have the same values as in the previous iteration, then Stop execution...

By purchasing this solution you'll be able to access the following files:

for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats