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 different 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.Clarification 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 fivedistinct 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 define 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 prefix-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 prefix 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 five 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 offive dollars. To emphasize, Judy wants to minimize the number of times she teleports. Anytotal cost is fine as long as it is a multiple of five 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

UT Dallas CS 6363 - Homework 3

Documents in this Course
Exam #1

Exam #1

5 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec14

lec14

11 pages

lec13

lec13

22 pages

lec12

lec12

8 pages

lec11

lec11

3 pages

lec10new

lec10new

11 pages

lec9

lec9

13 pages

lec8

lec8

9 pages

lec7

lec7

10 pages

lec6

lec6

8 pages

lec4

lec4

5 pages

lec3

lec3

5 pages

lec1

lec1

3 pages

greedy

greedy

4 pages

siphon

siphon

18 pages

hwk5

hwk5

3 pages

Load more
Download Homework 3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework 3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?