Overview of Today’s Lecture
I. Warmup, Review, Questions, Homework, etc.
Copyright By PowCoder代写 加微信 powcoder
II. Greedy Approach in Bin Packing
III. Coin Changing
IV. Interval Problems
VI. Minimum Spanning Tree
FunAlgo, Fall 2022 2 / 23
I. Review, Questions, Homework, etc.
1 I. Review, Questions, Homework, etc.
2 II. Greedy Approach in Bin Packing
3 III. Interval Problems
5 V. Minimum Spanning Tree
[Start] [End]
FunAlgo, Fall 2022 3 / 23
I. Review, Questions, Homework, etc.
I. Review, Questions, Homework, etc.
FunAlgo, Fall 2022 4 / 23
I. Review, Questions, Homework, etc.
Warmup, Review, Questions, Homework, etc.
Next week is in-class Midterm.
Covers all the material up to Chapter 4.
Study guide: read our solutions to the homeworks,
because we like to build upon them.
– We will publish an ”estimated grade” based on midterm and hwk1-hwk5.
– Don’t worry because grades are curved (not absolute).
Hwk5 is due this Thursday. No late hwk
FunAlgo, Fall 2022 5 / 23
II. Greedy Approach in Bin Packing
1 I. Review, Questions, Homework, etc.
2 II. Greedy Approach in Bin Packing
3 III. Interval Problems
5 V. Minimum Spanning Tree
[Start] [End]
FunAlgo, Fall 2022 6 / 23
II. Greedy Approach in Bin Packing
II. Greedy Approach in Bin Packing
FunAlgo, Fall 2022 7 / 23
II. Greedy Approach in Bin Packing
Introduction to Greedy Approach
What is the Greedy Approach?
Think of an algorithm as sequence of decisions
At each step, do what seems best for this step
Moreover, no regrets!!
THIS IS THE GREEDY PARADIGM?
Simple! Perhaps too simple?
FunAlgo, Fall 2022 8 / 23
II. Greedy Approach in Bin Packing
Introduction to Greedy Approach
To be specific: for i = 1,2, . . .
–the i th Step has a set Xi of choices.
–there is a ”gain function” G : Xi ! R
–te choose xi 2 Xi to maximize G(x).
greedy ⌘ LOCAL optimization
FunAlgo, Fall 2022 8 / 23
II. Greedy Approach in Bin Packing
Introduction to Greedy Approach
Surprising, this sometimes give OPTIMAL solutions!
In reality:
There is usually some global information used
(some global sorting)
–how to choose the ordering
–now to define the greedy function G(x)
FunAlgo, Fall 2022 8 / 23
II. Greedy Approach in Bin Packing
and Bin Packing
Ferris wheel
Riders join a queue
Load riders into current car if possible
Each car has a maximum load
Start new car if max load will be exceeded
FunAlgo, Fall 2022 9 / 23
II. Greedy Approach in Bin Packing
and Bin Packing
Maximum weight is M = 400
Queue: (30,190,80,210,100,80,50)
Solution 1 (Greedy) drop the last 0 digit
(3,19,8),(21,10),(8,5)
Solution 2 (Non-greedy)
(3,19),(8,21,10),(8,5)
Different solution, but “no improvement”.
FunAlgo, Fall 2022 9 / 23
II. Greedy Approach in Bin Packing
and Bin Packing
Online Policy or “First-Come First-Decide”
The decision might be: wait for the next car
First-Come First-Ride Policy (FCFR)
These two policies are independent.
FCFR is captured by ”linear bin packing” formulation
Given w = (w1, . . . ,wn), you can only insert “breakpoints” to choose
your cars.
THEOREM: the greedy method is optimal among all FCFR policies.
Sketch: proof by contradiction…
FunAlgo, Fall 2022 9 / 23
II. Greedy Approach in Bin Packing
Bin Packing
, assume M = 1 (normalized) and queue is w = (w1, . . . ,wn).
Let A(w) be the number of cars used by algorithm A.
E.g., w = (0.3,0.2,0.6,0.5)
FCFR algorithm, G1(w) = 3
Sorted FCFR algorithm, G2(w) = 2
E.g., w = (0.3,0.7,0.3,0.7)
FCFR algorithm, G1(w) = 2
Sorted FCFR algorithm, G2(w) = 3
So, G1,G2 are incomparable!
FunAlgo, Fall 2022 10 / 23
II. Greedy Approach in Bin Packing
Bin Packing
Bin Packing:
Let Opt(w) be the number of cars used by the optimal algorithm (with
arbitrary policy)
Bin Packing Problem : compute Opt(w)
It is an NP-complete Problem (last lecture in this class).
Such problems are not known to have polynomial-time
algorithms (we believe they do not exist).
Joy ride problem with FCFR constraint is Linear Bin Packing .
FunAlgo, Fall 2022 10 / 23
II. Greedy Approach in Bin Packing
Bin Packing
How Good is Linear Bin Packing?
(1) Opt(w)� 1+ bG1(w)/2c
(2) For all n, there exist w such that
Opt(w) = 1+ bn/2c and G1(w) = n
Significance? The (trivial) Linear Bin Packing is a factor of 2 from the
FunAlgo, Fall 2022 10 / 23
II. Greedy Approach in Bin Packing
Bin Packing
Proof: let G1(w) = k .
(1) If Wi is the weight of the i-th bin, then Wi +Wi+1 > 1
Thus Âki=1 Wi > bk/2c.
It follows that Opt(w)� 1+ bk/2c. This proves (1)
(2) Assume n is odd. Consider the n-vector
w = ( 1n ,1,
n ,1, . . . ,1,
Then G1(w) = n but Opt(w) = 1+ bn/2c.
FunAlgo, Fall 2022 10 / 23
II. Greedy Approach in Bin Packing
Bin Packing
The Concept of Approximation Ratio
Suppose A is an algorithm for bin packing.
Absolute approximation ratio of A:
a0(A) := supw
For our Greedy algorithm for linear bin packing, a0(G1) = 3
The problem is that this supw may be determined by a single value of w (we like it to
be achieved asymptotically). To overcome this, we define
a(A) := limsupn an = limn!• sup{ak : k � n}
where an := sup
Opt(w) : Opt(w) = n
FunAlgo, Fall 2022 10 / 23
II. Greedy Approach in Bin Packing
Bin Packing
E.g., from our theorem (1) that
Opt(w)� 1+ bG1(w)/2c � (G1(w)+1)/2 we conclude that
Opt(w) 2�
We mustn’t conclude that a(G1)< 2, only conclude a(G1) 2. What about the lower bound on a(G1)? We know that the bound 2� 1Opt(w) can be achieved by Opt(w) = n for every n. Hence the limit is 2: a(G1) = 2. FunAlgo, Fall 2022 10 / 23 II. Greedy Approach in Bin Packing First Fit Bin Packing How to beat Linear Bin Packing’s factor of 2 We now consider the First Fit (FF) bin packing algorithm that can beat Linear Bin Packing: a(FF) 17/10. FunAlgo, Fall 2022 11 / 23 II. Greedy Approach in Bin Packing First Fit Bin Packing First Fit Bin Packing First Fit Bin Packing INPUT: w = (w1, . . . ,wn) Initialize n empty bins (B1, . . . ,Bn) For i = 1, . . . ,n Place wi into the first bin Bj that fits Return the non-empty bins, (B1, . . . ,Bk) E.g., w = 17(3,5,4,1,3,2,3). Opt(w) = 3, and G1(w) = 5. But FF(w) = 4. Do simulation B = ((3,4),(5,1),(3,2),(3)) FunAlgo, Fall 2022 11 / 23 II. Greedy Approach in Bin Packing First Fit Bin Packing FunAlgo, Fall 2022 11 / 23 II. Greedy Approach in Bin Packing First Fit Bin Packing First Fit Bin Packing FF(w)/Opt(w) 17/10. Complexity? T (n) = O(n2) FunAlgo, Fall 2022 11 / 23 III. Interval Problems 1 I. Review, Questions, Homework, etc. 2 II. Greedy Approach in Bin Packing 3 III. Interval Problems 5 V. Minimum Spanning Tree [Start] [End] FunAlgo, Fall 2022 12 / 23 III. Interval Problems III. Interval Problems FunAlgo, Fall 2022 13 / 23 III. Interval Problems Introduction to Greedy Approach Activities Problem: E.g., swimming and tennis are in conflict . PROBLEM: Given a set of actitivies, find a maximal subset that is conflict-free. FunAlgo, Fall 2022 14 / 23 III. Interval Problems Introduction to Greedy Approach Interval Problems Consider half-open intervals Ii = [si , fi) where si < fi (for i = 1, . . . ,n) It represents time span of the i th activity. Two activities Ii , Ij conflict if Ii \ Ij 6= /0. A set A✓ S is said to be compatible if no 2 activities in A conflict. PROBLEM: Given activities S = {I1, . . . , In}, find a compatible set of maximum cardinality FunAlgo, Fall 2022 14 / 23 III. Interval Problems Introduction to Greedy Approach Generic Greedy Algorithm FunAlgo, Fall 2022 14 / 23 III. Interval Problems Introduction to Greedy Approach What Sorting Criteria? What are the solutions following these criteria? FunAlgo, Fall 2022 14 / 23 III. Interval Problems Introduction to Greedy Approach Sol1: (swim, mov1, mov2) Sol2: (beach, mov2) Sol3: (mov1, mov2, swim) Sol4: (mov2, mov1, swim) FunAlgo, Fall 2022 14 / 23 III. Interval Problems Introduction to Greedy Approach Sorting the activities Ii’s in order of increasing finish times yields the optimal solution. How to implement the algorithm? – Sorting in O(n logn) time. – Each S[{Ii} compatibility test is O(1). Extensions: e.g., maximize the time spent on activities. Give weights to activities: maximize the total weight of solution. FunAlgo, Fall 2022 14 / 23 1 I. Review, Questions, Homework, etc. 2 II. Greedy Approach in Bin Packing 3 III. Interval Problems 5 V. Minimum Spanning Tree [Start] [End] FunAlgo, Fall 2022 15 / 23 FunAlgo, Fall 2022 16 / 23 Informal Problem (P) Given a string s of characters (or symbols) from some alphabet ⌃, choose a variable length code C for ⌃ which minimize the space to encode s. s can be a file; ⌃ can be the ascii code Compare with fixed length encoding, ASCII : ⌃! {0,1}8 FunAlgo, Fall 2022 17 / 23 Variable Length Encoding C : ⌃! {0,1}⇤ Idea: if a letter x 2 ⌃ is more frequent in s, want C(x) to be shorter. Frequency function: fs(x) :=#(x ,s), number of occurences of x in s. Prefix Free Codes : For x 6= y 2 ⌃, C(x) is NOT a prefix of C(y). So if s = x1, . . . ,xn, then C(s) = C(x1)C(x2) · · ·C(xn) can be uniquely FunAlgo, Fall 2022 17 / 23 Example s = ‘abadacadaba0. Then fs(a) = 6, fs(b) = 2, fs(c) = 1, fs(d) = 2 Two variable codes C1,C2 for ⌃= {a,b,c,d} (represented by trees) What is the length of this encoding |C1(s)|? Let us calculate it! COST (f ,C) := Âx2⌃ |C(x)| · fs(x) FunAlgo, Fall 2022 17 / 23 The formal Coding Problem (H) Given f : ⌃! N, find an optimal prefix-free code C for f . The code C is representing by a binary tree TC whose nodes VC are binary strings, and each leaf u 2 VC is labeled by a unique symbol l (u) 2 ⌃. Define W : VC ! R where W (u) = f (l (u)) u is a leaf, W (uL)+W (uR) else. Then COST (f ,C) := Âu W (u) where u range over internal nodes of TC . If T1,T2 are two trees, we can merge them by introduce a new root. FunAlgo, Fall 2022 17 / 23 The Algorithm Note: Q is a priority queue FunAlgo, Fall 2022 17 / 23 Another Example: s = ‘hellotworld!0 FunAlgo, Fall 2022 17 / 23 Encoding a Binary Encoding bT of External Binary Tree T : FunAlgo, Fall 2022 18 / 23 Encoding a Assume n � 0 leaves (so 2n�2 edges) * Method 1: 4n�4 bits (= 2(2n�2)) * Method 2: 3n�2 bits (= (2n�2)+n) * Method 3: 2n�1 bits (= (3n�2)� (n�1)) (replace 01 by 1, for n�1 times) Called the compressed bit representation of T . These are self-limiting encodings! E.g., 1,011,01011,00111,0010111, etc. FunAlgo, Fall 2022 18 / 23 Encoding a Properties bT , a compressed bit representation 1. |bT |= 2n�1 with n�1 zeros and n ones. 2. Any proper prefix of bT has at least as many zeros as ones. 3. The compressed bit representations forms a prefix-free set. 4. There is a linear algorithm to check if bT is valid. FunAlgo, Fall 2022 18 / 23 Encoding a Let C : ⌃! {0,1}⇤ be a prefix-free code and ⌃✓ {0,1}N for some N. Let TC be the code tree for C. Protocol to transmit TC: STEP 1: Transmit the compressed bit representation of the shape of TC STEP 2: Transmit each element of ⌃ in the in-order listing of the leaves of TC. Total bit bit length: (2n�1)+N ·n FunAlgo, Fall 2022 18 / 23 Encoding a Transmit a string s ✓ ⌃⇤ using static Huffman coding assuming ⌃✓ {0,1}N . (1) Compute the frequency function fs of s (2) Compute a Huffman code tree TC using fs (3) STEP 3: Transmit TC using the above protocol (4) STEP 4: Compute and transmit C(s) = C(s1)C(s2) · · · using TC. ISSUES: need two passes over s – not good if s is very long. FunAlgo, Fall 2022 18 / 23 Online Huffman Coding Problem Let T be a weighted code tree with k � 0 internal nodes. Assume the nodes are {0,1, . . . ,2k}. Call i the rank of the node. Let node i have weight wi . E.g., FunAlgo, Fall 2022 19 / 23 Online Huffman Coding Problem Sibling Property (S1) w0 w1 · · · w2k (S2) 2j and 2j +1 are siblings (j = 0, . . . ,k�1) E.g., k = 8 FunAlgo, Fall 2022 19 / 23 Online Huffman Coding Problem Array Representations of T * Weight array: Wt * Left-Child array: [i] =�1 if no left-child * Character map array: Cm where x 2 ⌃0 7! {�1,0,1, . . . ,2k} FunAlgo, Fall 2022 19 / 23 Online Huffman Coding Problem How to use Cm to compute C(x) (bits in reverse order) Output(parity(u)) / parity(u)=1 iff u is odd While u < 2k u parent(u) Output(parity(u)) FunAlgo, Fall 2022 19 / 23 Online Huffman Coding Problem How to restore sibling property after an increment: FunAlgo, Fall 2022 19 / 23 Online Huffman Coding Problem Restore(u) (recursive) RESTORE (u) . u is a node whose weight is to be incremented While (u is not the root) do 1. . Find node v of largest rank R(v) subject . to Wt[v ] = Wt[u]. Specifically: While (Wt[v +1] = Wt[u]) 2. If (v 6= u) 3. Swap(u,v). / This swaps the subtrees rooted at u and v. 4. Wt[u]++. / Increment the weight of u 5. u parent(u). / Reset u 6. Wt[u]++. / Now, u is the root FunAlgo, Fall 2022 19 / 23 Online Huffman Coding Problem Assume the Hello World! Huffman tree. Now we increment the frequency of ‘t’ by one: Operations of Restore (1st potential swap) FunAlgo, Fall 2022 19 / 23 Online Huffman Coding Problem Operations of Restore (the remaining potential swaps) FunAlgo, Fall 2022 19 / 23 Online Huffman Coding Problem How to add a new letter: the 0-node Introduce a unique node of weight 0 It represents all the yet-unseen letters in ⌃0 \⌃ When a new letter x is seen, transmit the code of the 0-node, together with the standard code x 2 {0,1}N BUT we must increase the ranks of ALL the previous nodes by 2. FunAlgo, Fall 2022 19 / 23 V. Minimum Spanning Tree 1 I. Review, Questions, Homework, etc. 2 II. Greedy Approach in Bin Packing 3 III. Interval Problems 5 V. Minimum Spanning Tree [Start] [End] FunAlgo, Fall 2022 20 / 23 V. Minimum Spanning Tree V. Minimum Spanning Tree FunAlgo, Fall 2022 21 / 23 V. Minimum Spanning Tree Minimum Spanning Tree (MST) Given a graph G = (V ,E ;C) with cost function C : E ! R A spanning forest is an acyclic set T ✓ E of maximal cardinality. A minimum spanning forest is one of minimum For simplicity, assume G is connected. Then we speak of a minimum spanning tree (MST) T = {a�b,b�c,d�e} is acyclic T = {a�b,b�c,c�a,d�e} is cyclic FunAlgo, Fall 2022 22 / 23 V. Minimum Spanning Tree Minimum Spanning Tree (MST) Generic Greedy MST Algorithm Suppose S is “good” Problem: find e 2 E \S so that e is “good” for S Necessary for goodness: if S+e is acyclic, call e a candidate FunAlgo, Fall 2022 22 / 23 V. Minimum Spanning Tree Minimum Spanning Tree (MST) Prim’s Algorithm a b c d e S ✓ V edge m0 0 • • • • /0 m1 0 2/a 2/a 3/a 2/a {a} �� m2 2/a 1/b {a,b} a�b m3 1/b 2/c {a,b,c} b�c m4 2/c 1/d {a,b,c,d} c�d m5 1/d {a,b,c,d ,e} d�e FunAlgo, Fall 2022 22 / 23 V. Minimum Spanning Tree Minimum Spanning Tree (MST) Criteria for Algo, Fall 2022 22 / 23 V. Minimum Spanning Tree Minimum Spanning Tree (MST) Hand Simulation Kruskal: sort edges e1 e2 · · · Prim: maintain array d [1..n] where d [i] is least cost to connect 1 to i . Borukva: maintain connected component array CC[i] = j and min-cost A[CC[i]] = u�v extension FunAlgo, Fall 2022 22 / 23 V. Minimum Spanning Tree Minimum Spanning Tree (MST) Boruvka Algorithm Maintain connected components CC[i] = j Each phase, number of components is at least halved. Hence, at most lgn phases FunAlgo, Fall 2022 22 / 23 V. Minimum Spanning Tree Minimum Spanning Tree (MST) Implementing a Phase of Boruvka in O(n+m) Time Borukva: maintain connected component array CC[i] = j FunAlgo, Fall 2022 22 / 23 V. Minimum Spanning Tree What is a Matroid? It is a hypergraph H = (V ,E) with V ,E non-empty satisfying 2 properties: (1) Hereditary : if A✓ B 2 E then A 2 E . In particular /0 2 E . (2) Exchange : if A,B 2 E and |A|< |B| then there is some e 2 B \A such that A+e 2 E . FunAlgo, Fall 2022 23 / 23 V. Minimum Spanning Tree Matrix Matroids Let M be a n⇥n matrix of real numbers Let C := {M[1], . . . ,M[n]} be the columns of M. Let I comprise all linearly independent subset A✓ C. Then H = (C, I) is the matroid defined by matrix M. Recall in Linear Algebra: a set of vectors v1, . . . ,vk is linearly independent if for all real ci ’s, Âki=1 civ i = 0 iff c1 = c2 = · · ·= ck = 0. FunAlgo, Fall 2022 23 / 23 V. Minimum Spanning Tree Why is the matrix matroid a matroid? Clearly hereditory. Exchange property: if |A|< |B| then A[B has rank strictly greater than |A|, and so we can find some b 2 B so that A+b has rank |A|+1. E.g., let M = 5. Then the matroid of M is H = ({1,2,3} , I) where I = { /0,{1} ,{2} ,{3} ,{1,2} ,{2,3} ,{1,3}}. FunAlgo, Fall 2022 23 / 23 V. Minimum Spanning Tree Graphic Matroids Let G = (V ,E) be a bigraph. Let I denote the set of all acyclic subsets of S. The hypergraph H = (E , I) is a graphic matroid of G. See Lecture Notes for proof that I has the exchange property. FunAlgo, Fall 2022 23 / 23 V. Minimum Spanning Tree The bases of a matroid (V ,E) are those A 2 E that is not properly contained in another independent set. It follows from exchange property: all bases have the same cardinality called the rank of the matroid. Given a matroid (V ,E ;C) with cost function C : V ! R�0, find a base of maximum cost. Kruskal’s algorithm for Maximum base: Sort V in decreasing cost order: v1 � v2 � · · ·� vn. Initialize S /0. For i = 1, . . . ,n Add vi to S if it preserves independence. FunAlgo, Fall 2022 23 / 23 V. Minimum Spanning Tree “Algebra is generous, she often gives more than is asked of her.” — Rond D’Alembert FunAlgo, Fall 2022 23 / 23 I. Review, Questions, Homework, etc. II. Greedy Approach in Bin Packing III. Interval Problems V. Minimum Spanning Tree 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com