12 November 2015
Term Test # 2
CSC 373 H1
Duration: Aids Allowed:
Student Number: Last (Family) Name(s): First (Given) Name(s):
50 minutes
One single-sided handwritten 8.5″×11″ aid sheet.
Do not turn this page until you have received the signal to start. In the meantime, please read the instructions below carefully.
This term test consists of 3 questions on 8 pages (including this one), printed on both sides of the paper. When you receive the signal to start, please make sure that your copy of the test is complete, fill in the identification section above, and write your name on the back of the last page.
Answer each question directly on the test paper, in the space provided, and use one of the “blank” pages for rough work. If you need more space for one of your solutions, use a “blank” page and indicate clearly the part of your work that should be marked.
In your answers, you may use without proof any theorem or result covered in lectures, tutorials, assignments, or the textbook, as long as you give a clear statement of the result(s)/theorem(s) you are using. You must justify all other facts required for your solutions.
Write up your solutions carefully! In particular, use notation and terminology correctly and explain what you are trying to do —part marks will be given for showing that you know the general
structure of an answer, even if your solution is incomplete.
If you are unable to answer a question (or part of a question), you can get 10% of the marks by leaving your answer entirely blank
(or crossing off everything you wrote to make it clear that it should not be marked).
Marking Guide
No 1: / 9 No 2: / 8 No 3: / 8
TOTAL: /25
page 1 of 8
over…
Good Luck!
CSC 373 H1 Term Test # 2 12 November 2015 Use the space on this “blank” page for scratch work, or for any solution that did not fit elsewhere.
Clearly label each such solution with the appropriate question and part number.
page 2 of 8 cont’d. . .
12 November 2015 Term Test # 2 CSC 373 H1 Question1. [9marks]
Recall the Maximum Bipartite Matching problem: given an undirected bipartite graph G = (V1,V2,E), where E ⊆ V1 × V2, find a subset of disjoint edges with maximum size (where two edges are disjoint if they have no common endpoint).
Give a linear (or integer) program that corresponds to this problem. Describe clearly every component of your answer. Then, justify the correctness of your linear program: explain clearly what each variable and constraint represents and how solutions to each problem correspond to each other (and what that tells you about the relative values of those solutions).
Hint: Use one variable for each edge. If you are unable to solve this problem, you can get more than 10% of the marks by explaining clearly what your solution should consist of (including how to argue its correctness).
page 3 of 8 over…
CSC 373 H1 Term Test # 2
12 November 2015
Question2. [8marks]
Consider the network N1 pictured on the right. a Part(a) [3marks]
Compute the capacity of the cut X1 = {s,b,c},{a,d,t}. Show your work: list the components of the network used to obtain your answer.
10 3 3 5
s 8 b 10 c 8 t
5 3 3 10
d
Part(b) [1mark]
Let C1 represent your answer to Part (a). What can you conclude about |f |, for all valid flows f over N1?
page 4 of 8 cont’d. . .
12 November 2015 Term Test # 2 CSC 373 H1
Question2. (continued) Part(c) [4marks]
Given one network N and one cut X = (S , T ) in N , suppose that we reduce the capacity of every forward edge across X. Does the maximum flow value in N necessarily decrease? Justify your answer.
page 5 of 8 over…
CSC 373 H1 Term Test # 2 12 November 2015 Question3. [8marks]
For each of the following decision problems D, state whether D ∈ P, D ∈ NP or D ∈ coNP—make the strongest claim that you can. Then, justify your answer by writing down an explicit algorithm for D and explaining why it satisfies the properties required for your answer. Do not attempt to justify that other complexity classes are incorrect; focus on providing evidence that your choice is correct.
Part(a) [4marks] SomeShortPaths (“SSP” for short)
Input: UndirectedgraphG=(V,E),verticess,t∈V,non-negativeintegerk|V|.
Output: Does G contain some simple path from s to t with no more than k edges on the path?
page 6 of 8
cont’d. . .
12 November 2015 Term Test # 2
CSC 373 H1
Question3. (continued)
Part(b) [4marks]
AllShortPaths (“ASP” for short)
Input: UndirectedgraphG=(V,E),verticess,t∈V,non-negativeintegerk|V|. Output: Does every simple path in G from s to t contain no more than k edges?
page 7 of 8
over…
CSC 373 H1 Term Test # 2
On this page, please write nothing except your name.
12 November 2015
Last (Family) Name(s): First (Given) Name(s):
page 8 of 8
end
Total Marks = 25