Quiz 3
MCQ 1 November 2019
There will be questions with check boxes where single or multiple choices could be correct.
Mark will only be awarded ONLY if correct choices ticked.
Assignment 3
Due by 3 November at 11:59pm. Final Exam
Friday 22 November at 6pm in the International Student Lounge Wentworth G01.
2.5 hours
Closed book
Calculator nonprogrammable allowed
Homemade 2page cheat sheet allowed
6 questions
Allocate your timeeffort to a question according to its marks
The University of Sydney
Page 1
The University of Sydney
Room Number
Seat Number
Student Number
ANONYMOUSLY MARKED
Please do not write your name on this exam paper
EXAM WRITING TIME: READING TIME:
EXAM CONDITIONS:
EXAMINATION
Semester 2Main, 2019
COMP9007 Algorithms
2.5 hours 10 minutes
For Examiner Use Only Mark
CONFIDENTIAL EXAM PAPER
This paper is not to be removed from the exam venue Information Technologies
Q
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
This is a CLOSED book examinationno material permitted During reading timewriting is not permitted at all
MATERIALS PERMITTED IN THE EXAM VENUE:
No electronic aids are permitted e.g. laptops, phones
Calculatornonprogrammable
One A4 sheet of handwritten andor typed notes double sided
MATERIALS TO BE SUPPLIED TO STUDENTS:
None
INSTRUCTIONS TO STUDENTS:
The exam comprises 16 pages and contains 6 questions. All questions must be answered.
Space is provided for your answers.
If you need more space use the blank pages at the end of the paper and clearly mark where the answer to a question starts and ends.
Note that questions are of unequal value. The total mark of this exam paper is 100. 17Take care to write legibly. Write your final answers in ink, not pencil.
18
Please tick the box to confirm that your examination paper is complete.Page 1 of 16
Total
Page 2
Assignment 2 Results
40
35
30
25
20
15
10
5
0
0, 5
10, 15
20, 25
30, 35
40, 45
50, 55
60, 65
70, 75
80, 85
5, 10
15, 20
25, 30
35, 40
45, 50
55, 60
65, 70
75, 80
85, 90
95, 100 90, 95
The University of Sydney Page 3
Flow networks II: Applications
The University of Sydney
Page 4
General techniques in this course
Stable Matching
Algorithms design and analysis, asymptotic growthData structures and recursive algorithms
Graph algorithms: BFS and DFS
Greedy algorithms
DivideConquer algorithms
Dynamic programming algorithms
Network flow algorithms
Theory
Applications
Next lecture: NP and intractability The University of Sydney
Page 5
Recap: Minimum Cut Problem
Flow network
Abstraction for material flowing through the edges.GV, Edirected graph, no parallel edges.
Two distinguished nodes: ssource, tsink.
cecapacity of edge e.
295
10
15 15
sources 5 3 8 6 10 tsink
4
10
capacity
The University of Sydney
Page 6
15
46
10
15 4 30 7
Recap: Flows
Definition: An st flow is a function that satisfies:For each e I E: 0fece
capacity conservation
a f e . e out of s
6
10
For each v I Vs, t: a fee in to v
Definition: The value of a flow f is: 6
a fe e out of v
2 9 5
v f
10
10
0
15 15 0
44 388
s 5 3 8 6 10 t
capacity
flow
15
11
1
40 6 150
11
10
10
The University of Sydney
4 30 7
Value2Pa4ge 7
Recap: Maximum Flow Problem
Max flow problem. Find st flow of maximum value.
9
2 9 5
10
10
1
15 15 0
9
10
40 489
s 5 3 8 6 10 t
capacity
flow
15
14
4
40 6 150
14
10
10
The University of Sydney
4 30 7
Value2Pa8ge 8
Recap: Cuts
Definitions:
AnstcutisapartitionA,BofVwithsIAandtIB.
The capacity of a cut A, B is: capA, B295
a ce e out of A
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
Capacity10515
The University of Sydney
30
Page 9
Recap: Cuts
Definitions:
AnstcutisapartitionA,BofVwithsIAandtIB.
The capacity of a cut A, B is: capA, B2 9 5
10
a ce e out of A
15 15
s 5 3 8 6 10 t
4
10
A
The University of Sydney
15 4 30 7
15
46
10
Capacity915830
62
Page 10
Recap: Flows and Cuts
Flow value lemma. Let f be any flow, and let A, B be any st cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
afeafevf e out of A e in to A
6
2 9 5
10
10
44
0
15 15 0
6
10
388
s 5 3 8 6 10 t
A
1
40 6 150
11
10
10
15
11
Value60811124 Page 11
The University of Sydney
4 30 7
Recap: Residual Graph
Originaledge: eu,v IE.Flowfe,capacityce.
Residualedge.
Undoflowsent.
eu,vandeR v,u.Residualcapacity:
ceiicefe ifeIE
f i f e if eR I E
Residual graph: GfV, Ef .
Residualedgeswithpositiveresidualcapacity.Ef e:fece E eR :ce0.
capacity
u 17 v
6
flow
residualcapacity
u 11 v
6
residual capacity
The University of Sydney
Page 12
FordFulkerson Algorithm
FordFulkersonG,s,tforeach e I E
fe0
Gfresidual graph
while there exists augmenting path P in Gf fAugmentf,P
update Gf
return f
Augmentf,P
bbottleneckP,f foreach e u,v I P
if e is a forward edge then
increase fe in G by b
else e is a backward edge
decrease fe in G by b
return f
Page 13
The University of Sydney
Recap: FordFulkerson Algorithm
0
2 4 4
flow
capacity
G:
s 10 3 9 5 10 t
0 10208 6010
8X0 0 X8
0 0 8X0
Flow value0
244
residual capacity 10
Gf:
10
2
86
s 10 3 9 5 10 t
The University of Sydney
Page 14
Recap: FordFulkerson Algorithm
0
2 4 4
G:
0
1 0 X8 8
10208 6010
s 10 3 X 5 t 9 10
X
0 2 02 10X8
2 4 4
Flow value8
Gf:
8
2
86
10
2 s 10 3
9 5 2 t 8
The University of Sydney
Page 15
Recap: MaxFlow MinCut Theorem
Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths in the residual graph.
Maxflow mincut theorem: The value of the max flow is equal to the value of the min cut. FordFulkerson 1956
Integrality. If all capacities are integers then every flow value fe and every residual capacities cf e remains an integer throughout the algorithm.
The University of Sydney Page 16
Applications of max flow
Bipartite matching
Perfect matching
Disjoint paths
Network connectivityCirculation problemsImage segmentationProject selection
Baseball elimination
The University of Sydney
Page 17
Disjoint Paths
The University of Sydney Page 18
Edge Disjoint Paths
Disjoint path problem:
Given a digraph GV, E and two nodes s and t, find the max number of edgedisjoint st paths.
Definition: Two paths are edgedisjoint if they have no edge in common.
25
s36t
47
The University of Sydney
Page 19
Edge Disjoint Paths
Disjoint path problem:
Given a digraph GV, E and two nodes s and t, find the max number of edgedisjoint st paths.
Definition: Two paths are edgedisjoint if they have no edge in common.
25
s36t
47
The University of Sydney
Page 20
Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111
111
s1 1t
1
1
1 1
11
The University of Sydney
Page 21
Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111 10 10
1 1010
s11 11t
10
11
11 11
111
1
Theorem: Max number edgedisjoint st paths equals max flow value.
Proof:
Suppose there are k edgedisjoint paths P1, . . . , Pk.
Set fe1 if e participates in some path Pi ; else set fe0.Since paths are edgedisjoint, f is a flow of value k.
The University of Sydney Page 22
Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111 10 10
1 1010
s11 11t
10
11
11 11
111
1
Theorem: Max number edgedisjoint st paths equals max flow value. Proof: U
Suppose max flow value is k.
Integrality theoremthere exists 01 flow f of value k.Consider edge s, u with fs, u1.
by conservation, there exists an edge u, v with fu, v1
continue until reach t, always choosing a new edge
Produces k not necessarily simple edgedisjoint paths.The University of Sydney
Page 23
Vertex Disjoint Paths
Disjoint path problem:
Given a digraph GV, E and two nodes s and t, find the max number of vertexdisjoint st paths.
Definition: Two paths are vertexdisjoint if they have no vertex, except s and t, in common.
Reduction to disjoint edge disjoint paths:
xx1 in
xo
The University of Sydney
Page 24
Network Connectivity
Network connectivity. Given a digraph GV, E and two nodes s and t, find min number of edges whose removal disconnects t from s.
Definition: A set of edges F I E disconnects t from s if all st paths uses at least one edge in F.
25
s36t
47
The University of Sydney
Page 25
Network Connectivity
Network connectivity. Given a digraph GV, E and two nodes s and t, find min number of edges whose removal disconnects t from s.
Definition: A set of edges F I E disconnects t from s if all st paths uses at least one edge in F.
25
s36t
47
The University of Sydney
Page 26
Edge Disjoint Paths and Network Connectivity
Theorem: The max number of edgedisjoint st paths is equal to the min number of edges whose removal disconnects t from s.
Proof: U
Suppose the removal of F I E disconnects t from s, and Fk.
Every st path uses at least one edge of F. Hence, the number of edge disjoint paths is at most k.
25 25 s36ts36t
The University of Sydne4y 7 4 7 Page 27
Edge Disjoint Paths and Network Connectivity
Theorem: The max number of edgedisjoint st paths is equal to the min number of edges whose removal disconnects t from s.
Proof:
Suppose max number of edgedisjoint paths is k.
Then max flow value is k.
Maxflow mincutcut A, B of capacity k.LetFbesetofedgesgoingfromAtoB.
Fk and disconnects t from s.
25 25 s36ts36t
A
4
y7 47Page28
The University of Sydne
Extensions to Max Flow
The University of Sydney Page 29
Circulation with Demands
Circulation with demands.
Directed graph GV, E.
Edge capacities ce, e I E.
Node supply and demands dv, v I V.
demand if dv0; supply if dv0; transshipment if dv0
Definition: A circulation is a function that satisfies:
For each e I E: 0fece capacity
ForeachvIV: afeafedv conservation e in to v e out of v
Circulation problem: Given V, E, c, d, does there exist a circulation?
The University of Sydney
Page 30
Circulation with Demands
Necessary condition: sum of suppliessum of demands. adva dv : D
v:dv0 v:dv 0
Proof: Sum conservation constraints for every demand node v.
8
6 supply
G:
7
77
106 49
3 411
The University of Sydney
Page 31
10 0
capacity
demand
Circulation with Demands
Necessary condition: sum of suppliessum of demands. adva dv : D
v:dv0 v:dv 0
Proof: Sum conservation constraints for every demand node v.
G:
7
8
61 477
10 66 3
6 supply
7 42 9
3 411
10 0
4
capacity
flow
demand
The University of Sydney
Page 32
Circulation with Demands
Max flow formulation.
6 supply 106 49
3 411
8
G:
7
77
The University of Sydney
Page 33
10 0
demand
Circulation with Demands
Max flow formulation.
Add new source s and sink t.
For each v with dv0, add edge s, v with capacity dv.
For each v with dv0, add edge v, t with capacity dv.
Claim: G has circulation iff G has max flow of value D. s
saturates all edges leaving s and entering t
7
8
6
supply
G:
77
106 49
34
0 10
11
demand
The University of Sydney
Page 34
t
Circulation with Demands
Integrality theorem. If all capacities and demands are integers, and there exists a circulation, then there exists one that is integervalued.
Proof: Follows from max flow formulation and integrality theorem for max flow.
Characterization.
Given V, E, c, d, there is a feasible circulation with demand dv iff for all cuts A, B ,
SvIB dvcapA, B.
Proof idea: Look at min cut in G. Similar proof as the proof for the Marriage Theorem.
The University of Sydney
Page 35
Circulation with Demands and Lower Bounds
Feasible circulation.
Directed graph GV, E.
Edge capacities ce and lower bounds !e, e I E.Node supply and demands dv, v I V.
Definition: A circulation is a function that satisfies:
For each e I E: !efece capacity
ForeachvIV: afeafedv conservation e in to v e out of v
Circulation problem with lower bounds.
Given V, E, !, c, d, does there exists a circulation? The University of Sydney
Page 36
Circulation with Demands and Lower Bounds
Idea: Model lower bounds with demands.
Send !e units of flow along edge e.
Update demands of both endpoints. lower bound upper bound
v 2,9 w dv G dw
capacity
v 7 w
Theorem: There exists a circulation in G iff there exists a circulation in G. If all demands, capacities, and lower bounds in G are integers, then there is a circulation in G that is integervalued.
Proof sketch: fe is a circulation in G iff fefe!e is a circulation in G. The University of Sydney Page 37
dv2
dw2
G
Survey Design
The University of Sydney Page 38
Survey Design: Problem
Design survey asking n1 consumers about n2 products.
Can only survey consumer i about a product j if they own it.Ask consumer i between ci and ci questions.
Ask between pj and pj consumers about product j.
Goal: Design a survey that meets these specs, if possible.
The University of Sydney
Page 39
Survey Design: Algorithm
Formulate as a circulation problem with lower bounds.Include an edge i, j if consumer i owns product j.Integer circulation U feasible survey design.
1
c1, c1
2
s 3 4
consumers 5
0,
0, 1 1
p1, p1 2
3 4 5
t
products
The University of Sydney
Page 40
Survey Design: Correctness
1. If the Circulation problem with lower bounds is feasible then the Survey Design problem is feasible.
2. If the Survey Design problem is feasible then the Circulation
problem is feasible.
0,
0, 1 1
p1, p1 2
1
c1, c1
2
s 3 4
consumers 5
3 4 5
t
products
The University of Sydney
Page 41
Image Segmentation
The University of Sydney Page 42
Image Segmentation
Image segmentation.
Central problem in image processing.Divide image into coherent regions.
Ex: Three people standing in front of complex background scene. Identify each person as a coherent object.
The University of Sydney
Page 43
Image Segmentation: Problem
Foregroundbackground segmentation.
Vset of pixels, Epairs of neighboring pixels.
Label each pixel in picture as belonging to foreground or background.
ai 3 0 is likelihood pixel i in foreground.
bi 3 0 is likelihood pixel i in background.
pij 3 0 is separation penalty for labeling one of i
and j as foreground, and the other as background for i,j in E.
Goals:
Accuracy: if aibi in isolation, prefer to label i in foreground.
Smoothness: if many neighbors of i are labeled foreground, we should
be inclined to label i as foreground.Find partition A, B that maximizes:
aaiabjapij
The University of Sydney
Page 44
foreground background
iIA jIB !!
i,jI E Ai,j 1
Image Segmentation
Formulate as min cut problem.Maximization.
No source or sink.Undirected graph.
Turn into minimization problem.
Maximizing aaiabjiIA jIB
a pij i,jI E
Ai,j 1 is equivalent to maximizing
!!
or alternatively minimizing The University of Sydney
constant
aajab ap i ij
jIB iIA i, jIE A!i, j 1
Page 45
Image Segmentation
Formulate as min cut problem.
GV,E.
Add source to correspond to foreground; add sink to correspond to background
Use two antiparallel edges instead of undirected edge.
pij
pij pij
aj
s ipijj t
bi
G
The University of Sydney
Page 46
Image Segmentation
Consider min cut A, B in G.Aforeground.
capA,Baajabiapij jIB iIA i,jI E
if i and j on different sides, pij counted exactly once
iIA, jIBPrecisely the quantity we want to minimize.
s
aj
i pij j
bi
t
A
G
The University of Sydney
Page 47
Project Selection
The University of Sydney Page 48
Project Selection
Projects with prerequisites.
can be positive or negative
Set P of possible projects. Project v has associated revenue pv.
some projects generate money: create interactive ecommerce interface, redesign
web page
others cost money: upgrade computers, get site license
Set of prerequisites E. If v, w I E, then cant do project v unless doing project w.
A subset of projects A I P is feasible if the prerequisite of every project in A also belongs to A.
Project selection. Choose a feasible subset of projects to maximize revenue.
The University of Sydney Page 49
Project Selection: Prerequisite Graph
Prerequisite graph.
Include an edge from v to w if cant do v without doing w.
w
w
vx feasible
vx infeasible
The University of Sydney
Page 50
Project Selection: Min Cut Formulation
Min cut formulation.
Assign capacityto all prerequisite edge.
Add edge s, v with capacity pv if pv0.
Add edge v, t with capacity pv if pv0.
For notational convenience, define pspt0.
uw pu
pw
s py yz pz t
pvpx vx
The University of Sydney
Page 51
Project Selection: Min Cut Formulation
Claim. A, B is min cut iff A sis optimal set of projects.
InfinitecapacityedgesensureAsisfeasible.
Maxrevenuebecause: capA, Bapvapv vIB:pv 0 vIA:pv 0
!!
constant
apvapv v:p 0 vIA
! ! !
v
wu
A
s pyyzt
pv px vx
pu
pw
The University of Sydney
Page 52
Baseball Elimination
The University of Sydney Page 53
Baseball Elimination
Team i
Wins wi
Losses li
To play ri
Againstrij
Atl
Phi
NY
Mon
Atlanta
83
71
8
1
6
1
Philly
80
79
3
1
0
2
New York
78
78
6
6
0
0
Montreal
77
82
3
1
2
0
Which teams have a chance of finishing the season with most wins?
Montreal eliminated since it can finish with at most 80 wins, but Atlanta already has 83.
wi ri wj teamieliminated.Sufficient, but not necessary!
The University of Sydney Page 54
Baseball Elimination
Team i
Wins wi
Losses li
To play ri
Againstrij
Atl
Phi
NY
Mon
Atlanta
83
71
8
1
6
1
Philly
80
79
3
1
0
2
New York
78
78
6
6
0
0
Montreal
77
82
3
1
2
0
Whichteamshaveachanceoffinishingtheseasonwithmostwins?Phillycanwin83,butstilleliminated…
IfAtlantalosesagame,thensomeotherteamwinsone.
SoeitherAtlantareachesatleast84wins,orNewYorkreaches84wins
Remark: Answer depends not just on how many games already won and left to play, but also on whom theyre against.
The University of Sydney Page 55
Baseball Elimination
Baseball elimination problem.
Set of teams S.
Distinguished team s I S.
Team x has won wx games already.
Teams x and y play each other rxy additional times.
Is there any outcome of the remaining games in which team s finishes with the most or tied for the most wins?
The University of Sydney
Page 56
Baseball Elimination: Max Flow Formulation
Can team 3 finish with most wins?
Assume team 3 wins all remaining gamesw3r3 wins.
Distribute remaining games so that all teams havew3r3 wins.
team 4 can still win this many more games
games left
s
12 14 15
r247 24 25
game nodes
1 2
4
w3r3 w4 t
The University of Sydney
Page 57
45
5
team nodes
Baseball Elimination: Max Flow Formulation
Theorem. Team 3 is eliminated iff max flow strictly less than the total number of games left.
Integrality theoremeach remaining game between x and y added to number of wins for team x or team y.
Capacity on x, t edges ensure no team wins too many games.
games left
s
12 14 15
r247 24 25
game nodes 45
1 2
4
w3r3 w4
team 4 can still win this many more games
t
5
team nodes
The University of Sydney
Page 58
Applications
The University of Sydney
Page 59
Bipartite matching
Perfect matching
Disjoint paths
Network connectivityCirculation problemsImage segmentationProject selection
Baseball elimination
Reviews
There are no reviews yet.