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