# Latex代写 | Spring 2020, CMPSC 465 Homework Assignment #7

这个作业是用Latex解决硬币问题和门卫问题

Spring 2020, CMPSC 465 Homework Assignment #7

The homework is due 9 pm on April 30th. Submit the files on Gradescope. Late submissions are

permitted until 11:59 pm on the submission day and will incur a 20% penalty.

Collaboration is not permitted on homework assignments. You should not discuss these problems

with anybody else, either in person or online. Also, looking up solutions to the problems online is

forbidden. Your only reference sources must be the required or recommended text books for this

class. If you come across the solution idea to a homework problem elsewhere (e.g., proofs in other

textbooks or online sources such as Wikipedia articles), you are required to cite the source. If you

are stuck with a homework problem, please send a Canvas message to the 3 TAs and the instructor,

or contact the TAs during their office hours.

Please aim to be clear and concise. The graders and the teaching staff should be able to easily

follow your work.

Your homework submission must be a single PDF file with 5 pages. Use letter-sized pages (8.5 inches

by 11 inches) with 1-inch margins on all sides. Solve each problem on a separate page. Do not

include your name on any page because we may anonymize and randomly shuffle the submissions

while grading.

I strongly recommend using LaTeX (see Overleaf.com) to prepare the solutions. Alternately, you

can use R Markdown or Microsoft Word and convert the document to PDF. Legible PDF scans

of handwritten submissions are also okay if you follow the formatting guidelines above (5 pages,

1 problem on each page, letter-sized pages with 1-inch margins). If you violate the formatting

guidelines (e.g., plain text submissions, number of PDF pages not equal to 5, solutions not in

order, blurry scans, tex/docx files instead of PDF), the submission will not be graded.

This homework assignment has 5 problems and all problems have equal weight.

1

Given an unlimited supply of coins of denominations x1, x2, . . . , xn, we wish to make change for a

value v; that is, we wish to find a set of coins whose total value is v. This might not be possible:

for instance, if the denominations are 5 and 10, then we can make change for 15 but not for 12.

Give an O(nv) dynamic programming algorithm for the following problem.

Input: x1, . . . , xn; v.

Question: Is it possible to make change for v using coins of denominations x1, . . . , xn?

2

A certain string-processing language offers a primitive operation which splits a string into two

pieces. Since this operation involves copying the original string, it takes n units of time for a string

of length n, regardless of the location of the cut. Suppose, now, that you want to break a string

into many pieces. The order in which the breaks are made can affect the total running time. For

example, if you want to cut a 20-character string at positions 3 and 10, then making the first cut

at position 3 incurs a total cost of 20 + 17 = 37, while doing position 10 first has a better cost of

20 + 10 = 30.

Give a dynamic programming algorithm that, given the locations of m cuts in a string of length

n, finds the minimum cost of breaking the string into m + 1 pieces.

1

3

In the art gallery guarding problem, we are given a line L that represents a long hallway in an art

gallery. We are also given a set X = {x0, x1, . . . , xn−1} of real numbers that specify the positions of

paintings in this hallway. Suppose that a single guard can protect all the paintings within distance

at most 1 of his or her position (on both sides). Design an algorithm for finding a placement of

guards that uses the minimum number of guards to guard all the paintings with positions in X.

4

Use the recursion tree method to solve the recurrence T(n) = 6T(n/3) + n

2

.

5

Draw the 11-item hash table resulting from hashing the keys 12, 44, 13, 88, 23, 94, 11, 39, 20,

16, and 5, using the hash function h(i) = (2i + 5) mod 11 and assuming collisions are handled by

chaining.

2