Edward Kingyuan Lim
Dashboard My courses 6CCS3OME 20~21 SEM2 000001 OPTIMIZATION ME Revision and information about examination Mock exam paper, 2020/21
Started on State Completed on Time taken Grade
Saturday, 15 May 2021, 7:26 PM Finished
Saturday, 15 May 2021, 7:29 PM 3 mins 29 secs
34.00 out of 100.00
Information
In the real exam, you will have 90 minutes to complete and submit the KEATS quiz and additional 60 minutes to submit the document in the pdf format showing your working out for selected questions. This document should be prepared according to the instructions published in KEATS in section (‘course’) “Informatics Exams Information – May 2021”. You must submit your working- out document via the separate submission link for this examination.
For this mock exam, you should try to be well within the above time limits.
You will see the correct answers to the quiz questions after you submit your answers. (During the real examination, you will not see correct answers after submitting your answers.) The submitted working-out will not be checked. (Submit your working our, if you want to test your process of scanning and submitting.)
The questions are only examples. If the mock exam includes a question on a particular topic, this doesn’t mean that a similar question will be included in the real examination. Similarly, if the mock exam doesn’t include a particular topic, this doesn’t mean that this topic won’t be included in the real examination.
Linear programming can be used to calculate the maximum ow in a network from the source tothesink .Whichofthestatementsbelowgivesthecorrectobjectivefunctionandthecorrect number of constraints in a linear program for computing maximum ow in the following graph? In this graph, the maximum capacity of each edge is given as the number next to the corresponding edge. The ow along an edge is denoted by . We only consider
variables when the edge
exists.
Select one:
Objective function:
Objective function: Objective function: Objective function:
; the number of constraints: . ; the number of constraints: .
; the number of constraints: . ; the number of constraints: .
The correct answer is: Objective function: ; the number of constraints: .
Question 1 Incorrect Mark 0.00 out of 5.00
𝑠
02
))2 ,𝑠(𝑓 + )1 ,𝑠(𝑓(xam
02
))𝑡 ,4(𝑓 − )𝑡 ,3(𝑓 − )2 ,𝑠(𝑓 + )1 ,𝑠(𝑓(xam
01 02 41
))2 ,𝑠(𝑓 − )1 ,𝑠(𝑓(xam ))2 ,𝑠(𝑓 + )1 ,𝑠(𝑓(xam ))2 ,𝑠(𝑓 + )1 ,𝑠(𝑓(xam
)𝑗 ,𝑖(𝑓
)𝑗 ,𝑖(
)𝑗 ,𝑖(
)𝑗 ,𝑖(𝑓
𝑡
The gure below (which is the same as in Question 1) illustrates a ow network, where the capacity of each edge is given by the number next to the corresponding edge, and the source and sink nodes are denoted with labels and respectively. Select all correct statements about this network.
Select one or more:
The Ford-Fulkerson method run on this network will terminate successfully after only 1 iteration, as both edges from the source have equal capacity.
For each execution of the Ford-Fulkerson method on this network, there is an execution of the Edmonds-Karp algorithm on this network with the same number of iterations.
There exist two minimum cuts in this ow network.
Both edges outgoing from the source (node ) will be saturated after the execution of the Ford- Fulkerson method.
The correct answers are: Both edges outgoing from the source (node ) will be saturated after the execution of the Ford-Fulkerson method.
, For each execution of the Ford-Fulkerson method on this network, there is an execution of the Edmonds-Karp algorithm on this network with the same number of iterations.
Question 2 Incorrect Mark 0.00 out of 10.00
𝑠
𝑠
𝑡𝑠
𝑠
Flow networks are directed graphs used to model systems involving transportation of one or more commodities. There exist many types of network ow problems, including maximum ow problems, minimum-cost ow problems and multicommodity ow problems. Select the true statements about ow networks.
Select one or more:
In a multicommodity ow network, the amount of ow of a given commodity output from is always less than the amount of ow input to , for any node other than the source and the destination of this commodity.
If there is an augmenting path in a residual network, then the ow cannot be optimal.
The residual capacity of an edge is always greater than, or equal to, the amount of augmenting ow allowed through that edge.
A cut is a partitioning of a network into two disjoint sets and , where the net ow across the cut is the sum of the ow from to , plus the sum of the ow from to .
The correct answers are: The residual capacity of an edge is always greater than, or equal to, the amount of augmenting ow allowed through that edge.
, If there is an augmenting path in a residual network, then the ow cannot be optimal.
Question 3 Partially correct Mark 5.00 out of 10.00
𝑣
)𝑣 ,𝑢(
𝑆𝑇 𝑇𝑆 𝑇𝑆
𝑣𝑣
)𝑣 ,𝑢(
In the graph below, Dijkstra’s algorithm can be used to compute the shortest paths from node 0 to all other nodes. Assuming that we execute this algorithm, then upon the termination, which of the following choices describes the output of the algorithm? For a node , we denote here by and the shortest-path estimate for and the parent (predecessor) of .
Select one:
Question 4 Incorrect Mark 0.00 out of 10.00
𝑣 𝑣 𝜋.𝑣 𝑑.𝑣 𝑣
The correct answer is:
This question, in addition to selecting quiz answers (part B of the question), requires also including an additional answer in a separate document (part A of the question). If the additional answer is not submitted or is signi cantly incorrect, then the mark of Zero will be given for the whole question, irrespectively of the selected quiz answers. Otherwise the mark for this question will be the mark obtained for the quiz answers.
The following diagram (from the lecture slides) depicts an example input for the minimum-cost ow problem. The two numbers next to an edge are the capacity (the rst number) and the cost of this edge. The number next to a node indicates the supply/demand at this node.
A: Using the same type of diagram as above, depict the input for the minimum-cost flow problem specified by the following linear program:
B: Assume that the Successive Shortest Path algorithm is applied to the input for the minimum- cost ow problem speci ed in part A. Whenever there is a choice during the computation between two or more nodes, assume that the rst node in alphabetical order is taken. Select all correct statements.
Select one or more:
In this input network, increasing the capacity of one single edge cannot decrease the cost of an
Question 5 Incorrect Mark 0.00 out of 20.00
optimal ow.
The rst selected path is from node to node .
The rst selected path is from node to node .
The nal ow does not satisfy all supplies and demands.
The rst selected path is from node to node .
There is an edge in this input network such that increasing the capacity of this edge decreases the cost of an optimal ow.
During the whole computation, there are 4 iterations which update the ow.
During the whole computation, there are 5 iterations which update the ow. The nal ow satis es all supplies and demands.
During the whole computation, there are 3 iterations which update the ow.
The given linear programme speci es the following input network for the minimum cost ow problem:
The correct answers are: The rst selected path is from node to node .
, During the whole computation, there are 5 iterations which update the ow., The nal ow satis es all supplies and demands. , There is an edge in this input network such that increasing the capacity of this edge decreases the cost of an optimal ow.
𝑎𝑏
𝑐𝑏
𝑏𝑎 𝑎𝑏
All-pairs shortest-paths methods can be used to nd shortest paths for all source-destination pairs of nodes. Select the true statements about methods that can be used for this.
Select one or more:
By adding one large number to the weight of each edge, we can remove all negative edge weights without changing shortest paths.
An all-pairs shortest-paths method cannot be an iterative application of the Bellman-Ford algorithm, if the graph contains negative weights.
An all-pairs shortest-paths method cannot be an iterative application of Dijkstra’s algorithm, if the graph contains negative weights.
Johnson’s all-pairs shortest-paths algorithm can be used if the graph contains positive weight cycles.
The correct answers are: An all-pairs shortest-paths method cannot be an iterative application of Dijkstra’s algorithm, if the graph contains negative weights., Johnson’s all-pairs shortest-paths algorithm can be used if the graph contains positive weight cycles.
Question 6 Correct Mark 5.00 out of 5.00
This question, in addition to selecting quiz answers (part B of the question), requires also including an additional answer in a separate document (part A of the question). If the additional answer is not submitted or is signi cantly incorrect, then the mark of Zero will be given for the whole question, irrespectively of the selected quiz answers. Otherwise the mark for this question will be the mark obtained for the quiz answers.
Graph shows an input for the minimum spanning tree problem. Prim’s algorithm and Kruskal’s algorithm are applied to this graph, but both algorithms are interrupted before the end of the computation and output an incomplete tree or forest. Those two incomplete outputs are shown in and , without indication which output comes from which algorithm.
Question 7 Correct Mark 10.00 out of 10.00
𝐶𝐵 𝐴
A: Draw a minimum spanning tree of graph . B: Select all correct statements.
Select one or more:
The weight of a minimum spanning tree of the graph is not greater than 80.
𝐴
𝐴
We cannot say which gure is an iteration step of which algorithm, because the output depends on the choices made during the computation.
is an iteration step from Prim’s and is from Kruskal’s.
is an iteration step from Prim’s algorithm and from Kruskal’s algorithm. The weight of a minimum spanning tree of graph is greater than 80.
The minimum spanning tree of graph (this graph has a unique minimum spanning tree):
The correct answers are: is an iteration step from Prim’s and is from Kruskal’s. , The weight of a minimum spanning tree of graph is greater than 80.
Question 8 Partially correct Mark 2.00 out of 5.00
Which of the following statements are true?
Select one or more:
A polynomial time algorithm for an NP-Hard problem would imply the existence of polynomial algorithms for all problems in the NP class.
If a problem A reduces to a problem B we can say that B is at least as di cult to solve as A. An NP-Hard problem must necessarily be NP-Complete.
If P=NP, then all problems in NP are solved to optimality in polynomial time.
The correct answers are: A polynomial time algorithm for an NP-Hard problem would imply the existence of polynomial algorithms for all problems in the NP class., If a problem A reduces to a problem B we can say that B is at least as di cult to solve as A., If P=NP, then all problems in NP are solved to optimality in polynomial time.
𝐴 𝐶𝐵
𝐴
𝐴 𝐵𝐶
𝐶𝐵
The following statements refer to the Branch-and-Bound optimisation technique applied to a combinatorial optimization problem . Select all correct statements.
Select one or more:
During the execution of a Branch-and-Bound algorithm, if a complete con guration (solution) to the problem is generated, then it is the only time this con guration is generated.
The branching procedure takes as an input an incomplete con guration and generates at least one new partial or complete con guration.
The bounding procedure does not in uence the runtime performance of the algorithm.
The bounding procedure applied on a partial con guration , gives us an estimate about the cost of any con guration containing .
The correct answers are: During the execution of a Branch-and-Bound algorithm, if a complete con guration (solution) to the problem is generated, then it is the only time this con guration is generated.
, The branching procedure takes as an input an incomplete con guration and generates at least one new partial or complete con guration., The bounding procedure applied on a partial con guration , gives us an estimate about the cost of any con guration containing .
Question 10 Incorrect Mark 0.00 out of 10.00
Select all statements that describe correctly the behaviour of the Simulated Annealing algorithm.
Select one or more:
Convergence is only a ected by the number of iterations.
The Simulated Annealing algorithm does not guarantee that an optimal solution will be found. The performance of Simulated Annealing is not a ected by the choice of initial con guration.
The Simulated Annealing algorithm maintains a set of solutions and applies small modi cations to each one of them to generate new solutions.
The correct answers are: The performance of Simulated Annealing is not a ected by the choice of initial con guration., The Simulated Annealing algorithm does not guarantee that an optimal solution will be found.
Question 9 Partially correct Mark 2.00 out of 5.00
𝐶
𝐶
𝐶
𝐴
𝐴
𝐶
𝐴
The pool of con gurations has 6 individuals, and their tness values are given in the table below.
For each of the three selection strategies Roulette, Rank Selection and Tournament Selection, which of the following tables shows the correct selection probabilities. For the tournament selection assume that the tournament is between three individuals.
Select one:
None of the tables is correct.
Question 11 Correct Mark 10.00 out of 10.00
The correct answer is:
Recording of the revision session
Submission of additional answers for the mock exam
Jump to…
▶
◀