I.Warmup, Review, Questions, Homework, etc.
II.
Greedy Approach in Bin Packing
III.
IV.
Coin Changing
Interval Problems
V.
Huffman Code
VI.
Minimum Spanning TreeAdd
I. Review, Questions, Homework, etc.
Next…
1 I. Review, Questions, Homework, etc.
2 II. Greedy Approach in Bin Packing
3 III. Interval Problems 4 IV. Huffman Code
5 V. Minimum Spanning TreeAdd
[Start] [End]
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).
Next…
1 I. Review, Questions, Homework, etc.
2 II. Greedy Approach in Bin Packing
3 III. Interval Problems 4 IV. Huffman Code
5 V. Minimum Spanning TreeAdd [Start] [End]
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
THIS IS THE GREEDY PARADIGM?Moreover, no regrets!! Simple! Perhaps too simple?
Introduction to Greedy Approach
Add
To be specific: for i = 1,2,…
–the ith Step has a set Xi of choices.
–there is a ”gain function” G : Xi !R
–te choosexi 2 Xi to maximize G(x).
greedy ⌘ LOCAL optimization
Introduction to Greedy Approach
Add
8/23 Surprising, this sometimes give OPTIMAL solutions!
In reality:
Introduction to Greedy Approach
There is usually some global information used
(some global sorting) –how to choose the ordering –now to define the greedy function G(x)
Introduction to Greedy Approach
Add
8/23
Joy Rides and Bin Packing
Ferris wheel
Riders join a queue
Load riders into current car if possible
Each car has a maximum load
Add Start new car if max load will be exceeded Example
Maximum weight is M = 400
Joy Rides and Bin Packing
(30,190,80,210,100,80,50)
Queue:
Solution 1 (Greedy) drop the last 0 digit (3,19,8),(21,10),(8,5) Solution 2 (Non-greedy)
Add (3,19),(8,21,10),(8,5)
Different solution, but “no improvement”. Policies
Joy Rides and Bin Packing
AssignmOnline Policy ent Project Exam Helpor “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.Add
THEOREM: the greedy method is optimal among all FCFR policies.
Joy Rides and Bin Packing
Sketch: proof by contradiction…
Bin Packing
Optimality
Wlog, 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
Bin Packing
Add 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!
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)
Such problems are not known to have polynomial-time
algorithms (we believe they do not exist).
Bin Packing
Joy ride problem with FCFR constraint isAdd Linear Bin Packing . How Good is Linear Bin Packing?
THEOREM
(1) Opt(w) 1+bG1(w)/2c w such that
(2) For all n, there exist
Opt(w) = 1+bn/2c and G1(w) = n
Significance? The (trivial) Linear Bin Packing is a factor of 2 from the
optimal!
Bin Packing
Add
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 thatOpt(w) 1+bk/2c. This proves (1)
(2) Assume n is odd. Consider the n-vector
Bin Packing
w = ( n1,1, n1,1,…,1, n1)
ThenAdd G1(w) = n but Opt(w) = 1+bn/2c.
The Concept of Approximation Ratio
Suppose A is an algorithm for bin packing. Absolute approximation ratio of A:
a0(A):= supw OptA(w(w))
Bin Packing
For our Greedy algorithm for linear bin packing, a0(G1) = 3
a(A):= limsupn an = limn !•sup {ak : k n}
where an := .
E.g., from our theorem (1) that
Bin Packing
Opt(w) 1+bG1(w)/2c (G1(w)+1)/2 we conclude that OptG1((ww)) 2Opt1(w)
We mustn’t conclude thata(G1) < 2, only conclude a(G1) 2.
What about the lower bound on a(G1)? We know that the bound 2 Opt1(w) can be achieved by Opt(w) = n for every n. Hence the limit is 2:
Add Wea(G1) = 2Chat .
First Fit Bin Packing
How to beat Linear Bin Packing’s factor of 2
Assignment We now consider the First FitProject Exam Help(FF) bin packing algorithm that can beat Linear Bin Packing: a(FF) 17/10.
First Fit Bin Packing
Add
11/23 First Fit Bin Packing
First Fit Bin Packing
Assignment Project Exam
HelpFirst Fit Bin Packing
INPUT: w = (w1,…,wn)
1,…,n
First Fit Bin Packing
Place wi into the first bin Bj that fits
Return the non-empty bins, (B1,…,Bk )
E.g.,Add w = 17(3,5,4,1,3,2,3). Opt(w) = 3, and G1(w) = 5. But FF(w) = 4.
Do simulation
First Fit Bin Packing
B = ((3,4),(5,1),(3,2),(3))
11/23
First Fit Bin Packing
Add
11/23
First Fit Bin Packing
First Fit Bin Packing
Assignment Project ExaTHEOREM m Help
FF(w)/Opt(w) 17/10.
Complexity?
T(n) = O(n2)
Add
III. Interval Problems
Next…
1 I. Review, Questions, Homework, etc.
2 II. Greedy Approach in Bin Packing
3 III. Interval Problems 4 IV. Huffman Code
5 V. Minimum Spanning TreeAdd
[Start] [End]
Introduction to Greedy Approach
Activities Problem:
Add
E.g., swimming and tennis are in conflict .
PROBLEM: Given a set of actitivies, find a maximal subset that is conflict-free.
Introduction to Greedy Approach
Interval Problems
Assignment PrConsider half-open intervalsojectIi = [si,fi) Exam Help where si < fi (for i = 1,…,n) It
represents time span of the ith activity.
Two activities Ii,Ij conflict if Ii Ij 6= 0/.
Introduction to Greedy Approach
A set A ✓ S is said to be compatible if no 2 activities in A conflict.
PROBLEM: Given activitiesAdd S = {I1,…,maximumIn},
cardinality
find a compatible set of
Introduction to Greedy Approach
14/23 Generic Greedy Algorithm
Introduction to Greedy Approach
Add
14/23 What Sorting Criteria?
Introduction to Greedy Approach
Add
What are the solutions following these criteria?
14/23
Sol1: (swim, mov1, mov2)
Sol2: (beach, mov2)
Introduction to Greedy Approach
Sol3: (mov1, mov2, swim)
Sol4: (mov2, mov1, swim)
Add
14/23
Introduction to Greedy Approach
small
Assignment Project Exam
THEOREM
Sorting the activities Ii’s in order of increasing finish times yields the optimal solution.
Help
How to implement the algorithm? – Sorting in O(nlogn) time.
Add – 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. IV. Huffman Code
Next…
1 I. Review, Questions, Homework, etc.
2 II. Greedy Approach in Bin Packing
3 III. Interval Problems 4 IV. Huffman Code
5 V. Minimum Spanning TreeAdd [Start] [End]
Huffman Code
Informal Problem
(P) Given a string s of characters (or symbols) from some alphabet ⌃,
a variable length code C for ⌃ which minimize the space to encode s.
Huffman Code
s can be a file;Add ⌃ can be the ascii code
Compare with fixed length encoding, ASCII : ⌃! {0,1}8 Variable Length Encoding
AssignCment : ⌃! {0,1}⇤ Project Exam Help
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 :
Huffman Code
For x 6= y 2⌃, C(x) is NOT a prefix of C(y).
So ifAdd Wes = x1,…,xn, then CChat powc(s) = C(x1)C(x2)···C(xn) odercan be uniquely
decoded!
Huffman Code
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) Add
What is the length of this encoding |C1(s)|? Let us calculate it!
Huffman Code
COST(f,C):= Âx2⌃|C(x)|·fs(x)
17/23 The formal Huffman Tree Coding Problem
Assignment Project Exam(H) Given f : ⌃!N, find an optimal prefix-free code C for f. Help
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⌃.
Huffman Code
DefineW : VC !R where W(u) = ⇢ Wf(l(u(uL)+)) W(uR)uelseis a leaf,. Then COST(f,C):= Âu W(u)
Add where u range over internal nodes of TC.
If T1,T2 are two trees, we can merge them by introduce a new root.
17/23
Huffman Code
The Huffman Code Algorithm
Add
Note: Q is a priority queue
Huffman Code
17/23 Another Example: s = ‘hello tworld!0
Huffman Code
Add
17/23
Encoding a Huffman Tree
Binary Encoding bT of External Binary Tree T:
Add
Assume n 0 leaves (so 2n 2 edges)
* Method 1: 4n 4 bits (= 2(2n 2))
Encoding a Huffman Tree
* 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 areAdd self-limiting encodings! E.g., 1,011,01011,00111,0010111, etc.
Encoding a Huffman Tree
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 ifbT is valid.
Encoding a Huffman Tree
Add
Let C : ⌃! {0,1}⇤ be a prefix-free code and ⌃✓ {0,1}N for some N. Let
Encoding a Huffman Tree
Protocol to transmit TC:
Transmit each element of ⌃ in the in-order
Encoding a Huffman Tree
listing of the leaves of TC.
TC be the
code tree for C.
Total bit bit length:
Encoding a Huffman Tree
Add (2n 1)+N ·n
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
Encoding a Huffman Tree
(3) STEP 3: TransmitTC using the above protocol
(4) STEP 4: Compute and transmit C(s) = C(s1)C(s2)··· using TC.
ISSUES: need two passes overAdd s – not good if s is very long.
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., Add
Sibling Property
Online Huffman Coding Problem
(S1) w0 w1 ··· w2k
(S2) 2j and 2j +1 are siblings (j = 0,…,k 1)
E.g., k = 8 Add
Array Representations of T
Online Huffman Coding Problem
* Weight array: Wt
* Left-Child array:Add Lc
Lc[i] = 1 if no left-child
* Character map array: Cm where x 2⌃0 7! { 1,0,1,…,2k}
How to use Cm to compute C(x) (bits in reverse order)
Online Huffman Coding Problem
C(x):
uOutput(parity( Cm[x] u)) / parity(u)=1 iff u is odd
u < 2
k
Online Huffman Coding Problem
u parent(u)u)) Output(parity(
Online Huffman Coding Problem
Add
How to restore sibling property after an increment:
Online Huffman Coding Problem
Add
Restore(u) (recursive)
Online Huffman Coding Problem
Assignment Project Exam
HelpRESTORE (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
Online Huffman Coding Problem
= Wt[u]. Specifically:
vWhile ( u Wt[v +1] = Wt[u])
v++
Online Huffman Coding Problem
powcoderIf (v 6= u) (u,v). / This swaps the
subtrees rooted at u and v.
3. Swap
4. Wt[u]++. / Increment the weight of u
5.6. Wt[uu]++ . parent/ Now, u is the root(u). / Reset u
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)
Add
Operations of Restore (the remaining potential swaps)
Online Huffman Coding Problem
Add
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⌃
Online Huffman Coding Problem
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.
Add
V. Minimum Spanning Tree
Next…
1 I. Review, Questions, Homework, etc.
2 II. Greedy Approach in Bin Packing
3 III. Interval Problems
4 IV. Huffman Code
Minimum Spanning Tree (MST)
5 V. Minimum Spanning TreeAdd
[Start] [End]
20/23
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.
https://powA minimum spanning forestcoder.comis one of minimum cost.
For simplicity, assume G is connected.
Then we speak of aAdd minimum spanning tree (MST) T = {a b,b c,d e} is acyclic
Minimum Spanning Tree (MST)
T = {a b,b c,c a,d e} is cyclic
Minimum Spanning Tree (MST)
Generic Greedy MST Algorithm
Add
Suppose S is “good”
find e E S so that e is “good” for S
Problem: 2
Minimum Spanning Tree (MST)
candidate
Necessary for goodness: if S +e is acyclic, call e a Prim’s Algorithm
a b c d e S ✓ V edge
m0 0 • • • • 0/
Minimum Spanning Tree (MST)
Add { }
Criteria for Goodness
Minimum Spanning Tree (MST)
Add
Hand Simulation
Minimum Spanning Tree (MST)
Add
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
Boruvka Algorithm
Minimum Spanning Tree (MST)
Add
Maintain connected components CC[i] = j
Each phase, number of components is at least halved.
Hence, at most lgn phases
Implementing a Phase of Boruvka in O(n +m) Time
Minimum Spanning Tree (MST)
Borukva: maintain connected component array CC[i] = j
Add
Matroids
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.
Matroids
Add
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.
Matroids
Thenhttps://pH = (C,I) is the matroidowcoder.comdefined by matrix M.
Recall in Linear Algebra: a set of vectors v1,…,vk is linearly independent
if for all real ci ’s,
Add Âki=1 ci vi = 0 iff c1 = c2 = ··· = ck = 0. Why is the matrix matroid a matroid?
Matroids
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. Then the matroid of M is
H = ({1,Add 2,3},I) where I = {0/,{1},{2},{3},{1,2},{2,3},{1,3}}. Graphic Matroids
Let G = (V,E) be a bigraph.
Matroids
Let I denote the set of all acyclic subsets of S.
The hypergraph H = (E,I) is a graphic matroid of G.
Add
The bases of a matroid (V,E) are those A 2 E that is not properly
Matroids
contained in another independent set.
It follows from exchange property: all bases have the same cardinality called the rank of the matroid.
maximum cost. Given a matroid(V,E;C) with cost function C : V !R 0, find a base of
Kruskal’s algorithm for Maximum base:
Matroids
Add Sort V in decreasing cost order: v1 v2 ···
Initializei = 1,…,Sn 0/.
For
Add vi to S if it preserves independence. vn.
V. Minimum Spanning Tree
“Algebra is generous,
she often gives more than is asked of her.” — Jean Le Rond D’Alembert (1717-83)
Add
