S
1
CSE 3101 Design and Analysis of Algorithms
Solutions for Practice Test for Unit 5 Dynamic Programming
Jeff Edmonds
1. In one version of the scrabble game, an input instance consists of a set of letters and a board and the goal is to find a word that returns the most points. A student described the following recursive backtracking algorithm for it. The bird provides the best word out of the list of letters. The friend provides the best place on the board to put the word. Why are these bad questions?
• Answer: Asking to provide the best word is not a “little question” for the bird. She would be doing most of the work for you. Asking the friend to provides the best place on the board to put the word is not a subinstance of the same problem as that of the given instance.
2.
S
1
N 3
S
1
I saw this puzzle on a Toronto subway. The question is how many times the word “TRAINS” appears, winding snaking. We could count them but this might be exponential in the number of squares. Instead, for each box do a constant amount of work and write one integer. In the end, the answer should appear in the box with a “T”. You should give a few sentences explaining the order you fill the boxes and how you do it and how much work it is.
• Answer: In each box with an “S” write a 1. In each box with an “N” write the number of times “NS” appears starting in that box. In each box with an “I” write the number of times “INS” appears starting in that box. Similarly, “AINS”, “RAINS”, and “TRAINS”. As an example, consider the one with “T” in it. Each time “TRAINS” appears starting this box, it must first move from the box “T” to a neighboring box with an R in it and then continue on as “RAINS” starting from there. Hence, the number of times “TRAINS” appears starting in our first box is the sum of the numbers written in the neighboring boxes with an R, i.e. 124 = 31 + 31 + 31 + 31. The boxes should be filled in order S, N, I, A, R, and finally T. No work should be redone. A constant amount of time is spent for each box (or proportional to its degree). Hence, the running time is linear in the number of boxes.
S
1
N 2
I
7
N 2
S
1
S
1
N 2
I
4
A 15
I
4
N
S
1
S
1
N 2
I
4
A 8
R 31
A 8
I
4
N 2
S
1
S
1
N 3
I
7
A 15
R 31
T 124
R 31
A 15
I
7
N 3
S
1
S
1
N 2
I
4
A 8
R 31
A 8
I
4
N 2
S
1
S
1
N 2
I
4
A
I
4
N 2
S
1
S
1
N 2
I
7
N 2
S
1
S
1
N 3
S
1
S
1
S
S
N
S
S
N
I
N
S
S
N
I
A
I
N
S
S
1
N
I
A
R
A
I
N
S
S
1
N 3
I
A
R
T
R
A
I
N
S
S
1
N
I
A
R
A
I
N
S
S
N
I
A
I
N
S
S
N
I
N
S
S
N
S
S
3. (Answer is in the slides) A classic optimization problem is the integer-knapsack problem. For the problem in general, no polynomial algorithm is known. However, if the volume of the knapsack is a small integer, then dynamic programming provides a fast algorithm.
Integer-Knapsack Problem:
Instances: An instance consists of ⟨V, ⟨v1, p1⟩ , . . . , ⟨vn, pn⟩⟩. Here, V is the total volume of the knap-
sack. There are n objects in a store. The volume of the ith object is vi, and its price is pi.
Solutions: A solution is a subset S ⊆ [1..n] of the objects that fit into the knapsack, i.e., i∈S vi ≤ V .
Measure Of Success: The cost (or success) of a solution S is the total value of what is put in the knapsack, i.e., i∈S pi.
Goal: Given a set of objects and the size of the knapsack, the goal is fill the knapsack with the greatest possible total price.
• Answer: The Knapsack Problem:
Algorithm using Trusted Bird and Friend: Consideraparticularinstance,⟨V,⟨v1,p1⟩,…, ⟨vn , pn ⟩⟩ to the knapsack problem. The little bird knows a solution S to it.
2) Question for Bird: I ask the little bird whether or not this optimal solution contains the nth item from the store.
Possible Answers from Bird: There are K = 2 possible answers, Yes and No. No:
3) Constructing Subinstances: If the little bird tells me not to put the nth item into my solution, then we simply delete this last item from consideration. This leaves us with the smaller instance, subIno = ⟨V, ⟨v1, p1⟩ , . . . , ⟨vn−1, pn−1⟩⟩, which we give to a friend. He gives me an optimal solution optSubSol for it.
4) Constructing a Solution for My Instance: Trusting both the bird and the friend, my solution and its value/cost are same as his.
Yes:
3) Constructing Subinstances: If, on the other hand, she says to include the last
item, then we can take this last item and put it into the knapsack first. This leaves a volume of V − vn in the knapsack. We determine how best to fill the rest of the knapsack with the remaining items by asking our friend to solve the smaller instance subIno = ⟨V − vn, ⟨v1, p1⟩ , . . . , ⟨vn−1, pn−1⟩⟩. Here too, he gives me an optimal solution optSubSol for it.
4) Constructing a Solution for My Instance: Trusting both the bird and the friend, my solution is the same as my friends, except I add the nth item in the space of volume vn left for it.
5) Costs of Solution: Having the extra item in it, the value of my solution is pn more then the value of my friend’s.
Yes but wrong:
3) Constructing Subinstances: If the last item does not fit into the knapsack because
vn > V and the bird says to include it, then we politely tell her that she is wrong.
5) Costs of Solution: We set the value of this solution to be −∞ to ensure that it is
not selected as the best one.
Recursive Back Tracing Algorithm:
6) Best of the Best: I can trust the friend because he is a recursive version of myself.
Not actually having a little bird, I try all her answers and take best of best.
7) Base Cases: If there are n = 0 items or the volume of the knapsack is V = 0, then
the only solution is to put nothing in the knapsack for a value of zero. 2
Dynamic Programming Algorithm:
1) The Set of Subinstances: The set of subinstances subI
(Describe). By tracing the recursive algorithm, we see that the set of subinstances evergiventome,myfriends,theirfriendsis{⟨V′,⟨v1,p1⟩,…,⟨vi,pi⟩⟩ |V′ ∈[0..V],i∈ [0..n]}. Note that the items considered are a contiguous prefix of the original items, indicating a polytime algorithm. However, in addition we are considering every possible smaller knapsack size.
Closed: Applying the sub-operator to
⟨V ′, ⟨v1, p1⟩ , . . . , ⟨vi, pi⟩⟩ from this
⟨V′,⟨v1,p1⟩,…,⟨vi−1,pi−1⟩⟩ and ⟨V′ −vi,⟨v1,p1⟩,…,⟨vi−1,pi−1⟩⟩, which are contained in the stated set of subinstances. (The second one is not when V − vn < 0, but we don’t actually recurse in this case.) Therefore, this set contains all subinstances generated by the recursive algorithm.
Generating: For some instances, these subinstances might not get called in the re- cursive program for every possible value of V ′. However, as an exercise you could construct instances for which each such subinstance was called.
3) Construct a Table Indexed by Subinstances: The table indexed by the above set of subinstances will have a dimension for each of the parameters i and V′ used to specify a particular subinstance. The tables will be optCost[0..V,0..n] and birdAdvice[0..V, 0..n].
6) The Order in which to Fill the Table: The friends solve their subinstances (and the table is filled) in an order so that nobody has to wait. (from smaller to larger instances). This could be one row at a time with both i and V ′ increasing, one column at a time, or even diagonally.
8) Code:
algorithm Knapsack(⟨V,⟨v1,p1⟩,...,⟨vn,pn⟩⟩)
⟨pre−cond⟩: V is the volume of the knapsack. vi and pi are the volume and the price of the ith objects in a store.
⟨post−cond⟩: optSol is a way to fill the knapsack with the greatest possible total price. optCost is its price.
begin
% Table: subI [V ′ , i] denotes the subinstance of optimally filling a knapsack with vol-
ume V ′ with the first i objects.
optSol[V ′, i] would store an optimal solution for it, but it is too big. Hence, we store only the bird’s advice birdAdvice[V ′, i] given for the subinstance and the cost optCost[V ′, i] of an optimal solution.
table[0..V, 0..n] birdAdvice, optCost
% Base Cases: The base cases are when the number of objects is zero.
For each, the solution is the empty knapsack with cost zero.
(If the knapsack has zero volume, then nothing will fit in it until there are zero items.)
loop V ′ = 0..V
% optSol[V ′, 0] = ∅
optCost[V ′, 0] = 0
birdAdvice[V ′, 0] = ∅ end loop
% General Cases: Loop over subinstances in the table. loop i = 1 to n
loop V ′ = 0 to V
% Solve instance subI[V ′, i] and fill in the table at index ⟨V ′, i⟩.
3
set
an arbitrary subinstance constructs subinstances
% The bird and Friend Alg: The bird tells us either (1) exclude the ith item from the knapsack or (2) include it. Either way, we remove this last object, but in case (2) we decrease the size of the knapsack by the space needed for this item. Then we ask the friend for an optimal packing of the resulting subinstance. He gives us (1) optSol[V′,i − 1] or (2) optSol[V′ − vi,i − 1] which he had stored in the table. If the bird had said we were to include the ith item, then we add this item to the friend’s solution. Denote this resulting solution by optSol⟨⟨V ′,i⟩,k⟩. It is a best packing for our instance subI ⟨V ′, i⟩ from amongst those consistent with the bird’s kth answer.
% Try each possible bird answers.
% cases k = 1, 2 where 1=exclude 2=include
%optSol⟨⟨V′,i⟩,1⟩ =optSol[V′,i−1] optCost⟨⟨V′,i⟩,1⟩ =optCost[V′,i−1] if(V ′ − vi ≥ 0) then
% optSol⟨⟨V ′,i⟩,2⟩ = optSol[V ′ − vi, i − 1] ∪ i
optCost⟨⟨V ′,i⟩,2⟩ = optCost[V ′ − vi, i − 1] + pi else
% Bird was wrong
% optSol⟨⟨V ′,i⟩,2⟩ =? optCost⟨⟨V ′,i⟩,2⟩ = −∞
end if
% end cases
% Having the best, optSol⟨⟨V ′,i⟩,k⟩, for each bird’s answer k, we keep the best of these best.
kmax = “a k that maximizes optCost⟨⟨V ′,i⟩,k⟩” % optSol[V ′, i] = optSol⟨⟨V ′,i⟩,kmax⟩
optC ost[V ′ , i] = optC ost⟨⟨V ′ ,i⟩,kmax ⟩ birdAdvice[V ′, i] = kmax
end for end for
optSol = KnapsackW ithAdvice (⟨V, ⟨v1, p1⟩ , . . . , ⟨vn, pn⟩⟩ , birdAdvice)
return ⟨optSol, optCost[V, n]⟩ end algorithm
8’) Constructing the Solution: We would run the recursive algorithm with the bird’s advice to find the solution to our instance. We exclude this step from our answer.
9) Running Time: The number of subinstances is Θ(V · n) and the bird chooses be- tween two options: to include or not to include the object. Hence, the running and the space requirements are both Θ(V · n). However, this running time should be ex- pressed as a function of input size. The number of bits needed to represent the instance ⟨V′,⟨v1,p1⟩,...,⟨vn,pn⟩⟩ is N = |V|+n·(|v|+|p|), where |V|, |v|, and |p| are the the numbers of bits needed to represent V , vi, and pi. Expressed in these terms, the running time is T (|instance|) = Θ(nV ) = Θ(n2|V | ). This is quicker than the brute force algorithm because its running time is polynomial in the number of items n. In the worst case, however, V is large and the time can be exponential in the number of bits N. I.e., if |V | = Θ(N), then T = Θ(2N ). In fact, the knapsack problem is one of the classic NP complete problems, which means that it is generally believed that not polynomial time algorithm exists for it.
4. Stock Market Prices You are very lucky to have a time machine bring you the value each day of a set of stocks. The input instance to your problem consists of I = ⟨T , S, P rice⟩, where T is an integer indicating your last day to be in the market, S is the set of |S| stocks that you consider, and Price is a table such that P rice(t, s) gives the price of buying one share of stock s on day t. Buying stocks
4
costs an overhead of 3%. Hence, if you buy p dollars worth of stock s on day t, then you can sell them on day t′ for p · (1 − 0.03) · Price(t′,s). You have one dollar on day 1, can buy the same stock many
P rice(t,s)
times, and must sell all your stock on day T. You will need to determine how you should buy and sell
to maximize your profits.
Because you know exactly what the stocks will do, there is no advantage in owning more than one
stock at a time. To make the problem easier, assume that at each point time there is at least one
stock not going down and hence at each point in time you alway own exactly one stock. A solution
will be viewed a list of what you buy and when. More formally, a solution is a sequence of pairs
⟨ti,si⟩, meaning that stock si is bought on day ti and sold on day ti+1. (Here i ≥ 1, t1 = 1 and
tlast+1 = T .) For example, the solution ⟨⟨1, 4⟩ , ⟨10, 8⟩ , ⟨19, 2⟩⟩ means that on day 1 you put your one
dollar into the 4th stock, on day 10 you sell all of this stock and buy the 8th stock, on day 19 you
sell and buy the 2nd stock, and finally on day T you sell this last stock. The value of this solution is
Πi(1−0.03)·Price(ti+1,si)=1·(1−0.03)·Price(10,4) ·(1−0.03)·Price(19,8) ·(1−0.03)· Price(T,2). P rice(ti ,si ) P rice(1,4) P rice(10,8) P rice(19,2)
(Note that the symbol Πi works the same as i except for product.)
Design for a dynamic programming algorithm for this stock buying problem. Be sure to include ALL the steps given in the solution for the assignment. Hint: Ask the bird for the last “object” in the solution. Be sure to explain what this means.
• Answer:
1) Specifications: (See question) An input instance consists of I = ⟨T , S, P rice⟩, where T is the day that I must sell, S is the set of stocks, and P rice gives the prices. A solution is a sequence of pairs ⟨ti, si⟩, meaning that stock si is bought on day ti and sold on day ti+1. (Here i ≥ 1,
t1 =1andtlast+1 =T.) ThevalueofthissolutionisΠi(1−0.03)·Price(ti+1,si). P rice(ti ,si )
Algorithm using Trusted Bird and Friend: I have my instance I = ⟨T,S,Price⟩. The little bird knows a solution to it.
2) Question for Bird: I ask the little bird what is the last object ⟨tk,sk⟩ in the solution,
namely what stock sk ∈ S I should buy last and one what day tk ∈ [1..T − 1] I should
buy it. Note I will sell this stock on day T.
2’) Possible Answers from Bird: There are T ·|S| different answers ⟨tk, sk⟩ that she might
give.
3) Constructing Subinstances: Given the bird wants me to buy on day tk and I sell and
buy on the same day, I need my friend to tell me what and when to buy and sell so as to sell on day tk. Therefore, I give him the subinstance subI = ⟨tk,S,Price⟩. Note, I do not need to change the set of stocks considered and even though he wont use the entire table Price, we don’t need to change it either. He gives me an optimal solution optSubSol for it.
4) Constructing a Solution for My Instance: I produce an optimal solution optSol for my instance I from the bird’s answer k and the friend’s solution optSubSol simply by tacking the last object ⟨tk,sk⟩ on to the end of the friend’s solution. This means that my friend and I buy and sell the same stocks on the same days, we both sell on day tk, then I continue on to buy stock sk on this same day tk, later to sell it on day T.
5) Costs of Solution: If optSubCost is the cost of my friend’s optimal solution optSubSol
for his instance subI, then my cost optCost to my solution optSol is optSubCost × (1−0.03)· Price(T,sk)
Price(tk,sk) Recursive Back Tracing Algorithm:
6) Best of the Best: I can trust the friend because he is a recursive version of myself. Not actually having a little bird, I try all her answers and take best of best.
7) Base Cases: The base case instance is when we have to sell on day one. Its solution is to never buy or sell anything. It’s value is one because we still have the dollar that we started with.
5
Dynamic Programming Algorithm:
1) The Set of Subinstances: We determine the set of subinstances subI = ⟨t, S, P rice⟩
ever given to me, my friends, their friends. For each day t ∈ [1..T ], there is a subinstance that asks what to buy and sell so that on day t you sell your last stock and maximize the amount of money you have on that day. There are T such subinstances. Note that this set is closed under this “sub”-operator and all of these subinstances are needed.
3) Construct a Table Indexed by Subinstances: The table is simply indexed by t ∈ [1..T ]. We don’t actually store the solution optS [t] for the subinstance subI [t], but optCost[t] is the cost of this solution and birdAdvice[t] stores the birds advice given on this subinstance.
6) The Order in which to Fill the Table: The friends solve their subinstances (and the table is filled) in an order so that nobody has to wait. (from smaller to larger instances). This is simply for t = 1...T.
8) Code:
algorithm Stocks(T,S,Price)
⟨pre−cond⟩: T is the day that I must sell, S is the set of stocks, and Price gives the
prices.
⟨post − cond⟩: optS ol is an optimal valid schedule. It is a sequence of pairs ⟨ti , si ⟩,
meaning that stock si is bought on day ti and sold on day ti+1. optCost is its cost. begin
% Table: subI[t] denotes the subinstance of finding an optimal schedule ending on day t.
optSol[t] would store an optimal solution for it, but it is too big. Hence, we store only the bird’s advice birdAdvice[t] given for the subinstance and the cost optCost[t] of an optimal solution.
table[1..T ] optCost, birdAdvice
% Base Case: The only base case is for the optimal set ending on day t = 1. It’s solution consists of the empty set with value 1.
% optSol[1] = ∅ optCost[1] = 1 birdAdvice[1] = ∅
% General Cases: Loop over subinstances in the table. for t = 2 to T
% Solve instance subI[t].
% Try each possible bird answer. for each tk ∈ [1..t − 1]
for each sk ∈ S
% The bird and Friend Alg: I want to finish on day t. I ask the bird
what stock si ∈ S I should buy last and what day ti ∈ [1..t−1] I should buy it. She answers ⟨tk , sk ⟩. I ask my friend to solve the subinstance that ends on day tk. I produce an optimal solu- tion optSol for my instance subI[t] from the bird’s answer k and the friend’s solution optSubSol simply by tacking the last object ⟨tk,sk⟩ on to the end of the friend’s solution. This means that my friend and I buy and sell the same stocks on the same days except after we both sell everything on day tk, I buy stock sk later to sell it on day T.
Denote this resulting solution by optSol⟨t,⟨tk,sk⟩⟩. It is a best so-
lution for our instance subI[t] from amongst those consistent with
the bird’s ⟨tk,sk⟩th answer.
% optSol⟨t,⟨tk,sk⟩⟩ = optSol[tk] + ⟨tk, sk⟩
6
optCost⟨t,⟨tk,sk⟩⟩ = optCost[tk]·(1−0.03)· Price(t,sk) P rice(tk ,sk )
end for
% Having the best, optSol⟨t,⟨tk,sk⟩⟩, for each bird’s answer ⟨tk,sk⟩, we keep the best
of these best.
⟨tmax,smax⟩ = “a ⟨tk,sk⟩ that maximizes optCost⟨t,⟨tk,sk⟩⟩”
% optSol[t] = optSol⟨t,⟨tmax,smax⟩⟩ optCost[t] = optCost⟨t,⟨tmax,smax⟩⟩ birdAdvice[t] = ⟨tmax, smax⟩
end for
optSol = SchedulingW ithAdvice (T, S, P rice, birdAdvice) return ⟨optSol, optCost[T ]⟩
end algorithm
8’) Constructing the Solution: We would run the recursive algorithm with the bird’s ad-
vice to find the solution to our instance. We exclude this step from our answer.
9) Running Time:
The number of subinstances in the table is T.
The number of bird answers is T · |S|.
The running time is the product of these O(T 2 · |S|).
5. Dynamic Programming the Narrow Art Gallery Problem:
(See ACM contest open.kattis.com/problems/narrowartgallery):
A long art gallery has 2N rooms. The gallery is laid out as N rows of 2 rooms side-by-side. Doors connect all adjacent rooms (north-south and east-west, but not diagonally). The curator has been told that she must close off r of the rooms because of staffing cuts. Visitors must be able to enter using at least one of the two rooms at one end of the gallery, proceed through the gallery, and exit from at least one of the two rooms at the other end. Therefore, the curator must not close off any two rooms that would block passage through the gallery. That is, the curator may not block off two rooms in the same row or two rooms in adjacent rows that touch diagonally. Furthermore, she has determined how much value each room has to the general public, and now she wants to close off the set r rooms that minimize the sum of the values of the rooms closed, without blocking passage through the gallery.
Figure 1: Shows an example of an art gallery of N = 10 rows and 2 columns of rooms. The number of rooms to close is r = 5. The number 1-10 in each room gives its value. The gray rooms indicate which should be closed in the optimal solution.
(a) Algorithmic Paradigms:
Tell me which one is wrong or say all are right.
A: An iterative algorithm takes one step at a time. During each it makes a little progress while maintaining a loop invariant.
A recursive algorithm asks his friends any instance that is smaller and meets the precondition. It is best not to micro managing these friends.
B: A greedy algorithm grabs the next best item and commits to a decision about it without concern for long term consequences.
C: A recursive backtracking algorithm tries various things. For each thing tried it recurses. Then it backtracks and tries something different.
D: A dynamic programming algorithm fills in a table with a cell for each of a set of subinstances. Each is solved in the same way as one stack frame of the recursive backtracking algorithm.
E: They are all right.
• Answer: E: They are all right.
(b) Specification of the Narrow Art Gallery problem: Tell me which one is wrong or say all are right.
7
A: An instance is specified by I = ⟨N, r, value(1..N, 1..2)⟩ where N is the number of rows. 2 is the numberofcolumns. risthenumberofroomstoclose. Forn∈[1..N]andside∈{left,right}, value(n, side) is the value of this room, i.e. the cost of closing it.
B: A solution is a subset of the 2N rooms of size r.
C: A solution is valid if a visitor traveling only east-west or north-south is able to enter the top
of the gallery and leave though the bottom without traveling through a closed room. See the white path of rooms in the figure. For example, they closed the room of value 3 instead of the less valuable room next to it of value 2 because otherwise the public could not walk through.
D: The cost of such a solution is the sum of the values of the rooms closed. The goal is to minimize this cost.
E: They are all right.
• Answer: E: They are all right.
(c) What is the nature of the bird? Tell me which one is wrong.
A: There is no bird. There is no spoon (Quote from Matrix)
B: She helps us pose what we want to try.
C: We imagine her giving us a little answer about the solution.
D: She represents an algorithmic technique for learning part of the solution. E: She helps us trust what we are trying so that we can go on.
• Answer: D is wrong.
(d) What is the nature of the friend?
Tell me which one is wrong.
A: There is no friend. There is no spoon (Quote from Matrix)
B: I know you. You are just like me.
C: You don’t micro manage him because it’s too confusing.
D: You can give him anything that meets the precondition and that is smaller. E: Recursion
• Answer: A is wrong.
(e) Why does the bird tell you something about the end of the solution instead of the beginning?
A: It far too confusing the other way.
B: Esthetically the dynamic programming algorithm looks better going forward. C: Esthetically the dynamic programming algorithm looks better going backwards. D: It makes the algorithm faster.
E: The bird only knows about the beginning.
• Answer: B is right.
(f) Given the instance in the figure, I will ask bird:
“Should I close the bottom left room (i.e. labeled 7), the bottom right room (i.e. labeled 9), or neither of them.”
Tell me which one is wrong or say all are right.
A: It is ok not to worry here about r or the higher rooms.
B: The answer she gives is k ∈ {lef t, right, none}. The number of bird answers we will have to
try is 3.
C: I don’t just ask just about the bottom right room, because if we just delete it, the friend’s instance would be a funny shape.
D: I don’t include the option of closing both of them, because that is not valid. 8
E: They are all right.
• Answer: E: They are all right.
(g) One option is that we delete the bottom row of rooms (i.e. labeled 7&9) and we give the friend the first N −1 rows of rooms.
Tell me which one is wrong or say all are right.
A: We must also give the friend the new number rfriend of rooms to close which is our number r to close minus the number the bird closed.
B: We expect the friend to find the optimal solution for this.
C: The obvious solution for our instance of N rows is to close the rooms that our friend told us
to close and to close the rooms that the bird told us to close.
D: The problem with this obvious solution is that if the bird tells us to close the bottom left room (i.e. labeled 7) and the friend tells us to close the room on the right in the second last row (i.e. labeled 3), then the solution will not be valid because the public would not be able to exit out of the bottom of the gallery.
E: They are all right.
• Answer: E: They are all right.
Our buildings will always be rectangular with two columns. The public is allowed to enter either via the top left or the top right room. However, we are going to restrict the way that the public is allowed to leave the bottom of the gallery. We change the problem so that in addition to what has been specified above, the instance includes a parameter door ∈ {lef t, right, both} which tells us whether the public can leave the gallery though the bottom left room but not the bottom right, the bottom right room but not the left, or both the bottom left and the bottom right. For our initial instance, door = both.
(h) Suppose we are given the instance in the figure and the bird tells us either to close the bottom left, bottom right or none of the rooms on the bottom row. Tell me about the instance that we give our friend.
Tell me which one is right or say all are wrong.
A: The set of rooms he gets is the same as the set of rooms we get.
B: We change some of the values of the rooms for our friend’s instance.
C: Because the bird told us the solution for this last row of rooms, we delete this last row from our friend’s instance. We give the friend our first Nf riend = N −1 rows.
D: We remove just the room that the bird closes. E: They are all wrong.
• Answer: C is right.
(i) Suppose we are given the instance in the figure and the bird tells us to close the bottom left room, i.e. k = left. Tell me about the instance that we give our friend.
Tell me which one is right or say all are wrong.
A: The number of rooms r that must be closes is fixed by the boss and does not change.
B: We do not need to tell the friend how many rooms to close because his bird will tell him that.
C: The bird tells us the total number of rooms to close.
D: The number of that my friend’s instance needs closed is one less than the number we must close, i.e. rfriend = r−1.
E: They are all wrong. • Answer: D is right.
(j) Suppose we are given the instance in the figure and the bird tells us to close the bottom left room, i.e. k = left. Tell me about the instance that we give our friend.
Tell me which one is right or say all are wrong.
9
A: There is no need for doors.
B: The friend’s instance will have no door on the bottom left, i.e. doorfriend = right. This models the fact there is a pseudo room below his bottom left room that is closed and hence the public cannot enter his bottom left room in this way.
C: The friend’s instance will have no door on the bottom right, i.e. doorfriend = left. This models the fact there is a pseudo room below his bottom left room that is closed and hence the public cannot enter his bottom left room in this way.
D: In this case, the friend should be given a door both on the left and on the right. This gives the public the correct level of access.
E: They are all wrong. • Answer: B is right.
(k) Suppose we are given the instance in the figure except for the fact that there is no door on the bottom left, i.e. door = right. Tell me about the instance that we give our friend.
Tell me which one is wrong or say all are right.
A: The whole business with the doors is done to avoid the following bug. If the bird tells us to close the bottom left room (i.e. labeled 7) and the friend tells us to close the room on the right in the second last row (i.e. labeled 3), then the solution will not be valid because the public would not be able to exit out of the bottom of the gallery.
B: Closing the only room on the bottom with a door will prevent the public from leaving. Hence, we will not allow the bird to close the bottom right room, i.e. if she says that k = right, then we politely tell her that she is wrong.
C: We politely tell the bird she is wrong by setting optCost⟨I,k⟩ = ∞. Being a minimization problem, this option will never be selected.
D: Sometimes when writing a recursive program, we need to change the preconditions so that the friend gives us the answer that meets our needs. When converting this into a dynamic programming algorithm, this makes a larger set of subinstances.
E: They are all right.
• Answer: E: They are all right.
(l) Dynamic Programming:
Tell me which one is wrong or say all are right.
A: This recursive back tracking algorithm effectively tries every possible solution, i.e. brute force. The time is exponential.
B: Recursive back tracking is a common algorithmic technique that is used in artificial intelligence (certainly before machine learning).
C: A dynamic programming algorithm saves time by in a way similar to that the greedy algorithm works, i.e. if the existence of an optimal solution consistent with decision A implies the existence of an optimal solution consistent with decision B, then decision A does not need to be tried.
D: A dynamic programming algorithm saves time by not solving the same subinstance more than once.
E: They are all right.
• Answer: C is wrong: It is right for greedy algorithms, but this is not done in dynamic
programming.
(m) We start the dynamic programming algorithm by setting up a table indexed by all of the subin- stances that some friend friend friend will have to solve.
Tell me which one is wrong or say all are right.
A: This table will have a dimension that is indexed by the number of rows N′ ∈ [0..N] that the friend will consider.
10
B: This table will have a dimension that is indexed by the number of rooms r′ ∈ [0..r] that the friend will have to close.
C: This table will have a dimension indicating the values of the each room, i.e. the numbers 0 to 10 in the figure.
D: This table will have a dimension that is indexed by the parameter door ∈ {lef t, right, both}. E: They are all right.
• Answer: C is wrong.
(n) What needs to be true about the set S of subinstances being solved?
Tell me which one is wrong or say all are right.
A: Include our original instance. (Invite the bride and groom.)
B: Closed under the friend operation. For every subinstance I′ ∈ S, all of I′’s friends must also
be in S. (If you invite your aunt, then you must invite her friends.)
C: Don’t have too many things in S that are not asked by some friend’s friend.
D: Sometimes it is too hard to tell if some I′ is actually asked by some friend’s friend. Then we
just put it in S for good luck. E: They are all right.
• Answer: E: They are all right.
(o) The number of subinstance that we must solve is:
A: N×r×10×2N B: 2N
C: 3rN
D: O(r+N)
E: exponential (say in N, r, or the number of bits to write down the values of the rooms.) • Answer: C is right.
(p) Each cell of the table (tables)
Tell me which one is wrong or say all are right.
A: Is indexed by a subinstance to be solved.
B: Stores the optimal solution for that subinstance.
C: Stores the cost of optimal solution for that subinstance. D: Stores the bird’s advice for that subinstance.
E: They are all right.
• Answer: B is wrong.
(q) What order should the subinstances in the table be completed.
Tell me which one is wrong or say all are right.
A: Smallest to largest.
B: In an order that nobody waits, i.e. when a subinstance is solved, all of his friends have already
been solved. When its your aunt’s job, her friends are already done and gotten drunk. C: If the table is two dimentional, you have to fill it in diagonally.
D: Basecases first. Our instance last.
E: They are all right.
• Answer: C is wrong.
(r) What are the base cases?
Tell me which one is wrong or say all are right. A: The smallest subinstances in your table.
B: Subinstances that don’t have any friends.
11
C: Subinstances for which the generic code does not work. D: Subinstances that you can solve easily on your own.
E: They are all right.
• Answer: E: They are all right.
(s) The base cases are handled as follows.
Tell me which one is right or say all are wrong.
A: if(r≤0)thenreturn(noroomsneedtobeclosed)
B: if(N≤0)thenreturn(noroomstoclose)
C: if( N < r ) then return( more rooms to close than can be closed )
D: % The cost of the solution is the sum of that values of the rooms closed. Hence, if there are r = 0 rooms to close, then the cost is zero.
for all entries of the table for which r′ = 0, optCost[...r; ..] = 0
E: They are all wrong.
• Answer: D is right: The case that N < r has no solution and is handled in the code.
(t) Dynamic Programming
Tell me which one is wrong or say all are right.
A: To solve our instance, we recursively ask friends to solve smaller subinstances.
B: We loop over all subinstances from smallest to largest.
C: The word “Memoization” comes from the word “Memo,” i.e. to write nodes about what has happened already.
D: To solve our instance, we look in the table to see what our friends have stored about smaller subinstances.
E: They are all right.
• Answer: A is wrong.
(u) The first thing a dynamic program does is:
Tell me which one is right or say all are wrong.
A: Ask the bird about an optimal solution of the inputted instance. B: Set up the table.
C: Check if the input is a base case.
D: Check if the input has the correct format.
E: They are all wrong. • Answer: B is right.
(v) We combine the cost of our friend’s solution and the cost of our bird’s solution k to get: Tell me which one is right or say all are wrong.
A: The cost of an optimal solution optCostI′ for the instance I′.
B: The cost of an optimal solution optCost⟨I′,k⟩ for the instance I′ from amongst those that are
consistent with this bird’s answer k.
C: We need to compute the optimal solution.
D: The whole idea of combining is misrepresents the technique. E: They are all wrong.
• Answer: B is right.
(w) Consider a dynamic programming routine named RoomClosures. A key line of its is:
Tell me which one is right or say all are wrong.
A: optCost.. = optCost[Ifriend] + GetBirdsCost(...)
12
B: optCost.. = RoomClosures(Ifriend) + optCostbird where if( k = left ) then opCostbird = value(N′,left).
C: optCost.. = optCost[Ifriend] + optCostbird where if( k = none ) then opCostbird = 0.
D: optCost.. = RoomClosures(Ifriend) + GetBirdsCost(...) E: They are all wrong.
• Answer: C is right: The friend’s answer is looked up in the table and the bird’s answer is the current one we are trying.
(x) Dynamic Programming
Tell me which one is wrong or say all are right.
A: We try all bird answers.
B: Having the best, optSol⟨I′,k⟩, for each bird’s answer k, we keep the best of these best.
C: The following is reasonable pseudo code. kmin = “a k that minimizes optCost⟨I′,k⟩”
D: Options A, B, and C need to be done in dynamic programming but not in recursive back- tracking.
E: They are all right.
• Answer: D is wrong.
(y) Finishing up the dynamic programming algorithm. Tell me which one is wrong or say all are right.
A: The following is where the memo is being taken. optCost[I′] = optCost⟨I′,kmin⟩.
B: The following is key line of how Jeff does dynamic programming, but you likely won’t hear anyone else talk about it. birdAdvice[I′] = kmin.
C: The algorithm optSol = AlgW ithAdvice (I, birdAdvice) reruns the algorithm but this time it is fast because now there really is a bird.
D: The algorithm AlgWithAdvice and the greedy algorithm both follow one path down the decision tree.
E: They are all right.
• Answer: E: They are all right.
(z) Running time of dynamic programming algorithms. Tell me which one is wrong or say all are right.
A: The running time of a dynamic programming algorithm is the number of subinstances times the number of bird answers.
B: If an optimal solution is found in the inner loop then the time is multiplied by the number of bits to write down the solution.
C: Finding an optimal solution when the bird’s advice is known is fast. The time is in linear in the number of bits to write down the solution.
D: If the input consists of n objects and each subset of these objects is a subinstance, then the number of subinstances is exponential. This occurring with the obvious dynamic programming algorithm is a very common reason for a problem to be NP-complete, i.e. no polynomial algorithm for it is known.
E: They are all right.
• Answer: E: They are all right.
6. More questions past z.
(a) Which is true about the running time of our RoomClosures dynamic program?
13
A: The running time of this algorithm is proportional to the number of rows of rooms N. The size of the input includes the logN bits to represent N. This means that this dynamic programming algorithm runs in exponential time just like the Knapsack problem.
B: The running time of this algorithm is proportional to the number of rooms to close r. The size of the input includes the log r bits to represent r. This means that this dynamic programming algorithm runs in exponential time just like the Knapsack problem.
C: A and B.
D: The running time of this algorithm is quadratic in the size of the input. E: They are all wrong.
• Answer: D is right: The size the input is dominated by the table value whose description requires at least N bits. Lets say size = Θ(N). The number of rooms to close is at most the number of rows, i.e. r ≤ N or else the solution is impossible. The running time is the number of subinstances times the number of bird answers which is T ime(size) = 3N r × 3 = O(N2) = O(size2).
(b) Suppose instead of the number of columns being restricted to 2, the gallery could have width w. Consider extending the same basic algorithm done above.
Tell me which one is wrong or say all are right.
A: The running time would increase by a factor of w.
B: We would still ask the bird which rooms to close on the bottom row.
C: The number of bird answers would now be Θ(2w).
D: This problem is NP-complete, i.e. no polynomial algorithm for it is known. E: They are all right.
• Answer: A is wrong.
(c) Write out the code for the RoomClosure algorithm developed here. 14
algorithm DynamicProgrammingAlgforRoomClosures(N,r,value(1..N,1..2))
⟨pre−cond⟩: N is the number of rows. 2 is the number of columns. r is the number of rooms to close. For n ∈ [1..N ] and side ∈ {lef t, right}, value(n, side) is the value of this room, i.e. the
cost of closing it.
⟨post−cond⟩: A solution is a subset of the 2N rooms of size r.
A solution is valid if a visitor traveling only east-west or north-south is able to enter the top of the gallery and leave though the bottom without traveling through a closed room. See the white path of rooms in the figure.
The cost of such a solution is the sum of the values of the rooms closed. The goal is to minimize this cost.
The program returns optSol which is an optimal solution for this instance and optCost which is it’s cost.
begin
%Table: subI[N′,r′,door′]denotesthesubinstanceinwhichweconsiderthefirstN′ ∈[0..N]columns
of the rooms, we close r′ ∈ [0..r] of the rooms, and door′ ∈ {lef t, right, both} specifies which of the rooms on the bottom have doors.
optSol[N′,r′,door′] would store an optimal solution for it, but it is too big. Hence, we store only the bird’s advice birdAdvice[N′,r′,door′] given for the subinstance and the cost optCost[N′, r′, door′] of an optimal solution.
table[0..N, 0..r, 0..2] optCost, birdAdvice
% Base Cases: When the number of rooms r′ to close is zero, the solution is to close zero
rooms with a cost of zero. We won’t worry about the number N′ of rows being zero because
we will make sure that N′ ≥ r′.
for N ′ ∈ [0..N ], for door′ ∈ {lef t, right, both}
% optSol[N′,0,door′] = no rooms optCost[N′,0,door′] = 0 birdAdvice[N′, 0, door′] = none
end loop
% General Cases: Loop over subinstances in the table.
for N′ ∈ [0..N], for r′ ∈ [0..min(r, N′)], for door′ ∈ {left, right, both}
% Solve instance subI[N′, r′, door′] and fill in table entry ⟨N′, r′, door′⟩. % Try each possible bird answer.
for k ∈ {lef t, right, none}
% The bird and Friend Alg: Our instance either has N ′ rows of rooms, r′ rooms to close and a door on the door′ ∈ {lef t, right, both}. We ask the bird whether to close the bottom left room, the bottom right, or neither. She answers k ∈ {lef t, right, none}. Given the bird has handled the bottom row indexed N′, we ask the friend about the first Nfriend = N′ − 1 rows. If the bird says to close a room, then we ask the friend to close one few doors, i.e. rfriend = r′−1. Similarly, if she says to close no rooms, then rfriend = r′. If the bird answers to delete the bottom left room, then we give the friend the instance no door on the bottom left, i.e. if k = left then doorfriend = right. Similarly, if the bird answers k = right, then doorfriend = left. If the bird closes no rooms on the bottom then we leave both of the friend’s doors open, i.e. if k = none then doorfriend = both. If we must close one room per row, i.e. N′ = r′, then we make sure the bird closes at least one room. This ensures that Nfriend ≥ rfriend. If we are given the instance with no door on the bottom left, then we will not allow the bird to close the bottom right room, otherwise, the public can’t get out, i.e. it is not the case that door′ = right and k = right. Otherwise, we combine our friend’s room closures solution with that of the bird.
15
% Create friend’s instance and bird’s cost. Nfriend =N′−1
if( k = left ) then
rfriend =r′−1
doorfriend = right opCostbird = value(N′, left)
elseif( k = right ) then
rfriend =r′−1
doorfriend = left
optCostbird = value(N′, right)
elseif( k = none ) then
rfriend = r′ doorfriend = both optCostbird = 0
endif
% Build our solution and cost from friend’s and bird’s solutions.
if( Nfriend < rfriend or (door′ = left and k = left) or (door′ = right and k = right) ) then
% optSol⟨⟨N′,r′,door′⟩,k⟩ = error optCost⟨⟨N′,r′,door′⟩,k⟩ = ∞
else
% optSol⟨⟨N′,r′,door′⟩,k⟩ = optSol[Nfriend, rfriend, doorfriend] + k optCost⟨⟨N′,r′,door′⟩,k⟩ = optCost[Nfriend, rfriend, doorfriend] + optCostbird
endif end for
% Having the best, optSol⟨⟨N′,r′,door′⟩,k⟩, for each bird’s answer k, we keep the best of these best. kmin = “a k that minimizes optCost⟨⟨N′,r′,door′⟩,k⟩”
% optSol[N′, r′, door′] = optSol⟨⟨N′,r′,door′⟩,kmin⟩
optCost[N′, r′, door′] = optCost⟨⟨N′,r′,door′⟩,kmin⟩
birdAdvice[N′, r′, door′] = kmin end for
optSol = AlgW ithAdvice (N, r, value(N, 2), birdAdvice)
return ⟨optSol, optCost[N, r, both]⟩ end algorithm
16