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

32 views2 pages
Published on 16 Oct 2011
School
University of Waterloo
Department
Computer Science
Course
CS341
CS 341, Winter 2010
Timothy Chan
Assignment 4 (due March 23 Tuesday noon)
Please read http://www.student.cs.uwaterloo.ca/~cs341/policies.html first 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 first 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
Define the following subproblem, given 0 kn, 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 iff 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 find 1 < i1< i2<···< ik1< n to minimize (a1+···+ai11)2+ (ai1+
···+ai21)2+···+ (aik1+···+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: define 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 find 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 first and third intervals, with total weight 2. [Note: this
weighted problem does not appear to be solvable by a greedy approach.]
1
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

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: