xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

Python代写 - 55001 Algorithms Fall 2020 Homework 7

时间：2020-11-25

Notes:
1. MINIMUM SPANNING TREES
a) PRIM’S ALGORITHM
PRIM(G, w, r ) // r b el o n g s t o V, O( ElgV ) runnin g time u si n g Min−Heap data s t r u c t u r e
01 f o r each u i n V
02 key [ u ] = i n f i n i t y // wei gh t o f edge c o n n e c ti n g u t o a v e r t e x i n S ,
where S i s the cu t ( d yn amic all y ch an gin g )
03 pi [ u ] = NIL // p a ren t
04 c o l o r [ u ] = WHITE
05 key [ r ] = 0
06 Q = V // o r d e r e d by key [ u ] , Q = V−S . i n i t i a l l y i s a l l the v e r t i c e s i n V
07 w hil e Q i s not empty
08 u = EXTRACT−MIN(Q) , c o l o r [ u ] = BLACK // add u t o S
09 f o r each v e r t e x v i n Adj [ u ]
10 i f c o l o r [ v ] == WHITE && w( u , v ) < key [ u ]
11 pi [ v ] = u
12 key [ v ] = w( u , v )
13 key [ ∗ ] , pi [ ∗ ]
b) KRUSKAL’S ALGORITHM
KRUSKAL (G, w) //O( ElgV ) r u n ni n t time
01 X = EMPTY LIST //MAINTAIN EDGES IN MST BUILDING
02 f o r each v e r t e x u i n V
03 MAKESET( u )
04 S o r t (E) // i n a s c e n di n g o r d e r o f wei gh t
05 f o r each edge ( u , v ) i n E
06 i f FIND( u ) <> FIND( v )
07 X = X U {( u , v )}
08 UNIOIN( u , v )
09 r e t u r n X
MAKESET( x ) // e ve r y v e r t e x has rank , h ei g h t o f s u b t r e e hanging from t h a t ve r te x ,
RUNNING TIME:O( 1 )
01 pi ( x ) = x
02 rank ( x ) = 0
FIND( x ) // f o l l o w s p a ren t p o i n t e r s t o r o o t o f t r e e ,
RUNNING TIME: PROPORTIONAL TO TREE HEIGHT
01 w hil e x <> pi ( x )
02 x = pi ( x )
03 r e t u r n x
1
UNION( x , y )
01 LINK(FIND( x ) , FIND( y ) )
LINK( x , y )
01 i f rank ( x ) > rank ( y )
02 pi ( y ) = x
03 e l s e pi ( x ) = y
04 i f rank ( x ) = rank ( y )
05 rank ( y ) = rank ( y ) + 1
2.
a) fordFulkersonWithBFS
The BFS procedure should return true if there exists a path from s to t and false otherwise. It should also fill in the
P[], parent, list to store the path defined at 6. Algorithm 2 is a modification of BFS for this purpose.
b) BFSAugmented
2
3.DIJKSTRA ALGORITHM (USE MIN-HEAP DATA STRUCTURE)
DIJKSTRA(G, w, s ) //G = (V, E) i n a d j a c e n c y l i s t format , w = weight , s = s o u r c e v e r t e x
01 f o r each v e r t e x v i n V
02 d [ v ] = i n f i n i t y // di s t a n c e
03 pi [ v ] = n i l // p a ren t
04 d [ s ] = 0
05 Q = empty // c r e a t e a min−heap Q
06 f o r each v e r t e x v i n V
07 I n s e r t −Heap (Q, v , d [ v ] ) //v i s index , d [ v ] i s v al u e put i n t o node
08 w hil e Q != empty
09 u = Ex trac t−Min (Q)
10 f o r each v e r t e x v i n Adj [ u ]
11 i f d [ v ] > d [ u ] + w( u , v )
12 d [ v ] = d [ u ] + w( u , v )
13 Dec rease−Key (Q, v , d [ v ] )
14 pi [ v ] = u
MIN−HEAP OPERATIONS:
MIN−HEAP−INSERT(A, key )
heap−s i z e [A] <− heap−s i z e [A] + 1
A[ heap−s i z e [A ] ] <− +i n f
HEAP−DECREASE−KEY(A, heap−s i z e [A] , key )
HEAP−DECREASE−KEY(A, i , key )
i f key > A[ i ]
then e r r o r ”new key i s l a r g e r than c u r r e n t key ”
A[ i ] <− key
w hil e i> 1 and A[ p a ren t ( i ) ] > A[ i ]
do exchange A[ i ] <−> A[ p a ren t [ i ] ]
i <− p a ren t ( i )
HEAP−EXTRACT−MIN(A)
3
i f heap−s i z e [A] < 1
then e r r o r ” heap unde r fl ow ”
min <− A[ 1 ]
A[ 1 ] <− A[ heap−s i z e [A ] ]
1 Forest Finding
Let G = (V, E, w) be a weighted, undirected graph. A decycler is a set of edges D ⊂ E such that for any cycle
C ⊆ E, C ∩ D = ∅. Our goal is to find a decycler of minimum weight.
• (6 points) Write pseudocode for an algorithm which takes G = (V, E, w) as input, runs in O(E log V ) time,
and returns a minimum-weight decycler.
2 Tree Codes
A common task is to find an efficient representation of some data. In this problem, we will consider how to represent
a sequence of colors as efficiently as possible using binary strings (bitstrings). For example, suppose we have the
following data:
[Blue, Gold, Red, Magenta, Red, Red, Gold, Silver]
Consider the following two mappings from colors to bitstrings:
Color Mapping A Mapping B
Blue 00 110
Gold 10 00
Red 111 01
Magenta 01 111
Silver 110 10
If we replace our sequence of colors with the corresponding bitstrings and concatenate, mapping A yields
00101110111111110110, which has a total length of 20 bits. However, mapping B gives us 110000111101010010,
which uses only 18 bits, so it is a more efficient representation for our data.
In general, given a sequence of (not necessarily distinct) colors, we to design an algorithm which finds an assignment
of binary strings to each color which uses the fewest bits possible. However, to make our output easier to read, we
will also require that no color has a bitstring which begins with another color’s bitstring (e.g., we cannot assign ”0”
to Gold and ”01” to Blue).
A good way to do this is to build a rooted binary tree (NOT a BST) where the leaves represent our colors and the
path from the root to a leaf determines its bitstring (a 0 represents going left once, while a 1 represents going right
once). Another key idea is to construct the tree from the bottom upwards, starting with the least frequent colors -
it is more efficient to assign longer bitstrings to these colors and shorter bitstrings to more frequent colors. You can
use a heap to store colors (or combinations of colors) prioritized by frequency.
• (5 points) Write pseudocode for an algorithm which takes as input a sequence of colors C[1, . . . , n] and outputs
the binary tree described above. Your algorithm should run in O(n lg n) time.
• (1 point) Give a worked example on a sequence of at least 11 colors, of which 5 or more are distinct.
• (1 point) Argue why this process ensures that no color has a bitstring which begins with another color’s
bitstring.
• (2 points) Now, reverse this process. Write pseudocode for an algorithm which takes as input a bitstring
S[1, . . . , n] and a binary tree T built using the algorithm above, and outputs the sequence of colors C[1, . . . , n]
which maps to this string using the mapping given by T. 4
3 Spymaster
We have a set of n spies each of whom needs to meet exactly one messenger from a set of n messengers. The set of
possible locations [m] = {1, · · · , m} where they can meet. For each spy i, there is a subset Si ⊆ [m] of the possible
locations where spy i can go. Similarly, there is a subset Mi ⊆ [m] of the possible locations where messenger i can
go. Moreover, each location j can handle at most cj pairs of spy-messenger meetings. The task is to decide if there
is a possible way to match up spies and messengers such that every pair meets at one of their common locations.
Formally, does there exist a permutation σ on n vertices (mapping spies to messengers) and a function ` : [n] → [m]
mapping spies to locations such that
1. ∀i ∈ [n], `(i) ∈ Si ∩ Mσ(i) (every spy-messenger pair meets at a location which they can both visit)
2. ∀j ∈ [m], |{i | `(i) = j}| ≤ cj (the capacity of each location is not exceeded)
• (3 points) Write the pseudocode which given n, m, {Mi}, {Si} decides if such a pairing is possible.
• (2 points) Give a proof of the correctness of your algorithm.
4 Saturation
We are given a flow network G = (V, E, s, t, c) and some valid flow f. Recall that an edge is saturated under f if
f(e) = c(e). In this problem, we will examine whether the saturated edges can tell us something about the max flow
and min cut in G.
a) (1 points) We say that f is a blocking flow if for every directed path from s to t, there is a saturated edge somewhere along the path. Does this imply that f must be a maximum s t flow? Prove or give a counterexample.
b) (1 points) If f is a maximum s t flow, consider the set S of saturated edges. Let c(S) = Pe∈S c(e) be the total
capacity of S. Is c(S) equal to the minimum total capacity of any s t cut? Prove or give a counterexample.
5 Min-cut with the fewest edges
Given a flow network G = (V, E, s, t, c) with integer capacities, you would like to find the min-cut which contains the
fewest number of edges among all min-cuts in G. • (4 points) Write pseudocode for an algorithm which solves this problem in O(E2V ) time.
• (3 points) Prove that your algorithm returns a min cut with the fewest edges. In other words, if your algorithm
returns a min cut with k edges, show that any other min cut must have at least k edges.
6 Edmonds-Karp
We will develop a slightly modified implementation of the Ford-Fulkerson method using a greedy idea to choose
augmenting paths. Consider a flow network G = (V, E, s, t, c) where c(e) ≥ 1 for all e ∈ E. We define the widest
path as the augmenting path with the most capacity.
a) (2 points) Modify Dijkstra’s algorithm to compute the widest path.
b) Let’s say that we select the choose the widest path during each iteration of Ford-Fulkerson. Let’s try to prove
a bound on its complexity.
• (2 points) Show that the maximum flow in G is at most c|E| where c is the flow through the widest path. • (1 point) Let f0 = f ∗ and let fn denote the remaining flow after n iterations. Prove a recurrence between
fn and fn+1 using the previous observation.
• (1 point) Use your recurrence to conclude that we terminate O(|E| log |f ∗|) iterations. Hint - You can use
that for 0 < x < 1, log(1 x) ≤ −x 5
7 Programming
Please complete the HW7 programming assignment in Problem6 folder. Read the README file for instructions. Fill
in hw7.py for this problem. Code should pass tests in tests folder and all other cases not covered by tests provided.