[SOLVED] CS algorithm Kings College London

Kings College London
This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
Degree Programmes
Module Code Module Title Examination Period
BSc, MSci, BEng, MEng
6CCS3OME Optimisation Methods May 2019
Time Allowed Rubric
Two hours
Answer all questions 18 and 13-14. Answer either ques- tions 910, or questions 1112.
If both questions 910 and 1112 are attempted, only 9 10 will be marked. Questions not to be marked must be struck through with a line on the answer sheet.
The multiple-choice questions have ONE or MORE cor- rect choices. In order to obtain full marks you must select all correct choices and only those.
Marks will be deducted for incorrect choices se- lected in those questions.
Questions 18 each carry FIVE marks. Questions 914 each carry FIFTEEN marks.
The answers to questions 112 need to be clearly made by pen on the appropriate grid on the answer sheet provided at the back of the exam paper. The answers to questions 1314 need to be written by pen on the separate answer book provided.
Calculators may be used. The following models are permit- ted: Casio fx83 / Casio fx85.
Books, notes or other written material may not be brought into this examination
Calculators Notes
PLEASE DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
2019 Kings College London

May 2019 6CCS3OME
13. The diagram below shows a flow network for a USA based transportation company. In this diagram, a flow f is shown, with the source node denoted s, the sink (target) t, and intermediate nodes with letters between a to f. The two numbers next to each edge denote the amount of flow in that edge, and the capacity of the edge in parentheses.
a. In the context of network flow problems, define and provide the formula for each of the following terms.
1. Value of a flow,
2. Flow conservation, 3. Saturated edge.
[3 marks]
b. What is the value of the flow in this figure? Show a decomposition of this flow into possible flow paths.
[3 marks]
c. Does this graph show a maximum flow? Using the max-flow min-cut theorem, explain if the flow shown in the figure is a maximum flow?
[5 marks]
d. The capacity of the edge (a, d) is increased by from 2 to 3. Starting from the flow given in the figure above, construct a residual network, and use the Edmonds-Karp algorithm to compute the maximum flow. Show your working.
[4 marks]
Page 20
SEE NEXT PAGE

May 2019 6CCS3OME
14. a.Explainthefollowingnotions,whichappearinthecontextofthebranch- and-bound method:
1. partial configuration, 2. branching procedure, 3. bounding procedure.
[5 marks]
b. Let a partial configuration for the travelling salesman problem be any initial segment of a tour.
1. Describe a bounding procedure suitable for use in the branch-and- bound method for the travelling salesman problem.
2. Show the bound which your bounding procedure returns for the input given in the table below and the partial solution 1, 2, 3.
12345 1
2 3 4 5
0 10 15 4 20 90836 4 5 0 7 16
11 7 9 0 2 18 9 6 4 0
Page 21
FINAL PAGE
[10 marks]