INSTRUCTIONS:
For general instructions about homework, please look in hw1 or hw2.
(Q1) (20 Points) Improving Brute Force Bin Packing
Improve the bin packing upper bound in Lemma 2 (¶V.6, p.6) to Oppn{eqnp1{2qq.
HINT: Repeat the Karp-Held trick that saved us a factor ofn. Fix two weights w1,w2 and consider two cases: either w1,w2 belong to the same bin or they do not.
(Q2) (6+20 Points) Linear Bin Packing with Negative Weights
(a) Consider the linear bin packing problem when the weights in w pw1,…,wnq can be negative. A solution with k bins is determined by its the sequence of breakpoints, 0 t0 t1 t2 tk n where the ith bin holds the weights Add ti
wpti 1..tis: ‚ wj.
j ti 1 1
Here is a greedy way to define these indices: for i ¥ 1, assuming ti 1 is defined, let ti to be the largest index (but at most n) such that wpti 1..tis ⁄ M. Either prove that this solution is optimal (for linear bin packing), or give a counter example. NOTE: this algorithm is no longer “online”.
(b) Give an Opn2q algorithm for linear bin packing when there are negative weights.
HINT: When solving the problem for pM,wq, assume that you already know the solution for each pM,w1q where w1 is a suffix of w.
(Q3) (6+20 Points) Activities Selection to maximize length
Consider the activities selection problem. See ¶V.16, p.21. Let S tI1,…,Inu be a set of activities where each activity Ii rsi,fiq is a half-open interval. We want to find a compatible set A S which maximizes the length |A| where
|A|: ‚ |I|
IPA
and |Ii|: fi si. Denote by OptpSq the maximum length of A S.
Let Si,j tIi,Ii 1,…,Iju for i ⁄ j and Opti,j : OptpSi,jq.
Opti,j maxtOpti,k Optk 1,j : i ⁄ k ⁄ j 1u (1)
(b) Give an Opnlognq algorithm for computing Opt1,n.
HINT: order the activities in the set S according to their finish times.
(Q4) (10+20 Points) Huffmann coding
(a) Let s be the following string: “hello! hisismylittleworld!”. Show the Huffman code C for s, and what is |Cpsq|?
(b) Suppose you are given the frequencies fi in sorted order. Show that you can construct the Huffman tree in linear time.
(Q5) (10+10 Points) MST
We consider minimum spanning trees (MST’s) of the bigraph G pV,Eq where each vertex v P V is given a numerical value Cpvq ¥ 0. The cost Cpu,vq of an edge pu vq P E is defined to be Cpuq Cpvq. For each simulation below, please also state the cost of your MST.
Please organize your computation so that we can verify the computation results. See ¶V.37 (p.60) for how to do the for Prim’s algorithm. For Kruskal’s algorithm, it is best to list the edges in increasing sorted order, and successively, accept or reject each edge.
2
1 v1 v2
0 6 4
v3 v4 v5
1 2
Add pv6 owcoderv7
v8 v9 v10 v11 v12
3 5 1 0 2
Figure 1: The house graph: The cost of edge vi vj is defined as Cpviq Cpvjq, where Cpvq is the value of vertex v. E.g. Cpv1 v4q 1 6 7.
(a) Simulate Prim’s algorithm on the bigraph G of Figure 1.
(b) Simulate Kruskals’s algorithm on G.
