· 8 years ago · Apr 08, 2018, 11:36 AM
1Major Topics:
2 - Dynamic Programming
3 - Network Flow
4
5~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
61. Dynamic Programming
7
8 Sources:
9 Lecture - Week 7, 8
10 Algorithm Design - Chapter 6
11
12 Overview:
13 To solve a larger problem, we solve smaller overlapping subproblems and
14 store their values in a table.
15 DP is applicable when subproblems greatly overlap. Therefore, divide and
16 conquer does not count as DP. Consider mergesort.
17 DP is not greedy. DP is optimized brute force. DP tries every choice before
18 solving the problem. It is much more expensive than Greedy.
19
20 Key Attributes:
21 Optimal Substructure:
22 Solution can be obtained by the combination of optimal solutions to its
23 subproblems. Such optimal substructures are usually described
24 recursively
25
26 Overlapping Subproblems
27 Space of subproblems must be small, so an algorithm solving the problem
28 should solve all the subproblems over and over
29
30 Methods:
31 Memoization:
32 Optimization technique to speed up recursive programs by storing the
33 intermediate results
34 Filling up a table recursively in a top-down manner
35
36 Tabulation:
37 Filling up a table iteratively in a bottom up manner.
38 This implementation is preferred since it takes less time and memory,
39 However, nowadays compilers are good at optimizing recursive functions.
40
41 Definition:
42
43 I. Pseudo-Polynomial
44 A numeric algorithm runs in pseudo-polynomial time if its running time is
45 polynomial in the numeric value of input, but is exponential in length of
46 input.
47 T(n) = Θ(nW)
48 For the knapsack problem, the input size capacity W is measured in bits,
49 so the actual complexity is given by
50 T(n) = Θ(n*2^(input size of W))
51 Thus, if you change W by one bit, the amount of work (table size) will
52 double.
53
54 Algorithms:
55
56 I. Bellman Ford
57
58 Notes:
59 - See Shortest Path (Bellman Ford)
60
61 II. Floyd Warshall
62
63 Notes:
64 - See All Pairs Shortest Path (Floyd Warshall)
65
66 Problems:
67
68 I. Fibonacci Numbers
69
70 Statement:
71 Fibonacci number F_n is defined as the sum of two previous Fibonacci
72 numbers:
73 F_n = F_n-1 + F_n-2
74
75 Subproblem:
76 Smaller n Fibonacci numbers
77
78 Recurrence:
79 OPT[n] = OPT[n-1] + OPT[n-2]
80 OPT[0] = 1
81 OPT[1] = 1
82
83 Table:
84 Array of size N
85 Solution is in the last index
86 0 1 2 3 4 5 6 7
87 |1 |1 |2 |3 |5 |8 |13|21|
88
89 Implementation:
90 Memoization:
91 int table[50]; // initialize to zero
92 table[0] = table[1] = 1;
93 int fib(int n) {
94 if table[n] != 0
95 return table[n]
96 else
97 table[n] = fib(n-1) + fib(n-2)
98 return table[n] }
99 Tabulation:
100 int table[n]; // initialize to zero
101 int fib(int n) {
102 table[0] = table[1] = 1;
103 for i in range 2, n:
104 table[i] = table[i-1] + table[i-2]
105 return table[n] }
106
107 Complexity:
108 Memoization: T(n) = T(n-1) + Θ(n) = Θ(n^2)
109 - We only have to compute one recursive call and the second is a table
110 look up
111 - Each addition operation will take O(n) time. Assuming numbers are so
112 big that they must be added bit by bit, we will need to add
113 log(ψ^n) bits -> O(n) time.
114 Tabulation: O(n^2)
115 - n loops with an addition
116 - Each addition operation will take O(n) time. Assuming numbers are so
117 big that they must be added bit by bit, we will need to add
118 log(ψ^n) bits -> O(n) time.
119 - Faster than Memoization by a constant factor due to running from
120 bottom up, rather top down and then bottom up
121
122 II. Money Changing Problem
123
124 Statement:
125 You are to compute the minimum number of coins needed to make change for
126 a given amount m. Assume that we have an unlimited supply of coins.
127 All denominations d_k are sorted in ascending order:
128 1 = d_1 < d_2 < ... < d_n
129
130 Subproblem:
131 Let OPT[v,c] be the least number of coins to represent some amount
132 v (0 <= v <= m), using the first c (1 <= c <= n) denominations.
133
134 Recurrence:
135 OPT[v,c] = MIN{ OPT[v,c-1],
136 OPT[v-c_val, c] + 1 }
137 OPT[v,c] = OPT[v,c-1], if v < c_val
138 OPT[0,c] = 0
139 OPT[v,1] = v
140
141 Table:
142 NxM table
143 Solution is at bottom right corner
144 0 1 2 3 4 5 6 7 8
145 1|0 |1 |2 |3 |4 |5 |6 |7 |8 |
146 4|0 |1 |2 |3 |1 |2 |3 |4 |2 |
147 6|0 |1 |2 |3 |1 |2 |1 |2 |2 |
148
149 Backtrack:
150 model = []
151 for i = m, j = n:
152 if 1 + OPT[i - j_val, j] < OPT[i, j-1]:
153 model.append(j_val)
154 i = i - j_val
155 else:
156 j = j-1
157 return model
158
159 Complexity:
160 Solving: O(mn) * O(C) = O(mn)
161 Table size * work at each cell
162 Backtrack: O(m+n)
163 Worst case is climbing stairs through cells
164
165 Key Points:
166 - Cannot be solved optimally by greedy algorithm for some non-US
167 denominations
168 - Can be solved with linear space complexity
169 - Similar to knapsack problem, however since we allow repetition of
170 items we replace v-1 with v in our recurrence formula
171
172 III. 0-1 Knapsack Problem
173
174 Statement:
175 Given a set of unique items, each with a weight and a value, determine
176 the subset of items such that the total weight is less than or equal to
177 a given capacity and the total value is as large as possible.
178
179 Subproblem:
180 Let OPT[i, w] be the largest value for a knapsack with capacity
181 w (0<=w<=W), using the first i (0<=i<=N) items
182
183 Recurrence:
184 OPT[i, w] = MAX{ i_v + OPT[i-1, w - i_w],
185 OPT[i-1, w]}
186 OPT[i, w] = OPT[i-1, w], if i_w > w
187 OPT[0, w] = 0
188 OPT[i, 0] = 0
189
190 Table:
191 NxW table
192 Solution is at bottom right corner
193 0 1 2 3 4 5
194 w,v 0|0 |0 |0 |0 |0 |0 |
195 2,3 1|0 |0 |3 |3 |3 |3 |
196 3,4 1|0 |0 |3 |4 |4 |7 |
197 4,5 1|0 |0 |3 |4 |5 |7 |
198 5,6 1|0 |0 |3 |4 |5 |7 |
199
200 Implementation:
201 int knapsack(int cap, int w[], int v[], int n) {
202 int OPT[n+1][cap+1];
203 for (k = 0; k <= n; k++) {
204 for (w = 0; w <= cap; w++) {
205 if (k==0 || w==0) OPT[k][w] = 0;
206 elif (w[k-1] > w) OPT[k][w] = OPT[k-1][w];
207 else OPT[k][w] = max(v[k-1] + OPT[k-1][w-w[k-1]], OPT[k-1][w])
208 }
209 }
210 return OPT[n][cap]
211 }
212
213 Backtrack:
214
215 Complexity:
216 Solve:
217 O(N+1*W+1) * O(1) = O(N*W)
218 Table size * work at cells
219 Note: This is a pseudo-polynomial algorithm because it depends on the
220 value of W, which could be much bigger than n.
221 To show this we can compute the total input size:
222 1. The number of items is n; input size O(log n) bits
223 2. n weights; each cannot exceed W, so the total number of bits
224 is O(nlogW)
225 3. n values; let the largest be V, then the total number of bits
226 is O(nlogV)
227 Summing up: total input size is O(n(log W + log V))
228 Compare this to running time: O(nW)
229 O(nw) is not polynomial in input size O(nlogW)
230
231 Key Points:
232 - Fractional Knapsack problem can be solved with greedy algorithm
233 - Can be solved with linear space complexity
234 - Since we do not allow repetition of items we must use i-1 instead of i
235 in our recurrence formula
236 - Cannot be solved in polynomial time
237
238 IV. Longest Common Subsequence
239
240 Statement:
241 We are given two strings: string S of length n and string T of length m.
242 Our goal is to produce their longest common subsequence.
243
244 Subproblem:
245 Let L[i, j] be the longest common subsequence of string S from [1..i]
246 and string T from [1..j]
247
248 Recurrence:
249 LCS[i, j] = 1 + LCS[i-1, j-1], if S[i]=T[j]
250 LCS[i, j] = max(LCS[i-1, j], LCS[i, j-1]) if S[i]≠T[i]
251 LCS[i, 0] = 0
252 LCS[0, j] = 0
253
254 Table:
255 N+1xM+1 table
256 Answer in bottom left
257 - B A C B A D
258 -|0 |0 |0 |0 |0 |0 |0 |
259 A|0 |0 |1 |1 |1 |1 |1 |
260 B|0 |1 |1 |1 |2 |2 |2 |
261 A|0 |1 |2 |2 |2 |3 |3 |
262 Z|0 |1 |2 |2 |2 |3 |3 |
263 D|0 |1 |2 |2 |2 |3 |4 |
264 C|0 |1 |2 |3 |3 |3 |4 |
265
266 Implementation:
267 int LCS(char[] S, int n, char[] T, int m) {
268 int table[n+1, m+1];
269 table[0..n, 0] = table[0, 0..m] = 0
270
271 for(int i; i <= n; i++) {
272 for(int j; j<=m; j++) {
273 if S[i] == T[j]
274 table[i, j] = 1 + table[i-1, j-1];
275 else
276 table[i, j] = max(table[i-1, j], table[i, j-1]);
277 }
278 }
279 return table[n, m]
280 }
281
282 Backtrack:
283 Start from bottom right.
284 If the cell above or to the left contains a value equal to the value
285 in the cell, then move to that cell
286 If both values are less than the value in the current cell, then move
287 diagonally and save S[n] to the model
288
289 Complexity:
290 O(mn)
291
292 Key Points:
293 - We can solve this with O(n) space but we won't be able to reconstruct
294 the solution
295
296 V. Shortest Path (Bellman Ford)
297
298 Statement:
299 Given a graph G with weighted edges (positive or negative), find the
300 shortest path from s to any vertex v.
301
302 Subproblem:
303 D[v, k] denotes the length of the shortest path from s to v that uses
304 at most k edges.
305
306 Recurrence:
307 Case 1: Path uses at most k-1 edges, D[v, k] = D[v, k-1]
308 Case 2: Path uses at most k edges.
309 - If w is adjacent to v, take (w, v) edge, and then select the best
310 s-w path that uses at most k-1 edges (check all vertices adjacent
311 to v), D[v, k] = min_(w,v)inE(D[w, k-1] + c_wv)
312
313 D[v,k] = min(D[v, k-1], min_(w,v)inE(D[w, k-1] + c_wv))
314 D[v,k] = 0, if k = 0 & v = s
315 D[v,k] = ∞, if k = 0 & v ≠s
316
317 Table:
318 VxK table
319
320 Implementation:
321 for k=1 to V-1:
322 for each v in V:
323 for each edge (w,v) in E:
324 D[v,k] = min(D[v, k-1], D[w, k-1] + c_wv))
325
326 Complexity:
327 O(VE)
328
329 Key Points:
330 - Can be done dynamically by finding distance from t for first neighbor
331 on path to T
332 - Bellman Ford can handle negative weights
333 - Number of edges K should be less than the number of vertices V
334 - Bellman Ford can be used to find a negative cycle if you perform one
335 more cycle after reaching v-1 edges. If anything changes on the
336 second cycle, we have a negative cycle
337
338 VI. All Pairs Shortest Path (Floyd Warshall)
339
340 Statement:
341 Given a graph G with weighted edges (positive or negative) find the
342 shortest path between each pair of vertices
343
344 Subproblem:
345 Let D[i, j, k] be the shortest path from i to j for which all
346 intermediate vertices can only be chosen from the set {1, 2,..., k}.
347 A shortest path does not contain the same vertex more than once.
348
349 Recurrence:
350 D[i, j, k] = min_u(D[i, u, k-1] + D[u, j, k-1], D[i, j, k-1])
351 D[i, j, 0] = c(i, j)
352
353 Implementation:
354 D[i, j, 0] = c[i, j] for all i and j
355 for k=1..V:
356 for i=1..V:
357 for j=1..V:
358 D[i, j, k] = min (D[i, j, k-1], D[i, k, k-1] + D[k, j, k-1])
359
360 Table:
361 V-1 VxV tables
362 V-1th table is optimal path for each node
363
364 Backtrack:
365 To extract shortest path:
366 Create a new matrix P[i,j], whenever we discover that the shortest
367 path from i to j passes through an intermediate vertex k, we set
368 P[i,j] = k.
369 Recursively compute the shortest path from i to k and from k to j
370
371 Key Points:
372 - O(V^3) vs Bellman Ford O(EV^2)
373
374 VII. Weighted Interval
375
376 Statement:
377 Given N intervals where every job is given a start time, s, a finish
378 time t, and a weight w. Maximize the weight.
379
380 Subproblem:
381 C[i] is the maximum weight that can be obtained from the first i jobs.
382 p(i) uses binary search the interval with the latest finishing time from
383 the set of intervals that does not overlap with i.
384
385 Recurrence:
386 C[i] = MAX(w_i + C[p(i)], C[i-1])
387 C[0] = 0
388
389 Table:
390 Array of size N.
391 Max value is at the last index.
392
393 Complexity:
394 O(n) * O(logn) = O(nlogn)
395 Array Size & Binary Search runtime
396
397 Key Points:
398 - Must sort intervals by finish time
399
400 Tips:
401 - To generate recursion formula, try to start with a toy problem or try
402 drawing the problem
403 - To verify complexity, write out the implementation
404 - Don't forget edge cases for recurrence
405
406 //TODO Tree
407~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
4082. Network Flow
409
410 Sources:
411 Lecture - Week 9, 10
412 Algorithm Design - Chapter 7
413
414 Definitions:
415
416 I. Flow Network
417 Directed graph G = (V,E) with the following features:
418 - Each edge e has a non-negative capacity c_e
419 - Has a single source node s in V
420 - Has a single sink node t in V
421
422 II. Steady State Flow
423 Flow that does not change over time
424 The value of flow v(f) is defined as follows:
425 v(f) = Σ f(e), outOf(s)
426
427 III. Residual Graph
428 G_f is the residual graph of G with the following definition:
429 - G_f has the same set of nodes as G
430 - for each edge e with f(e) < c_e, we include e in G_f with capacity
431 c_e - f(e)
432 - for each edge e with f(e) > 0, we include edge e' (opposite direction
433 to e) in G_f with f(e) units of capacity
434
435 IV. Bottleneck
436 If p is a simple path from s to t in G_f, then bottleneck(p) is the
437 minimum residual capacity of any edge on P.
438
439 V. Strongly Polynomial
440 An algorithm runs in strongly polynomial time if the number of operations
441 is bounded by a polynomial in the number of integers in the input.
442 This is relevant if input consists of integers.
443
444 VI. Bipartite Graph
445 A bipartite graph G(V,E) is an undirected graph whose node set can be
446 partitioned as V = X U Y with property that every edge e in E has one
447 end in X and the other in Y.
448
449 VII. Matching
450 A matching M in G is a subset of the edges M ≤ E such that each node
451 appears in at most one edge in M.
452
453 VIII. Edge Disjoint
454 A set of paths is edge-disjoint if their edge sets are disjoint
455
456 XI. Node Disjoint
457 A set of paths is node-disjoint if their node sets (except for starting
458 and ending) are disjoint
459
460 X. Circulation
461 A circulation with demand {d_v} is a function f that assigns non-negative
462 real numbers to each edge and satisfies:
463 1. Capacity Conditions
464 for each edge e in E: 0 <= f(e) <= c_e
465 2. Demand Conditions
466 for each node v in V: f_in(v) = f_out(v) = d_v
467
468 Algorithms:
469
470 I. Ford-Fulkerson:
471
472 Assumptions:
473 - no edges enter source (s) or leave sink (t)
474 - at least one edge connected to each node
475 Note: This simplifies complexity analysis O(m+n) => O(m)
476 - all capacities are integers
477
478 Notation:
479 We call f(e) flow through edge e. f(e) has the following properties:
480 1. Capacity Constraint:
481 for each edge e in E, 0<=f(e)<=c(e)
482 2. Conservation of Flow:
483 Σ f(e), into(v) = Σ f(e), outOf(v), except for s & t
484
485 Implementation:
486 Max-Flow(G,s,t,c):
487 Initially f(e)=0 for all e in G
488 While there is an s-t path in the residual graph G_f
489 Let P be a simple s-t path in G_f
490 f' = augment(f, P)
491 Update f to be f'
492 Update G_f to G_f'
493 Endwhile
494 Return f
495
496 Augment(f, P):
497 Let b = bottleneck(P,f)
498 For each edge (u, v) in P:
499 If e = (u,v) is a forward edge:
500 increase f(e) in G by b
501 Else e = (u,v) is a backward edge:
502 Let e = (v,u)
503 decrease f(e) in G by b
504 Endif
505 Endfor
506 Return f
507
508 Complexity:
509 O(Cm)
510
511 Key Points:
512 - The flow going through the network at every step is integer valued
513 - Pseudo-polynomial
514
515 II. Scaled Ford-Fulkerson:
516
517 Assumptions:
518 See Ford-Fulkerson:Assumptions
519
520 Notation:
521 We call f(e) flow through edge e. f(e) has the following properties:
522 1. Capacity Constraint:
523 for each edge e in E, 0<=f(e)<=c(e)
524 2. Conservation of Flow:
525 Σ f(e), into(v) = Σ f(e), outOf(v), except for s & t
526 Let ∆ be the largest power of 2 that is no larger than the max
527 capacity out of s
528
529 Implementation:
530 Scaled-FF(G,s,t,c):
531 Initially f(e)=0 for all e in G
532 Set ∆ = largest power of 2 that is <= max capacity out of s
533 While ∆ >= 1
534 While there is an s-t path in the residual graph G_f
535 Let P be a simple s-t path in G_f
536 f' = augment(f, P)
537 Update f to be f'
538 Update G_f to G_f'
539 Endwhile
540 ∆ = ∆/2
541 Endwhile
542 Return f
543
544 Complexity:
545 O(logCm^2)
546 Outer while = O(logC), Inner while = O(m), Inner function = O(m)
547
548 Key Points:
549 - During the ∆ scaling phase, each augmentation the flow increases by
550 at least ∆
551 - Weakly Polynomial
552
553 III. Edmunds-Karp (Short Pipes):
554
555 Background:
556 Same as Ford-Fulkerson, except that each augmenting path must be a
557 shortest path with available capacity.
558
559 Complexity:
560 O(nm^2)
561
562 Key Points:
563 - Strongly polynomial
564
565 IV. Edmunds-Karp (Fat Pipes):
566
567 Background:
568 Same as Ford-Fulkerson, except choose the augmenting path with the
569 largest bottleneck value.
570
571 Complexity:
572 O(E^2 logE logf)
573 O(E log V) -> Primm's variant to find augmentation paths
574
575 Key Points:
576 - Weakly polynomial
577
578 Problems:
579
580 I. Max Flow
581
582 Statement:
583 Given a flow network G, find an s-t flow with max value.
584
585 Strategy:
586 1. Find a path from s to t
587 2. Find the bottleneck value for this path
588 3. Push flow through this path with value equal to bottleneck value
589 4. Repeat
590
591 Key Points:
592 - Max Flow <= Capacity of any (A, B) cut
593
594 II. Min Cut
595
596 Statement:
597 Given a flow network G, find the min-cut of an s-t flow with max value.
598
599 Strategy:
600 1. Find max flow
601 2. Construct residual graph G_f
602 3. Run BFS to find reachable nodes from s. Let the set of these nodes
603 be called A.
604 4. Let B = V - A
605
606 Key Points
607 - Value of max flow = capacity of min-cut
608 - Is min cut unique?
609 - Find min cut closest to S
610 - Reverse edge directions and find Max flow from s to t
611 - Find min cut closest to T
612 - Check if the cuts are the same
613
614 III. Bipartite Matching
615
616 Statement:
617 Find a matching M of largest possible size in G.
618
619 Strategy:
620 Design a flow network G' that will have a flow value v(f) = k iff there
621 is a matching of size k in G. Moreover, flow f in G' should identify
622 the matching M in G.
623
624 Solution:
625 - Construct G'
626 - Connect super source to all nodes in X, set weights to 1
627 - Connect all edges X & Y where edges are valid, set weights to 1
628 - Connect super sink to all nodes in Y, set weights to 1
629 - Run max flow on G', let f = max flow
630 - Edges carrying flow between sets X & Y will correspond to our max
631 size matching in G.
632
633 Key Points:
634 - In this problem, Ford Fulkerson is strongly polynomial
635
636 IV. Edge Disjoint
637
638 Statement:
639 Given a directed graph G with s & t in V. Find the max number of edge
640 disjoint s-t paths in G.
641
642 Strategy:
643 Design a flow network G' that will have a flow value v(f) = k iff there
644 are k edge-disjoint s-t paths in G. Moreover, flow f in G' should
645 identify the set of edge disjoint paths in G.
646
647 Solution:
648 - Construct G'
649 - Remove any edges going into s
650 - Remove any edges going out of t
651 - Run max flow in G'
652 - v(f) will equal the max number of edge disjoint s-t paths
653 - f will identify edges on these paths
654
655 Key Points:
656 - If we wind up with a cycle on our path, we can just remove the loop
657 - We can solve this problem for an undirected graph by adding two edges
658 in G' for every edge in G. If we find that we are using both edges in
659 a pair, then reroute both paths by combining their paths to avoid the
660 shared edge e.g. if path B(s,t) and path A(s,t) collide on the forward
661 and backward edges of (u,v), then:
662 B' = B(s, u) + A(u, t)
663 A' = A(s, v) + B(v, t)
664
665 V. Node Disjoint
666
667 Statement:
668 Given a directed graph G with s & t in V. Find the max number of node
669 disjoint s-t paths in G.
670
671 Strategy:
672 - Construct G'
673 - For every node v, create a node v' for all edges into v, create a
674 node v'' for all edges out of v, connect v' and v'' with an edge
675 of capacity 1.
676
677 VI. Circulation with Lower Bounds
678
679 Statement:
680 Given a directed graph G(V,E) with capacities on the edges, and demands
681 (positive - demand, negative - supply) on the nodes. Find if a feasible
682 circulation exists.
683
684 Strategy:
685 Find a feasible circulation (if it exists in two passes):
686 1. Find f_0 to satisfy all lower bounds
687 - Push flow f_0 through G where f_0(e) = l_e
688 - Construct G' where c_e' = c_e - l_e & d_v' = d_v - l_v
689 2. Use remaining capacity of the network to find a feasible
690 circulation f_1 (if it exists)
691 - Find feasible circulation in G' (if no circulation in G' then no
692 circulation in G)
693 3. Combine the two flows: f = f_0 + f_1