**Unformatted text preview:**

CS 6363.003 Homework 3Due Sunday April 4th on eLearningMarch 20, 2021Please answer the following 4 questions, some of which have multiple parts.1. Suppose you are given a sequence of integers separated by + and − signs; for example:1 + 3 − 2 − 5 + 1 − 6 + 7You can change the value of this expression by adding parentheses in diﬀerent places.For example:1 + 3 − 2 − 5 + 1 − 6 + 7 = −1(1 + 3 − (2 − 5)) + (1 − 6) + 7 = 9(1 + (3 − 2)) − (5 + 1) − (6 + 7) = −17Describe and an alyze a dynamic programming algorithm to compute, given a listof integers separated by + and − signs, the maximum possible value the expressioncan take by adding parentheses. Parentheses must be used only to group additionsand subtractions; in particular, do not use them to create implicit multiplication as in1 + 3(−2)(−5) + 1 − 6 + 7 = 33.Clariﬁcation The unary − operators one would normally use to denote negative integersare not included in the collection of + and − signs separating the integers of the inputsequence. For example, suppose one is given the following sequence of integers separatedby + and − signs:3 + (−2) − 6 − (−4)The (−2) and the (−4) are to be treated as a −2 and −4, respectively, in any methodof adding parentheses considered by the algorithm. In particular, there are exactly ﬁvedistinct ways to group the + and − operations in this sequence using parentheses (someof which evaluate to the same result):3 + ((−2) − (6 − (−4))) = 153 + (((−2) − 6) − (−4)) = −1(3 + (−2)) − (6 − (−4)) = −9(3 + ((−2) − 6)) − (−4) = −1((3 + (−2)) − 6) − (−4) = −11CS 6363.003 Homework 3 (due April 4) Spring 20212. Let T be a rooted binary tree with n vertices, and let k ≤ n be a positive integer. We wouldlike to mark k vertices in T so that every vertex has a nearby marked ancestor. Moreformally, we deﬁne the clustering cost of any subset K of vertices ascost(K) = maxvcost(v, K),where the maximum is taken over all vertices v in the tree, and cost(v, K) is the distancefrom v to its nearest ancestor in K:cost(v, K) =0 if v ∈ K∞ if v is the root of T and v /∈ K1 + co st(parent(v)) otherwiseIn particular, cost(K) = ∞ if K excludes the root of T .112312 22 2112331 12233111222312 212 22 23 3Figure 1. A subset of six vertices in a binary tree with clustering cost 3. The other vertices are labeled with thedistance to their nearest ancestor in the subset.(a) Describe a dynamic programming algorithm to compute, given the tree T and aninteger r, the size of the smallest subset of vertices whose clustering cost is at most r.For full credit, your algorithm should run in O (nr) time.(b) Describe an algorithm to compute, given the tree T and an integer k, the minimumclustering cost of any subset of k vertices in T . For full credit, your algorithm shouldrun in O(n2log n) time. [Hint: Use your algorithm for part (a) as a subroutine. Youmay assume your algorithm for part (a) is correct and runs in O(nr) time.]3. Describe and analyze an algorithm to compute an optimal tern ary preﬁx-free code for agiven array of frequencies f [1 .. n]. In other words, each character in the alphabet shouldbe assigned a string of 0s, 1s, and 2s such that no code is a preﬁx of any other and thetotal length of the encoded message represented by the frequencies is as small as possible.Similar to what we saw in lecture, your output can be the representation of a ternary codetree. See Figure 4.4 of Erickson 4 and the preceding text for an example of how to buildan optimal binary code tree.For simplicity, you may consider the empty string to be a valid code word for the casen=1. Don’t forget to prove that your algorithm is correct foralln.2CS 6363.003 Homework 3 (due April 4) Spring 20214. There are n galaxies connected by m intergalactic teleport-ways. Each teleport-way joinstwo galaxies and can be traversed in both directions. Also, each teleport-way e has anassociated cost c(e) of dollars, where c(e) is a positive integer. A teleport-way can be usedmultiple times, but the toll must be paid every time it is used.Judy wants to travel from galaxy s to galaxy t, but teleportation is not very pleasantand she would like to minimize the number of times she needs to teleport. However, shewants the total cost to be a multiple of ﬁve dollars, because carrying small change is notpleasant either.Describe and analyze an algorithm to compute the smallest number of times Judyneeds to teleport to travel from galaxy s to galaxy t so that the total cost is a multiple ofﬁve dollars. To emphasize, Judy wants to minimize the number of times she teleports. Anytotal cost is ﬁne as long as it is a multiple of ﬁve doll ars.[Hint: Build a graph that can model Judy’s location and how much small change she has.Then, run an appropriate graph search algorithm that you’ve seen

View Full Document