CS6033 Homework Assignment 11∗ Due April 27th at 11:59 pm
No late assignments accepted
1. Show the longest common subsequence table, L, for the following two strings: X = “notice”, Y = “encircle”. What is the longest common subsequence between these strings?
In your answer, define what your variables mean.
2. What is the best way to multiply a chain of matrices with dimensions that are
15×3,3×7,7×27,27×10,10×5, and 5×60? Show your work.
3. As stated, in dynamic programming, we first solve the subproblems and then choose which of them to use in an optimal solution to the problem. Professor Capulet claims that we do not always need to solve all the subproblems in order to find an optimal solution. She suggests that we can find an optimal solution to the matrix- chain multiplication problem by always choosing the matrix Ak at which to split the sub-product AiAi+1 ···Aj(by selecting k to minimize the quantity pi−1pkpj) before solving the subproblems. Find an instance of the matrix-chain multiplication problem for which this greedy approach yields a suboptimal solution.
Modified from Goodrich, Michael T.; Tamassia, Roberto. Algorithm Design and Applications
4. You are taking a road trip to visit Aunt Mary!
Since you are taking Design and Analysis of Algorithms, you are going to optimize your route.
You will be traveling with your cousin. Since your cousin owns the car, he has decide which route you will take. You have, however, convinced your cousin you are the one to decide what hotels to stop at on your way (they all are mysteriously on the side of the road). You are going to optimize your route so it costs the least (you are a graduate student after all and need to save money).
∗Many of these questions came from outside sources.
On your route are a series of hotels h1, h2, . . . , hn. The hotel hi costs ci. If you travel more than 500 miles per day, you realize you will spend more on coffee, specifically you will spend (n/2) for n miles over 500 (your cousin crashes hard, and hiring someone to help move him into the hotel room is reasonably expensive)
You would like to minimize your expenses. For this problem:
• provide the recursive solution
• prove that the problem has optimal substructure
• use your recurrence formula to find the minimum cost to get to California, which is 2,700 miles away for the case where the hotels are at mile markers:
400, 850, 926, 1420, 1540, 1950, 2100, 2400 and the hotels cost $56, $75, $46, $76,$49, $60, $55, $87.
In your answer, define what your variables mean.
5. This question is modified from a question in CLRS.
The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluxuating, but predictable, demand. The company wishes to design a plan for the next n months. For each month i, the company knows the demand di, that is, the number of machines that it will sell. Let D = PNi=1 di be the total demand over the next n months. The company keeps a full-time staff who provide labor to manufacture up to m machines per month. If the company needs to make more than m machines in a given month, it can hire additional, part-time labor, at a cost that works out to c dollars per machine. Furthermore, if the company is holding any unsold machines at the end of a month, it must pay inventory costs. The company can hold up to D machines, with the cost for holding j machines given as a function h(j) for j = 1, 2, ..., D that monotonically increases with j.
• Provide a recurrence relation to find the minimum cost and fulfill all the demand.
• Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomial in n and D.
• Show a small example of how your recurrence relation works.
6. During the annual robotic competition, competitors store their robots along the southern wall in positions 1, . . . , n. All teams must move their robots across the room to the northern wall during the award ceremony. The winner will be in posi- tion 1; the second-place winner will be in position 2, etc. The award ceremony order is given by y1, . . . , yn showing robot yi should be in the ith position.
The organizers would like to be an event to run smoothly by getting as many robots on the southern wall as quickly as possible. They also do not want an accident of two robots colliding when they cross the room. They have asked you to determine the maximum number of robots that can move across the room first without crossing any two paths.
As a first step in solving this problem,
• create the recurrence relation that returns the maximum number of robots that can move at the same time without having any two robots cross paths. (Make sure you define your variables.)
• If you implement your recurrence relation efficiently using dynamic program- ming, what would be the running time of your algorithm?
• What size table do you need to store the subproblems using big-Oh notation?
• Create a small example to demonstrate how your algorithm works
7. (3 bonus points) Think of a good exam question for the topics in this lecture.
