Description
1. Given a non-empty string s and a dictionary containing a list of unique words, design a dynamic
programming algorithm to determine if s can be segmented into a space-separated sequence of one or
more dictionary words. If s = “algorithmdesign” and your dictionary contains “algorithm” and “design”.
Your algorithm should answer Yes as s can be segmented as “algorithm design”.
2. Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by
array nums. You are asked to burst all the balloons. If you burst balloon i you will get nums[left] * nums[i]
* nums[right] coins. Here left and right are adjacent indices of i. After bursting the balloon, the left and
right then become adjacent. You may assume nums[-1] = nums[n] = 1, and they are not real, therefore,
you can not burst them. Design a dynamic programming algorithm to find the maximum coins you can
collect by bursting the balloons wisely. Analyze the running time of your algorithm.
3. You are in Downtown of a city where all the streets are one-way streets. At any point, you may go right
one block, down one block, or diagonally down and right one block. However, at each city block (i, j) you
have to pay the entrance fees fee(i, j). The fees are arranged on a grid as shown below. Your objective is to
travel from the starting point at the city’s entrance, located at block (0,0), to a specific destination block
(n, n). The city is laid out in a grid, and at each intersection or block (i, j), you might either incur a cost
(pay an entrance fee) or receive a reward (get a payback) for passing through. These transactions are
captured in a grid, with positive values representing fees and negative values representing paybacks You
would like to get to your destination with the least possible cost. Formulate the solution to this problem
using dynamic programming
a. Define (in plain English) subproblems to be solved.
b. Write the recurrence relation for subproblems.
4. Assume we have N workers. Each worker is assigned to work at one of M factories. For each of the
M factories, they will produce a different profit depending on how many workers are assigned to that
factory. We will denote the profits of factory i with j workers by P(i,j). Develop a dynamic programming
solution to find the assignment of workers to factories that produce the maximum profit.(Mention the
pseudocode)
5. You have two rooms to rent out. There are n customers interested in renting the rooms. The i
th
customer wishes to rent one room (either room you have) for d[i] days and is willing to pay bid[i] for the
entire stay. Customer requests are non-negotiable in that they would not be willing to rent for a shorter
or longer duration. Devise a dynamic programming algorithm to determine the maximum profit that you
can make from the customers over a period of D days.
a) Define (in plain English) subproblems to be solved. b) Write the recurrence relation for subproblems.
6. You are given a sequence of n numbers (positive or negative) x1, x2, . . . , xn. Your job is to select a subset
of these numbers of maximum total sum, subject to the constraint that you can’t select two elements that
are adjacent (that is, if you pick xi then you cannot pick either xi−1 or xi+1. On the boundaries, if x1 is
chosen, x2 cannot be chosen; if xn is chosen, then xn−1 cannot be chosen. Give a dynamic programming
solution to find, in time polynomial in n, the subset of maximum total sum.
7. Suppose you have a rod of length N, and you want to cut up the rod and sell the pieces in a way that
maximizes the total amount of money you get. A piece of length i is worth pi dollars. Devise a Dynamic
Programming algorithm to determine the maximum amount of money you can get by cutting the rod
strategically and selling the cut pieces.
