CS341 Lecture : Assignment #4 This is the forth assignment from winter 2010 term
16 Oct 2011
School
Department
Course
Professor
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:
