# Assignment #4 This is the forth assignment from winter 2010 term

32 views2 pages

Published on 16 Oct 2011

Department

Computer Science

Course

CS341

Professor

CS 341, Winter 2010

Timothy Chan

Assignment 4 (due March 23 Tuesday noon)

Please read http://www.student.cs.uwaterloo.ca/~cs341/policies.html ﬁrst for general

instructions and http://www.student.cs.uwaterloo.ca/~cs341/prog.html for programming

guidelines.

1. [17 marks] Given a “chain” with nlinks of lengths a1,...,an, where each aiis a positive

integer, we want to “fold” the chain (in one dimension) so that the length of the folded chain

is minimized. More formally, we want to minimize Wsubject to the following constraint:

there exist tin the interval [0, W ] and s1,...,sn∈ {−1,+1}such that t+Pj

i=1 siai∈[0, W ]

for all j∈ {0,...,n}. (Here, tdenotes the position of the ﬁrst joint, and si=±1 depending

on whether we turn rightward or leftward for the i-th link.)

Example: for a1= 5, a2= 1, a3= 7, a4= 2, a5= 8, the minimum length Wis 9.

8

27

1

5

Deﬁne the following subproblem, given 0 ≤k≤n, 0 ≤`≤m:

Let A[k, `, m] be true if we can fold the chain with klinks of lengths a1, . . . , akso

that all the joints lie in the interval [0, m] and the position of the last joint is exactly

`. Let A[k, `, m] be false otherwise. (In other words, A[k, `, m] is true iﬀ there exist

tand s1,...,sk∈ {−1,1}such that t+Pj

i=1 siai∈[0, m] for all j∈ {0, . . . , k}and

t+Pk

i=1 siai=`.)

(a) [8 marks] Derive a recursive formula for A[k, `, m] and set up appropriate base cases.

(b) [9 marks] Present an O(nW 2)-time dynamic programming algorithm to compute the

minimum length Wof the folded chain. Give pseudocode both to compute Wand to

retrieve an optimal folding (i.e., the values of s1,...,sn).

2. [15 marks] Given a sequence of nnumbers a1,...,anand an integer k, we want to divide the

sequence into kblocks so as to minimize the sum of the squares of the block sums. In other

words, we want to ﬁnd 1 < i1< i2<···< ik−1< n to minimize (a1+···+ai1−1)2+ (ai1+

···+ai2−1)2+···+ (aik−1+···+an)2.

Present an O(kn2)-time dynamic programming algorithm to solve the problem. Give pseu-

docode both to compute the minimum value and to retrieve the blocks in the optimal solution.

[Hint: deﬁne a class of O(nk) subproblems. . . ]

3. [10 marks] Given nintervals [a1, b1],...,[an, bn] where each interval [ai, bi] has weight wi, we

want to ﬁnd a subset of intervals whose union covers [0,1] while minimizing the total weight.

Example: if [a1, b1] = [−0.2,0.6], w1= 1, [a2, b2] = [−0.1,1.1], w2= 3, [a3, b3] = [0.5,1.2],

w3= 1, then we would pick the ﬁrst and third intervals, with total weight 2. [Note: this

weighted problem does not appear to be solvable by a greedy approach.]

1

## Document Summary

Please read http://www. student. cs. uwaterloo. ca/~cs341/policies. html rst for general instructions and http://www. student. cs. uwaterloo. ca/~cs341/prog. html for programming guidelines: [17 marks] given a chain with n links of lengths a1, . , an, where each ai is a positive integer, we want to fold the chain (in one dimension) so that the length of the folded chain is minimized. More formally, we want to minimize w subject to the following constraint: there exist t in the interval [0, w ] and s1, . , sn { 1, +1} such that t + (cid:80)j i=1 siai [0, w ] for all j {0, . , n}. (here, t denotes the position of the rst joint, and si = 1 depending on whether we turn rightward or leftward for the i-th link. ) Example: for a1 = 5, a2 = 1, a3 = 7, a4 = 2, a5 = 8, the minimum length w is 9. De ne the following subproblem, given 0 k n, 0 (cid:96) m: