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 ith
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): 𝑥 .Your job is to select
1
, 𝑥
2
,. . . , 𝑥
𝑛
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 𝑥 then you cannot pick either or ). On
𝑖
𝑥
𝑖−1
𝑥
𝑖
the boundaries, if 𝑥 is chosen, cannot be chosen; if is chosen, then cannot be chosen.
1
𝑥
2
𝑥
𝑛
𝑥
𝑛−1
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.
