## 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.