CSC373H1
Midterm Test
Fall 2019
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, and fill in the identification section above.
Answer each question directly on the test paper, in the space provided, and use any 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, problem sets, or assignments, 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— partial marks will be given for showing that you know the general structure of an answer, even if your solution is incomplete.
However, if you do not know how to approach a problem, remember that writing “I do not know how to approach this problem.” (or a similar statement) earns you 20% of the marks for a solution (not writing this will still earn you 10%), but only if you leave the question entirely blank (or cross off everything you wrote to make it clear that it should not be marked).
Marking Guide
No 1: /25 No 2: /20 No 3: /10
TOTAL: /55
page 1 of 8
over…
Good Luck!
CSC373H1 Midterm Question 1. Network Flow [25 marks]
Let N = (V , E) be a network with a set of nodes V and a set of directed edges E with integer capacities. Let F be the maximum flow value in N from node s to node t. Let P be a simple path from s to t in N consisting of k edges, and let N + be the network obtained from N by adding 1 to the capacity of every edge in P .
(a) (5 marks) TRUE/FALSE: The maximum flow value in N + is at least F + 1. (If this is true, argue why. If this is false, provide a counter-example.)
(b) (5 marks) Prove that the maximum flow value in N + may not be exactly F + 1.
(c) (10 marks) What is a tight upper bound on the maximum flow value in N+ in terms of F and k? You must prove that your upper bound always holds. To show that it is tight, you must produce a network in which the maximum flow value in N + exactly matches your upper bound.
(d) (5 marks) Let N − be the network obtained from N by subtracting 1 from the capacity of every edge in P (assume each edge in P had capacity at least 1 in N ). TRUE/FALSE: The maximum flow value in N − is always strictly less than F. (If this is true, argue why. If this is false, provide a counter-example.)
page 2 of 8 cont’d. . .
Test Fall 2019 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 3 of 8 over…
CSC373H1 Midterm Question 2. Integer Linear Programming [20 marks]
Recall that given an undirected graph G = (V , E), we say that G is k-colourable if we can assign a colour c(v) ∈ {1, . . . , k} to every vertex v ∈ V such that no two adjacent vertices have the same colour (i.e. c(u) c(v) for all (u,v) ∈ E).
The minimum vertex coloring problem, MinColour, is defined as follows. • Input: An undirected graph G = (V , E) with n nodes and m edges.
• Output: The smallest positive integer k such that G is k-colourable.
We wish to write a binary integer program (with each variable taking value in {0, 1}) to solve MinColour.
(a) (5 marks) Argue that the solution of MinColour is never greater than n (the number of nodes in G).
(b) (15 marks) Provide a binary integer linear program to solve MinColour. Clearly explain why your objective minimizes the number of colours used and why your constraints ensure a valid colouring. For full marks, your program should use at most O(n2) binary variables, where n is the number of nodes in G.
page 4 of 8 cont’d. . .
Test Fall 2019 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 5 of 8 over…
CSC373H1 Midterm Question 3. P/NP/coNP [10 marks]
(a) (2.5 marks) Does P = N P imply N P = coN P ? Justify your answer.
(b) (2.5 marks) Does N P = coN P imply P = N P ? Justify your answer.
(c) (2.5 marks) Given an undirected graph G and a positive integer k, the k-Colour problem asks whether G is k-colourable (i.e. whether it has a valid colouring using at most k colours). Show that given a polynomial-time algorithm for k-Colour, one can solve MinColour in polynomial time.
(d) (2.5 marks) Show that given a polynomial-time algorithm for MinColour, one can solve k-Colour in polynomial time.
page 6 of 8 cont’d. . .
Test Fall 2019 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 7 of 8 over…
CSC373H1 Midterm 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 8 of 8 cont’d. . .