[SOLVED] CS代考程序代写 AI algorithm ER data structure Lecture 13: Summary

Lecture 13: Summary
The University of Sydney
Page 1

How to design algorithms
Step 1: Understand problem
Step 4: Better understanding of problem
Step 2: Start with simple alg. Step 5: Improved alg.
Step 3: Does it work? Is it fast?
No Yes
The University of Sydney
Page 2
Problem
Algorithm
Analysis
DONE!

comp3027 – Overview I
– Graphs
– Definitions and properties
– Graph traversal: BFS and DFS
– Applications: min-link path, bipartitness…
– Greedy algorithms
The University of Sydney
Page 3
– – –
Greedy technique
Standard correctness proof: exchange argument Applications: Scheduling, MST, Dijkstra (incl. properties)

comp3027 – Overview II
– Divide-and-Conquer algorithms
– General technique: break, solve and combine
– Recursion: How to state and solve a recursion – Standard correctness proof: Induction
– Applications: Mergesort, Inversions,
The University of Sydney
Page 4

comp3027 – Overview III
– Dynamic programming
– General technique: break, solve, combine
• Define states
• State recursion
– Correctness proof: Induction
– Applications: Knapsack, weighted scheduling, RNA, Bellman-Ford,…
– Flow networks
The University of Sydney
Page 5
– – – –
Properties of flow network: max flow, min cut, integer lemma,… General technique: reduce to a flow network
Correctness proof: Solution for X Û Solution for FN Applications: matching, edge-disjoint paths, circulation,…

comp3027 – Overview IV
– Complexity
– Polynomial-time reductions!
– Classes: P, NP, NP-complete, NP-hard
– How to prove that a problem belongs to P/NP/NP-complete – Understand the NP-complete problems in lecture 10.
– Coping with hardness
– Understand the basic concepts:
• Exponential time algorithms • Restricted instances
• Approximation algorithms
The University of Sydney
Page 6

Main Themes
– Induction:
– Proof technique
– Algorithm design method: Divide-and-conquer and DP
– Reduction:
– Algorithm design: Reduction to flows
– Hardness: Reduction from NP-complete problems
The University of Sydney
Page 7

Lecture 2: Graphs
Joachim Gudmundsson
The University of Sydney Page 8

Lecture 2: Graphs
– Definitions
– Representations
The University of Sydney
Page 9
–
–
Graph traversal:
– Breadth First Search (incl. layers)
– Depth First Search
Applications: bipartiteness, min-link paths, …

Basic Definitions
– Graphs (directed/undirected)
– Tree (rooted/unrooted)
– Path (simple), connectivity, cycle…
The University of Sydney
Page 10

Trees
Definition: An undirected graph is a tree if it is connected and
does not contain a cycle.
Number of edges in a tree?
Theorem: Let G be an undirected graph on n nodes. Any two of the following statements imply the third.
– G is connected.
– G does not contain a cycle. – G has n-1 edges.
The University of Sydney Page 11

Graph traversal: Breadth First Search
BFS intuition. Explore outward from s in all possible directions, adding nodes one “layer” at a time.
s
L n-1
BFS algorithm.
– L0={s}.
– L1 = all neighbors of L0.
– L2 =allnodesthatdonotbelongtoL0 orL1,andthathaveanedgetoa node in L1.
– Li+1 = all nodes that do not belong to an earlier layer, and that have an edge to a node in Li.
Theorem: For each i, Li consists of all nodes at distance exactly i from s. There is a path from s to t iff t appears in some layer.
The University of Sydney
Page 12
L1
L2

Application: BFS applied to Shortest paths
The shortest path between two nodes u,v in an unweighted graph G, is the path with the minimum number of edges that connects u and v (if it exists).
Compute the shortest paths from a given node s to all other nodes using BFS.
The University of Sydney
Page 13

Application: BFS applied to bipartiteness
Lemma: If a graph G is bipartite, it cannot contain an odd length
cycle.
Lemma: Let G be a connected graph, and let L0, …, Lk be the layers produced by BFS starting at node s. Exactly one of the following holds.
(i) No edge of G joins two nodes of the same layer, and G is bipartite.
(ii) An edge of G joins two nodes of the same layer, and G contains an odd-length cycle (and hence is not bipartite).
L1 L2 L3 L1 L2 L3
The University of Sydney Case (i) Case (ii) Page 14

Lecture 3:
Greedy algorithms
The University of Sydney
Page 15

Greedy algorithms
The University of Sydney
Page 16
A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

Greedy
Examples of problems that can be solved using a greedy approach:
– Interval scheduling/partitioning
– Scheduling to minimize lateness
– Shortest path
– Minimum spanning trees
The University of Sydney
Page 17

Interval Scheduling
– Interval scheduling.
– Input: Set of n jobs. Each job i starts at time sj and finishes at time fj.
– Two jobs are compatible if they don’t overlap in time.
– Goal: find maximum subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 18

Interval Scheduling: Greedy Algorithm
Greedy algorithm. Consider jobs in increasing order of finish time. Take each job provided it is compatible with the ones already taken.
Sort jobs by finish times so that f1 £ f2 £ … £ fn. jobs selected
A®
for j = 1 to n {
if (job j compatible with A) A ¬ A È {j}
}
return A
Implementation. O(n log n).
– Rememberjobj*thatwasaddedlasttoA. – Job j is compatible with A if sj 3 fj*.
The University of Sydney Page 19

Greedy algorithms: Analysis
1. DefineyoursolutionXandanoptimalsolutionOPT.
2. Compare solutions. If X1OPT then they must differ in a
specific way.
3. Exchange pieces. Transform OPT by exchanging some piece of OPT for some piece of X.
4. Iterate. Argue optimality.
The University of Sydney
Page 20

Interval Scheduling: Recap of Exchange Argument
Greedy: OPT:
– We have an optimal solution that is “closer” to the greedy solution.
– Start the argument over again, but now the first (r+1) elements of the greedy solution and the optimal solution are identical.
– Continue iteratively until the optimal solution is transformed into the greedy solution without increasing the cost.
i1
i1
ir
ir+1
…
J1
J2
Jr
Jr+1
…
The University of Sydney Page 21

Minimum Spanning Tree*
Minimum spanning tree (MST). Given a connected graph G = (V, E) with real-valued edge weights ce, an MST is a subset of the edges
T Í E such that T is a spanning tree whose sum of edge weights is minimized.
4 24 4 62396 9
16
18
511 511
The University of Sydney
Page 22
8 14 7 8 7 10
21
G = (V, E)
T, SeÎT ce = 50

MST properties*
– Simplifying assumption. All edge costs ce are distinct.
– Cut property. Let S be any subset of nodes, and let e be the min cost edge with exactly one endpoint in S. Then the MST contains e.
– Cycle property. Let C be any cycle, and let f be the max cost edge belonging to C. Then the MST does not contain f.
S
e
e is in the MST
f
C
The University of Sydney
Page 23
f is not in the MST

Prim’s Algorithm*
– Prim’s algorithm. [Jarník 1930, Dijkstra 1957, Prim 1959] – Initialize S = any node.
– Apply cut property to S.
– Add min cost edge in cutset corresponding to S to T, and add one new
explored node u to S.
S
The University of Sydney
Page 24

Naïve implementation: O(nm) time Need a Union-Find data structure to efficiently keep track of connected components
Kruskal’s Algorithm*
Kruskal’s algorithm. [Kruskal, 1956] Consider edges in ascending order of weight.
Case 1: If adding e to T creates a cycle, discard e according to cycle property.
Case 2: Otherwise, insert e = (u, v) into T according to cut property where S = set of nodes in u’s connected component.
v
u
S
e
e
The University of Sydney
Case 1
Case 2
Page 25

Shortest Path Problem*
– Shortest path network.
– Directed graph G = (V, E).
– Source s, destination t.
– Length !e = length of edge e.
– Shortest path problem: find shortest directed path from s to t. cost of path = sum of edge costs in path
9 s
15
2 23 3 18
The University of Sydney
5
7 44 t
Page 26
14
6
6
11 4 19
5
20 16 6
2
Cost of path s-2-3-5-t = 9+23+2+16
= 50
30

Dijkstra’s Algorithm*
– Compute shortest path distances to every vertex. – Dijkstra’s algorithm.
– Maintain a set of explored nodes S for which we have determined the shortest path distance d(u) from s to u.
– Initialize S = {s}, d(s) = 0.
– Repeatedly choose unexplored node v which minimizes
p(v) = min
e = (u,v) : uÎS
add v to S, and set d(v) = p(v).
d(u) + !e ,
!e u
shortest path to some u in explored part, followed by a single edge (u, v)
v
d(u)
S
s
The University of Sydney
Page 27

Summary: Greedy algorithms
A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
Problems
– Interval scheduling/partitioning
– Scheduling: minimize lateness
– Minimum spanning tree (Prim’s algorithm)
– Shortest path in graphs (Dijkstra’s algorithms) –…
The University of Sydney
Page 28

Lecture 4:
Divide & Conquer
The University of Sydney
Page 29
Fast Fourier Transform

Divide-and-Conquer
The divide-and-conquer strategy solves a problem by:
1. Breaking it into subproblems that are themselves smaller
instances of the same type of the original problem. 2. Recursively solving these subproblems.
3. Appropriately combining (merging) their answers.
Most common usage.
– Break up problem of size n into two equal parts of size 1⁄2n. – Solve two parts recursively.
– Combine two solutions into overall solution in linear time.
The University of Sydney
Page 30

Mergesort
– Mergesort.
– Divide array into two halves.
– Recursively sort each half.
– Merge two halves to make sorted whole.
Jon von Neumann (1945)
A
L
G
O
R
I
T
H
M
S
divide
O(1)
A
L
G
O
R
I
T
H
M
S
sort
2T(n/2)
A
G
L
O
R
H
I
M
S
T
merge
O(n)
A
G
H
I
L
M
O
R
S
T
The University of Sydney
Page 31

Merging
– Merging. Combine two pre-sorted lists into a sorted whole.
– How to merge efficiently?
– Linear number of comparisons. – Use temporary array.
A
G
L
O
R
H
I
M
S
T
A
G
H
I
The University of Sydney
Page 32

Mergesort
– Mergesort.
– Divide array into two halves.
– Recursively sort each half.
– Merge two halves to make sorted whole.
Jon von Neumann (1945)
A
L
G
O
R
I
T
H
M
S
divide
O(1)
A
L
G
O
R
I
T
H
M
S
sort
2T(n/2)
A
G
L
O
R
H
I
M
S
T
merge
O(n)
A
G
H
I
L
M
O
R
S
T
The University of Sydney Þ T(n) = O(n) + 2T(n/2) Page 33

Counting Inversions: Divide-and-Conquer
– Divide-and-conquer.
– Divide: separate list into two pieces.
– Conquer: recursively count inversions in each half.
– Combine: count inversions where ai and aj are in different halves, and
return sum of three quantities.
1
5
4
8
10
2
6
9
12
11
3
7
1
5
4
8
10
2
6
9
12
11
3
7
5 blue-blue inversions 8 green-green inversions
9 blue-green inversions
5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9, 10-3, 10-7
Total = 5 + 8 + 9 = 22.
Divide: O(1). Conquer: 2T(n/2)
Combine: ???
The University of Sydney
Page 34

Counting Inversions: Combine
Combine: count blue-green inversions
– Assume each half is sorted.
– Count inversions where ai and aj are in different halves. – Merge two sorted halves into sorted whole.
3
7
10
14
18
19
2
11
16
17
23
25
The University of Sydney
Page 35
632200
5 blue-blue inversions 8 green-green inversions
How many blue-green inversions?

Counting Inversions: Combine
Combine: count blue-green inversions
– Assume each half is sorted.
– Count inversions where ai and aj are in different halves. – Merge two sorted halves into sorted whole.
632200
13blue-greeninversions: 6+3+2+2+0+0
Count: O(n) Merge: O(n)
3
7
10
14
18
19
2
11
16
17
23
25
2
3
7
10
11
14
16
17
18
19
23
25
Time: T(n) = 2T(n/2) + O(n) = O(n log n) The University of Sydney
Page 36

Proof by unrolling*
ìc
T(n)=ïí 2T (n / 2) + cn
if n=1 otherwise
ïî%”$”# ! sorting both halves merging
T(n)
T(n/2)
T(n/4) T(n/4)
T(n/2k)
T(1) T(1) T(1) T(1)
1 (of size n) ® cn
2 (of size n/2) ® cn
4 (of size n/4) ® cn
log2n
…
2k (of size n/2k) ® cn …
n(of size 1) ® cn cn log2n Page 37
T(n/4)
T(n/2) T(n/4)
T(1) T(1)
The University of Sydney
T(1) T(1)

The master method*
The master method applies to recurrences of the form
T(n) = a·T(n/b) + f(n) ,
where a 3 1, b > 1, and f is asymptotically positive.
The University of Sydney Page 38

T(n) = a·T(n/b) + f(n)
size n cost f(n)
size n/b cost a·f(n/b)
size (n/b2) cost a2·f(n/b2)
size 1
cost w·T(1)
Branching factor a
height logb n
The University of Sydney
width w = alogb n = nlogb a
Page 39

Summary: Divide-and-Conquer
– Algorithm:
– Break up problem into several parts.
– Solve each part recursively.
– Combine solutions to sub-problems into overall solution.
– Complexity analysis: Solve recurrence – Unrolling
– Master Method
– Correctness: Induction
– Problems
The University of Sydney
–
–
Merge Sort Closest pair Multiplication
–
Page 40

Lectures 6-7:
Dynamic Programming
The University of Sydney
Page 41
Fast Fourier Transform

Dynamic programming
1. Definesubproblems.
2. Write a recurrence (include base cases).
3. Prove that the recurrence is correct. Usually case-by-case. May
require an induction proof, but usually easy to prove.
4. Prove the algorithm evaluates the recurrence. Values computed in correct order.
5. Prove the algorithm is correct. The University of Sydney
Page 42
42

Weighted Interval Scheduling
– Weighted interval scheduling problem.
– Job j starts at sj, finishes at fj, and has weight or value vj .
– Two jobs compatible if they don’t overlap.
– Goal: find maximum weight subset of mutually compatible jobs.
b
a
c
d
e
f
g
h
0 1 2 3 4 5 6 7 8 9 10 11 The University of Sydney
Time
Page 43

Weighted Interval Scheduling
Notation. Label jobs by finishing time: f1 £ f2 £ . . . £ fn .
Def. p(j) = largest index i < j such that job i is compatible with j. Ex: p(8)=5,p(7)=3,p(2)=0. 1 2 3 4 5 6 7 80 1 2 3 4 5 6 7 8 9 10 11 The University of SydneyTimePage 44 Dynamic Programming – Step 1 Step 1: Define subproblemsOPT(j) = value of optimal solution to the problem consisting of job requests 1, 2, …, j.The University of SydneyPage 45 Dynamic Programming – Step 2 Step 2: Find recurrences– Case 1: OPT selects job j.• can’tuseincompatiblejobs{p(j)+1,p(j)+2,…,j-1}• must include optimal solution to problem consisting of remaining compatible jobs 1, 2, …, p(j)– Case 2: OPT does not select job j.• must include optimal solution to problem consisting ofremaining compatible jobs 1, 2, …, j-1OPT(j) = max {vj + OPT (p(j)), OPT(j-1)} Case 1 Case 2The University of SydneyPage 46 Dynamic Programming – Step 3 Step 3: Solve the base casesOPT(0) = 0 OPT(j)=ìí 0 if j=0 îmax{vj +OPT(p(j)), OPT(j-1)} otherwiseThe University of SydneyPage 47Done…more or less Knapsack Problem– Knapsackproblem.– Givennobjectsanda”knapsack.”– Item i weighs wi > 0 kilograms and has value vi > 0. – KnapsackhascapacityofWkilograms.
– Goal: fill knapsack so as to maximize total value.
W = 11
Item
Value
Weight
1
1
1
2
6
2
3
18
5
4
22
6
5
28
7
The University of Sydney
Page 48

Dynamic Programming – Step 1 Step 1: Define subproblems
OPT(i, w) = max profit with subset of items 1, …, i with weight limit w.
The University of Sydney
Page 49

Dynamic Programming – Step 2 Step 2: Find recurrences
– Case 1: OPT does not select item i.
• OPT selects best of { 1, 2, …, i-1 } using weight limit w
– Case 2: OPT selects item i.
• newweightlimit=w–wi
• OPT selects best of { 1, 2, …, i–1 } using this new weight limit
If wi>w
OPT(i,w) = OPT (i-1,w)
otherwise
OPT(i,w) = max { vi + OPT (i-1,w-wi), OPT(i-1,w) }
The University of Sydney
Page 50

Recap: Dynamic Programming – Step 3 Step 3: Solve the base cases
OPT(0,w) = 0
ì0 if i=0 OPT(i,w)=ïOPT(i-1,w) if i>0andw >w
í
i
ïmax{OPT(i-1,w),v+OPT(i-1,w-w)} otherwise îii
The University of Sydney
Page 51
Done…more or less

Knapsack Problem: Running Time
– Running time: Q(nW).
– Not polynomial in input size!
– “Pseudo-polynomial.”
– Decision version of Knapsack is NP-complete.
– Observe that in the reduction of vertex cover to subset sum, the numbers are exponential in the size of the graph!
The University of Sydney Page 52

Vertex Cover Reduces to Subset Sum
Proof: Given an instance (G, k) of VERTEX-COVER, construct an instance (S, t) of SUBSET-SUM that has a subset of S summing to t iff G has a vertex cover of
size at least k.
Number edges from 0 to |E|-1. Set S of integers:
– For the i-th edge, add an integer bi
– For each vertex v, add an integer av
bi = 4i
av = 4|E| + X 4i
0
xyz
1
t = k · 4|E| +
The University of Sydney i=0
2 · 4i
Page 53
i:i-th edge is incident to v
az = 1104 ay = 1114
ax = 1014
|EX|1
t = 1224
k=1
b0 = 0014
b1 = 0104

Shortest Paths
– Shortest path problem. Given a directed graph G = (V, E), with edge weights cvw, find shortest path from node s to node t.
allow negative weights
2 10 3
9
s
18
30
5
-8
20
7
6
6
15
-16 6
4 19
6 16
t
11
44
The University of Sydney
Page 54

Shortest Paths: Dynamic Programming
Step 1: OPT(i, v) = length of shortest v-t path P using at most i edges.
Step 2:
Case 1: P uses at most i-1 edges. • OPT(i, v) = OPT(i-1, v)
Case 2: P uses exactly i edges.
• if (v, w) is first edge, then OPT uses (v, w), and then selects
best w-t path using at most i-1 edges
Step 3: OPT(0,t) = 0 and OPT(0,v≠t) = ∞
0 if i=0 and v=t OPT(i,v) = ∞ if i=0 and v≠t
min{OPT(i-1,v), min [OPT(i-1,w)+cvw] } otherwise
The University of Sydney
(v,w)ÎE
Page 55

Dynamic Programming Summary I
Algorithm – 3 steps:
1. Definingsubproblems
The University of Sydney
Page 56
2. 3.
Finding recurrences Solving the base cases
56

Dynamic Programming Summary II
– 1D dynamic programming
– Weighted interval scheduling
– Segmented Least Squares
– Maximum-sum contiguous subarray – Longest increasing subsequence
– 2D dynamic programming – Knapsack
– Shortest path
– Dynamic programming over intervals
– RNA Secondary Structure The University of Sydney
Page 57

Lectures 8-9: Flow networks
The University of Sydney
Page 58

Flow network*
– Abstraction for material flowing through the edges. – G = (V, E) = directed graph, no parallel edges.
– Two distinguished nodes: s = source, t = sink.
– c(e) = capacity of edge e.
295
10
15 15
sources 5 3 8 6 10 tsink
4
10
capacity
The University of Sydney
Page 59
15
46
10
15 4 30 7

Flows*
– Definition: An s-t flow is a function that satisfies: – For each e Î E: 0 £ f(e) £ c(e)
(capacity) (conservation)
å f (e) . e out of s
6
10
– For each v Î V – {s, t}: å f(e) = e in to v
– Definition: The value of a flow f is: 6
å f(e) 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
Value =P2ag4e 60

Maximum Flow Problem*
– Max flow problem. Find s-t 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
Value =P2ag8e 61

Cuts*
Definitions:
– Ans-tcutisapartition(A,B)ofVwithsÎAandtÎB.
– The capacity of a cut (A, B) is: cap(A, B) = 295
å c(e) e out of A
10
4
15 15
10
s 5 3 8 6 10 t A
15
46
10
15 4 30 7
Capacity = 10 + 5 + 15
The University of Sydney
= 30
Page 62

Cuts
Definitions:
– Ans-tcutisapartition(A,B)ofVwithsÎAandtÎB.
– The capacity of a cut (A, B) is: cap(A, B) = 2 9 5
10
å c(e) 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
Capacity = 9 + 15 + 8 + 30
= 62
Page 63

Flows and Cuts*
– Flow value lemma. Let f be any flow, and let (A, B) be any s-t cut. Then, the net flow sent across the cut is equal to the amount
leaving s.
åf(e) – åf(e) = v(f) 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
Value = 6 + 0 + 8 – 1 + 11 = 24 Page 64
The University of Sydney
4 30 7

Ford-Fulkerson
Ford-Fulkerson(G,s,t) { foreach e Î E
f(e) ¬ 0
Gf ¬ residual graph
while (there exists augmenting path P in Gf){ f ¬ Augment(f,P)
update Gf }
return f }
Augment(f,P) {
b ¬ bottleneck(P,f) foreach e =(u,v) Î P {
if e is a forward edge then
increase f(e) in G by b
else (e is a backward edge)
decrease f(e) in G by b
}
return f }
Page 65
The University of Sydney

Residual Graph*
– Originaledge: e=(u,v) ÎE. – Flowf(e),capacityc(e).
– Residualedge.
– “Undo”flowsent.
– e=(u,v)andeR =(v,u). – Residualcapacity:
c(e)=ìíc(e)-f(e) ifeÎE
f î f (e) if eR Î E
– Residual graph: Gf = (V, Ef ).
– Residualedgeswithpositiveresidualcapacity. – Ef ={e:f(e) 0}.
capacity
u 17 v
6
flow
residualcapacity
u 11 v
6
residual capacity
The University of Sydney
Page 66

Ford-Fulkerson 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 value = 0
244
residual capacity 10
Gf:
10
2
86
s 10 3 9 5 10 t
The University of Sydney
Page 67

Ford-Fulkerson Algorithm
G:
0
2 4 4
1 0 X8 8
10208 6010
s 10 3 X 5 t 9 10
X
0 2 02 10X8
0
2 4 4
Flow value = 8
Gf:
8
2
86
10
2 s 10 3
9 5 2 t 8
The University of Sydney
Page 68

Max-Flow Min-Cut Theorem*
– Augmenting path theorem: Flow f is a max flow if and only if there are no augmenting paths in the residual graph.
– Max-flow min-cut theorem: The value of the max flow is equal to the value of the min cut. [Ford-Fulkerson 1956]
– Integrality. If all capacities are integers then every flow value f(e) and every residual capacities cf (e) remains an integer throughout the algorithm.
The University of Sydney Page 69

Running Times*
Theorem. Ford-Fulkerson runs in O(mF) time.
Theorem. Ford–Fulkerson with maximum bottleneck augmenting path finds a max flow in O(m2 log F) time. [Covered in last week’s slides]
Theorem. Ford–Fulkerson with shortest augmenting path finds a max flow in O(nm2) time. [3927 Lecture]
Theorem. There is an algorithm that finds a max flow in O(nm) time. [Orlin 2012]
The University of Sydney Page 70

Bipartite Matching*
– Input: undirected, bipartite graph G = (L È R, E).
– M Í E is a matching if each node appears in at most
one edge in M.
– Max matching: find a max cardinality matching.
1 1′ 2 2′
3 3′ 4 4′
max matching 1-1′, 2-2′, 3-3‘, 5-5′
5 5′
The University of Sydney L
R Page 71

Bipartite Matching
Max flow formulation.
– Create digraph G’ = (L È R È {s, t}, E’ ).
– Direct all edges from L to R, and assign unit capacity.
– Add source s, and unit capacity edges from s to each node in L. – Add sink t, and unit capacity edges from each node in R to t.
G’
1
1 1 1′ 2 2′
3 3′ 4 4′
1
s
t
The University of Sydney
L 5 5′ R
Page 72

Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G Û value of max flow in G’. Proof: Þ
– Assume max matching M has cardinality k.
– Consider a flow f that sends 1 unit along each of the k paths, defined by
the edges in M.
– fisaflow,andithasvaluek. ■
1 1 1′
2 2′ 12 2’1
G3 3’s33’tG’ 4 4′ 4 4′
1 1′
The Univers5ity of Sydney 5′ 5 5′ Page 73

Bipartite Matching: Proof of Correctness
Theorem: Max cardinality matching in G Û value of max flow in G’. Proof: Ü
– LetfbeamaxflowinG’ofvaluek.
– Integrality theorem Þ k is integral so f(e) is 0 or 1. – ConsiderM=setofedgesfromLtoRwithf(e)=1.
• each node in L and R participates in at most one edge in M • |M|=k: considercut(LÈs,RÈt)
1 1 1′
12 2’1 2 2′
s 3 3′ t 3 3′ 4 4′ 4 4′
G’5 5′ 5 5’G
1 1′
The University of Sydney Page 74

Edge Disjoint Paths
Disjoint path problem:
Given a digraph G = (V, E) and two nodes s and t, find the max number of edge-disjoint s-t paths.
Definition: Two paths are edge-disjoint if they have no edge in common.
25
s36t
47
The University of Sydney
Page 75

Edge Disjoint Paths
Disjoint path problem:
Given a digraph G = (V, E) and two nodes s and t, find the max number of edge-disjoint s-t paths.
Definition: Two paths are edge-disjoint if they have no edge in common.
25
s36t
47
The University of Sydney
Page 76

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 77

Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111
111
s1 1t
1
1
1 1
11
Theorem: Max number edge-disjoint s-t paths equals max flow value.
Proof: Þ
– Suppose there are k edge-disjoint paths P1, . . . , Pk.
– Set f(e) = 1 if e participates in some path Pi ; else set f(e) = 0. – Since paths are edge-disjoint, f is a flow of value k.
The University of Sydney Page 78

Edge Disjoint Paths
Max flow formulation: assign unit capacity to every edge. 111
111
s1 1t
1
1
1 1
11
Theorem: Max number edge-disjoint s-t paths equals max flow value. Proof: Ü
– Suppose max flow value is k.
– Integrality theorem Þ there exists 0-1 flow f of value k. – Consider edge (s, u) with f(s, u) = 1.
• by conservation, there exists an edge (u, v) with f(u, v) = 1
• continue until reach t, always choosing a new edge
– Produces k (not necessarily simple) edge-disjoint paths. ▪ The University of Sydney
Page 79

Summary: Flow networks
– Properties
– Max-flow min-cut theorem
– Integrality lemma –…
– Ford-Fulkerson’s algorithm – Problems
– Max flow
– Min cut
– Matching
– Disjoint edge paths –…
The University of Sydney
Page 80

Lecture 10:
NP and Computational Intractability
The University of Sydney
Page 81

Definition of the class NP
Class NP: Decision problems for which YES-instances have a poly-time certifier.
Certification algorithm intuition.
– Certifier views things from “managerial” viewpoint.
– Certifier does not solve the problem by its own;
rather, it checks if a proposed proof t is a valid solution.
Definition: Algorithm C(s,t) is a certifier for problem X if for every input instance s and proposed proof t, C(s, t) = `yes’ if and only if t is a valid solution to s.
“certificate” or “witness”
The University of Sydney
Page 82

Class NP-hard
Class NP-complete: A problem in NP such that every problem in NP polynomially reduces to it.
Class NP-hard:
A decision problem such that every problem in NP polynomially reduces to it.
not necessarily in NP
The University of Sydney Page 83

Establishing NP-Completeness
Remark: Once we establish first “natural” NP-complete problem, others fall like dominoes.
Recipe to establish NP-completeness of problem Y. – Step1. ShowthatYisinNP.
– Step 2. Choose an NP-complete problem X. – Step 3. Prove that X £ p Y.
Justification: If X is an NP-complete problem, and Y is a problem in NP with the property that X £ P Y then Y is NP-complete.
Proof: LetWbeanyprobleminNP. ThenW £P X £P Y. – Bytransitivity,W£P Y.
– Hence Y is NP-complete. ▪ The University of Sydney
by definition of NP-complete
by assumption
Page 84

Reduction Template for Decision Problems (aka Karp reduction)*
Algorithm for X
Instance of Y
f(I)
Yes for f(I) No for f(I)
Transforms instance of X to instance of Y
Algorithm for Y
Instance of X
I
Yes for I No for I
Step 2
Step 1
Step 1: Construct a polynomial-time algorithm that transforms instance I of X to an instance f(I) of Y
Step 2: Prove correctness, which boils down to showing
Answer for I is Yes iff answer for f(I) is Yes
Proof usually done by transforming certificate for I to certificate
for f(I) and vice versa
The University of Sydney Page 85

Summary
§ Polynomial time reductions
3-SAT £P DIR HAMILTONIAN CYCLE £P HAMILTONIAN CYCLE £P TSP 3-SAT £P INDEPENDENT-SET £P VERTEX-COVER £P SET-COVER
§ Complexity classes:
P: Decision problems for which there is a poly-time algorithm.
NP: Decision problems for which there is a poly-time certifier. NP-complete: A problem in NP such that every problem in NP polynomial
reduces to it.
NP-hard: A problem such that every problem in NP polynomial reduces to it.
§ Lots of problems are NP-complete
See https://www.nada.kth.se/~viggo/wwwcompendium/
The University of Sydney
Page 86

Lecture 11:
Coping with hardness
The University of Sydney
Page 87

Summary
NP-complete problems show up in many applications. There are different approaches to cope with it:
• Approximation algorithms
• Restricted cases (trees, bipartite graphs, small solution…)
• Randomized algorithms •…
Each approach has its pros and cons.
The University of Sydney
Page 88

Exam
Time: 10 minutes reading time 2.5 hours writing
Number of problems: 6 (ordered from easiest to hardest…imo) For Question 6 there is one for comp3027
and one for comp3927. See Practice Final on Ed.
The University of Sydney
Page 89

More algorithms?
– COMP3530:DiscreteOptimization(2019S2) Lecturer: Julian Mestre
– COMP5045:ComputationalGeometry(2020S1) Lecturer: Joachim Gudmundsson
– Otheropportunities:
– SSP, summer projects, informal reading
Please get in touch with us for more information The University of Sydney
Page 90

Please remember to fill in the unit of study evaluation
https://student-surveys.sydney.edu.au/students/
What was good? What was bad?
Thanks for taking the class! Good luck on the exam!
The University of Sydney
Page 91