CSC373 Winter’22, Midterm 1
Due: 11:00 Eastern Time Mar 12 2022
Instructions
1. Each question is listed on a separate page. If you print this PDF or write your solutions on
a tablet, it may be convenient to start answering each question right below it and add pages
as needed.
2. Upload a single PDF with your solutions, named “midterm2.pdf”, to MarkUs at https:
//markus.teach.cs.toronto.edu/2022-01/courses/22
3. For handwritten solutions, please make sure that your handwriting is legible, and your scan
is high-quality and not distorted.
4. Remember: You will receive 20% for any (sub)question when you leave it blank (or cross off
any written solution) and write “I do not know how to approach this problem.”.
Q1 [24 Points] Network Flow Let N = (V, E) be a network with nodes V and directed edges E
with integer capacities. Let F be the maximum flow value in N. Let P be any simple path of k
edges in N from s to t and let N+ be the network obtained from N by adding 1 to the capacity of
every edge on P.
(a) (4 marks) Prove that the maximum flow value in N+ is at least F+ 1.
(b) (4 marks) Prove that the maximum flow value in N+ may not be exactly F+ 1.
(c) (8 marks) What is a tight upper bound for the maximum flow value in N+? A tight upper
bound implies that you must show an example network and path where the upper bound maxi-
mum flow value is achieved.
(d) (4 marks) Given a flow of value F in N, show that you can compute the max flow in N+ in
O(k*(m+n)) time.
(e) (4 marks) Let N be the network obtained from N by subtracting 1 from the capacity of every
edge on P (assume a capacity of at least 1 for edges of P in N). Does the maximum flow value in
N necessarily decrease?
1

ÉE
3
8 5 do a offJ
Q2 [16 Points] Bipartite Flow
An orientation of an undirected graph G = (V; E) creates a directed graph G0 = (V; E0) by giv-
ing a direction to each undirected edge e = (u; v); that is, either (u; v) becomes a directed edge
(u; v) 2 E0 from u to v, or edge (v; u) 2 E0 from v to u. Consider the following graph orientation
problem: Given: An undirected graph G = (V;E). Output: An orientation of G so as to minimize
the maximum in-degree of any node. That is, we want to minimize maxv2V(Â(u;v)2E0 1).
Desribe a method to optimally solve this problem in polynomial time.
(a) (8 marks) Set up a bipartite graph involving edges and vertices of G as a network whose flow
can be used to solve the above problem.
(b) (4 marks) Show how max flow in network of (a) can be used to find the desired orientation.
(c) (4 marks) What is the run time complexity of your algorithm? You may assume knowledge of
the run-time complexity of the Ford-Fulkerson algorithm.
2
o o
of d
8
O O
N 9 a
8 bx
or
off
de
Q3 [10 Points] Linear Programming
(a) (4 marks) Write the following linear program in standard form (i.e. maximize cTx subject to
Ax  b, and x 0:
minimize |x|+ 3y, subject to x+ y 0, and y 0.
(b) (2 marks) Show that the linear program in (a) has a feasible solution?
(c) (2 marks) Is the domain of feasible solutions bounded?
(d) (2 marks) What is the optimal solution, if one exists?
3
tax
tax Min key
3g
min tty
max t y Max t 3g
tix Max E ta 3g t.tt 3g
tax
ti taty20
470 titta YEO
YEO ti ta 470
I Ee 4
3
3 2
s 4
422
t
a 5
P S 1 4 2,3 t
7
3 3
s3 I t
2 2
2
4
2
C 19

欢迎咨询51作业君