Homework 6
Fundamental Algorithms, Fall 2022, Professor Yap; Section Leaders and Zeming Lin
Copyright By PowCoder代写 加微信 powcoder
Due: Fri Nov 11, in GradeScope by 11pm.
INSTRUCTIONS:
� Please download the latest version of Chapter 5 (l5-class.pdf) from the Schedule Page in ClassWiki.
The page references below refers to this version.
� The reading list for Chapter 5 may be narrowed down to §1, 3, 4, 6.
� 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{eqn�p1{2qq.
HINT: Repeat the Karp-Held trick that saved us a factor of n. 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
wpti�1..tis :�
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
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.
© Page 1 November 4, 2022
(a) Show by a counter example that the following algorithm does not work:
Opti,j � max tOpti,k �Optk�1,j : i ¤ k ¤ j � 1u (1)
HINT: May assume |S| ¤ 4 in the counter example.
(b) Give an Opn log nq 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!\this\is\my\little\world!”. 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.
v12v11v10v9
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.
© Page 2 November 4, 2022
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com