Spring 2020, CMPSC 465 Homework Assignment #2
You will submit this homework in two parts. Part 1 (problems 2, 5, 7) is due 9 pm on February
17th. Part 2 (problems 1, 3, 4, 6) is due 9 pm on February 19th. Submit both 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 3 pages (for part 1) or 4 pages (for part
2). 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 (3 or 4 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 7, solutions not in
order, blurry scans, tex/docx files instead of PDF), the submission will not be graded.
This homework assignment has 7 problems. Problems 1-3 are worth 7 points, problems 4-6 are
worth 8 points, and problem 7 is worth 5 points.
1
Use iterative substitution to solve the recurrence T (n) = 2T (n− 1) + 3n. Assume that T (1) = 1.
2
Suppose you wish to develop a matrix-multiplication algorithm that is asymptotically faster than
Strassen’s algorithm. Your algorithm will use divide-and-conquer, dividing each matrix into pieces
of size n/8 × n/8, and the divide and combine steps together will take Θ(n2) time. You need
to determine how many subproblems your algorithm has to create in order to beat Strassen’s
algorithm. If your algorithm creates a subproblems, what is the largest integer value of a for which
your algorithm would be asymptotically faster than Strassen’s algorithm?
3
You are given two boxes: one box filled with mason jars of different sizes, and another box filled
with corresponding screw top lids. You can test whether a given jar and lid are a match, from which
1
you learn whether the jar is too large, too small, or an exact match for the lid. The differences in
size between pairs of jars or lids are too small to see by eye, so you cannot compare the sizes of
two jars or two lids directly. You are to match each jar to each lid, with the assumption that no
two jars or two lids are of the same size, and that every jar in one box has a corresponding lid in
the other box. Give a randomized O(n log n) expected time algorithm for this problem.
4
Solve the recurrence equation T (n) = 8T (n/4) + n3 using the recursion tree construction method.
Express your answer in the Θ-notation. In the recursion tree method, you (i) draw a recursion
tree, (ii) determine its height, (iii) estimate the work associated with nodes at each level, and (iv)
simplify the summation to come up with a closed-form expression for the running time. Assume
that T (1) = 1 and that n is a power of 4.
5
Suppose you are consulting for a bank that is concerned about fraud detection, and they come to
you with the following problem. They have a collection of n bank cards that they have confiscated,
suspecting them of being used in fraud. Each bank card is a small plastic object, containing a
magnetic stripe with some encrypted data, and it corresponds to a unique account in the bank.
Each account can have many bank cards corresponding to it, and we will say that two bank cards
are equivalent if they correspond to the same account.
It is very difficult to read the account number off a bank card directly, but the bank has a
high-tech “equivalence tester” that takes two bank cards and, after performing some computations,
determines whether they are equivalent.
Their question is the following: among the collection of n cards, is there a set of more than n/2
of them that are all equivalent to one another? Assume that the only feasible operations you can
do with the cards are to pick two of them and plug them in to the equivalence tester. Show how
to decide the answer to their question with only O(n log n) invocations of the equivalence tester.
6
Suppose we are given a sequence S of n elements, each of which is colored red or blue. Assuming S
is represented as an array, give an in-place O(n) method for ordering S so that all the red elements
are listed before all the blue elements.
7
Consider the following variant of Mergesort, where instead of partitioning the array into two equal
halves, you split the array into 5 nearly-equal parts. What is the running time recurrence relation for
this algorithm? How does the running time compare asymptotically to the running time of normal
Mergesort? Clearly state any assumptions you make when deriving the closed form expression for
the running time.
2