CIS 320 Homework Assignment 2
Due: June 9th, 11:00 AM on Gradescope
Please see Piazza and Canvas for submission logistics and LATEXtemplate.
1. Design a dynamic programming algorithm to count the number of binary strings of length n that do not contain the pattern ‘101’ as any 3 consecutive bits in the string. Analyze the running time of your algorithm.
2. In the log-cutting problem we are given a log of wood of length n and cut points 0 < a1 < a2 ··· < ak < n, specifying that we should cut the log at distance a1 from its left end, at distance a2 from the left end, and so on. (Because different portions of the log have different characteristics, it is not enough to get the length of the pieces right. We must make cuts at precisely the specified positions.) The cost of making any cut is proportional to the length of the log being cut. If the first cut is at position ai, cutting the log into pieces of length ai and n − ai, then the next cut on the left piece costs ai and the next cut on the right piece costs n−ai. Use dynamic programming to determine the order in which to perform the cuts to minimize the total cost of all cuts. Prove the correctness and running time bound of your algorithm.
3. In the station placement problem discussed in class, the goal was to minimize the maximum distance traveled by the resident of any town to the nearest station. In this problem, we are going to consider the station placement problem with a different objective function. First of all, there are n towns t1, t2, . . . , tn as before, but now, we are also given that town i has population pi. Your goal is to place k stations so as to minimize the sum of the distances that people have to travel to get to the nearest station. Design a dynamic programming along the lines of the algorithm we designed for the objective function we analyzed in class, with necessary changes. [Hint: Along the way you will need to figure out what the optimal location of a station would be if you knew that it was going to serve a particular set of towns, and how you would design an efficient algorithm to find this location.
4. You are given n types of boxes: The ith type of box has dimensions li × wi × hi. You are given an unlimited supply of boxes of each type. (As a concrete example, these could be the types of boxes you could get from a moving company, and there is an unlimited supply of each type of box available.) You want to build a stack of these boxes of the maximum possible height. You can stack any box in all 3 possible orientations, with any of the 3 dimensions becoming the height of the box. (So the box of type i could be stacked with a base of li ×wi and a height of hi; it could also be stacked with a base of wi × hi and a height of li or with a base of li × hi and a height of wi.) However, the constraint for a valid stack is that if you put one box on top of another, the base of the upper box should fit strictly
1
inside the base of the lower box — in other words, if the lower box has a base of dimension a × b, and theupperboxhasabaseofdimensiona′×b′,thena′