Homework #3 Solution

Homework should be submitted via Moodle in PDF, or plain text. To avoid reduced marks, please submit word/latex-formated PDF file, NOT scanned writing in pdf format. All assignments are due on 9 PM of the due date. Late homework will be accepted only in circumstances that are grounds for excused absence under university policy. The university provides mechanisms for documenting such reasons (severe illness, death in the family, etc.). Arrangements for turning in late homework must be made by the day preceding the due date if possible.




All assignments for this course are intended to be individual work. Turning in an assignment which is not your own work is cheating. The Internet is not an allowed resource! Copying of text, code or other content from the Internet (or other sources) is plagiarism. Any tool/resource must be approved in advance by the instructor and identified and acknowledged clearly in any work turned in, anything else is plagiarism.




If an academic integrity violation occurs, the offending student(s) will be assessed a penalty that is at least as severe as getting a 0 for the whole homework for which the violation occurred, and the case will be reported to the Office of Student Conduct.




Instructions about how to “give/describe” an algorithm (taken from Erik Demaine): Try to be concise, correct, and complete. To avoid deductions, you should provide (1) a textual description of the algorithm, and, if helpful, flow charts and pseudocode; (2) at least one worked example or diagram to illustrate how your algorithm works; (3) a proof (or other indication) of the correctness of the algorithm; and (4) an analysis of the time complexity (and, if relevant, the space complexity) of the algorithm. Remember that, above all else, your goal is to communicate. If a grader cannot understand your solution, they cannot give you appropriate credit for it.




Problem 1d of homework 2) (6 points) Given a set of arbitrary denominations C =(c1,...,cd), describe an algorithm that uses dynamic programming to compute the minimum number of coins required for making change. You may assume that C contains 1 cent, that all denomination are different, and that the denominations occur in in increasing order.




Problem 1e of homework 2) (5 points) Implement the algorithm described in d). We will use the AutoGradr site (https://app.autogradr.com/) for grading your programs. Instructions for signing up at the site and submitting the programming task are given at the bottom of this assignment.







Problem 2. Purpose: reinforce your understanding of dynamic programming and the matrix-chain multiplication problem. (10 points) Please follow the description in our textbook (Chapter 15) and implement a dynamic programming version of the algorithm for solving the matrix-chain multiplication problem. Your program should take an array of integers representing the dimensions of the matrices in the matrix-chain as input, and it should produce the optimal number of scalar multiplications needed to compute the matrix-chain product as output. In addition, your algorithm should also output an optimal parenthesization of the matrix chain.




Again, like in problem 1e of homework 2, We will use the AutoGradr site (https://app.autogradr.com/) for grading your programs. Please submit your implementation of problem 2 in the “Homework 3: MCM” project, which will be posted in AutoGradr. You will find the detailed description of the problem in the site, including input and output specifications, limits, and formatting. Some test cases will be made visible to you as samples. The other test cases will be hidden. Your program will run against each test case automatically, and you will receive an instant feedback on how many test cases you have passed. Usually, the percentage of passed test cases will be proportional to your grade in this question. We may cut off some marks for poorly written codes. The time limit will be set sufficiently high, so you do not need to worry so long as you have correctly implemented a dynamic-programming-based solution with the expected time complexity. Our test cases will be designed in a way that the optimal cost, as well as, all intermediate values should fit in 32-bit signed integers. Also, none of our test cases will have more than one optimal parenthesization order.







Problem 3. Purpose: practice algorithm design using dynamic programming. A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence A,C,G,T,G,T,C,A,A,A,A,T,C,G has many palindromic subsequences, including A,C,G,C,A and A,A,A,A (on the other hand, the subsequence A,C,T is not palindromic). Assume you are given a sequence x[1...n] of characters. Denote L(i,j) the length of the longest palindrome in the substing x[i,...,j]. The goal of the Maximum Palindromic Subsequence Problem (MPSP) is to take a sequence x[1,...,n] and return the length of the longest palindromic subsequence L(1,n).




a) (4 points) Describe the optimal substructure of the MPSP and give a recurrence equation for L(i,j).

b) (6 points) Describe an algorithm that uses dynamic programming to solve the MPSP. The running time of your algorithm should be O(n2).




Problem 4. Purpose: practice designing greedy algorithms. (10 points) Suppose you have a long straight country road with houses scattered at various points far away from each other. The residents all want cell phone service to reach their homes and we want to accomplish this by building as few cell phone towers as possible.

More formally, think of points x1, …, xn, representing the houses, on the real line, and let d be the maximum distance from a cell phone tower that will still allow reasonable reception. The goal is to find a minimum number of points y1,…,yk so that, for each i, there is at least one j with | yj - xi | ≤ d.

Describe a greedy algorithm for this problem. If the points are assumed to be sorted in increasing order your algorithm should run in time O(n). Be sure to describe the greedy choice and how it reduces your problem to a smaller instance. Prove that your algorithm is correct.




Problem 5. Purpose: reinforce your understanding of data structures for disjoint sets. For background on binomial trees and binomial heaps please read 19-2 on page 527. (6 points) Please solve Problem 21.3-3 on page 572 of our textbook.