racket | Algorithm代做 | 代写angular | AI | assignment – Algorithms Tutorial 4

Algorithms Tutorial 4

racket | Algorithm代做 | 代写angular | AI | assignment – 这个题目属于一个racket的代写任务, 包括了racket/Algorithm/AI等方面, 这个项目是assignment代写的代写题目

Solutions

1. You are traveling by a canoe down a river and there arentrading posts along the way. Before starting your journey, you are given for each 1i < jnthe feeF(i, j) for renting a canoe from postito postj. These fees are arbitrary. For example it is possible thatF(1,3) = 10 andF(1,4) = 5. You begin at trading post 1 and must end at trading postn(using rented canoes). Your goal is to design an efficient algorithms which produces the sequence of trading posts where you change your canoe which minimizes the total rental cost. Solution:We solve the following subproblem: Find the minimum cost it would take to reach posti. The base case is opt(1) = 0. The recursion is:

opt(i) = min{opt(j) +F(j, i) : 1j < i}, i > 1 ,

To reconstruct the sequence of trading posts the canoe had to have visited, we
define the following function:

from(i) = arg min
1 j<i

{opt(j) +F(j, i)}, i > 1.

(Note: arg min returns the value of j that produces the minimal value of
opt(j) +F(j, i)). The minimum cost is opt(n). To get the sequence, we
backtrack from postngiving the sequence{n,from(n),from(from(n)), ..., 1 }.
Reverse this to get the boats journey.
The complexity isO(n^2 ) because there arensubproblems, and each subproblem
takesO(n) to find the best previous trading post.

2. You are given a set ofntypes of rect angular boxes, where the ithbox has heighthi, widthwiand depthdi. You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the

dimensions of the 2-D base of the lower box are each strictly larger than those
of the 2-D base of the higher box. Of course, you can rotate a box so that any
side functions as its base. It is also allowable to use multiple instances of the
same type of box.
Solution: First, since each box type has six different box rotations (there are
three faces and each face can be rotated once, exchanging width and depth),
it is easier to treat these rotations as being separate boxes entirely. This gives
6 nboxes in total, and allows us to assume that boxes cannot be rotated. We
now order these boxes in a decreasing order of the surface area of their base.
Notice that in this way if a boxB 1 can go on top of a boxB 0 thenB 0 precedes
boxB 1 in such an ordering.
We aim to solve the following subproblem: What is the maximum height pos-
sible for a stack if the top most box is box numberi? The recursion is:

opt(i) = max{opt(j) +hi: over alljsuch thatwj> wianddj> di}.

The final solution of the problem is the maximum value returned by any of
these subproblems, i.e., max 1 i 6 nopt(i).
The complexity isO(n^2 ). There are 6ndifferent subproblems, and each sub-
problem requires us to search throughO(6n1) boxes to find ones that have
a base large enough to stack the current box on top.

3. You have an amount of moneyM and you are in a candy store. There aren kinds of candies and for each candy you know how much pleasure you get by eating it, which is a number between 1 and 100, as well as the price of each candy. Your task is to chose which candies you are going to buy to maximise the total pleasure you will get by gobbling them all. Solution: This is a knapsack problem with duplicated values. The pleasure score is the value of the item, the cost of a particular type of candy is its weight, and the moneyM is the capacity of the knapsack. The complexity isO(M n).
4. Consider a 2-D map with a horizontal river passing through its centre. There arencities on the southern bank withx-coordinatesa 1… anandncities on the northern bank withx-coordinatesb 1… bn. You want to connect as many north-south pairs of cities as possible, with bridges such that no two bridges cross. When connecting cities, you are only allowed to connect the theithcity on the northern bank to theithcity on the southern bank. Solution:

Sort the cities on the south bank according to theirxcoordinates and then
re-enumerate them so that they appear as{ 1 , 2 , 3 ,.. .}, and then apply the
same permutation to the cities on the north bank. Now the problem reduces
to finding a maximal increasing sequence of indices of cities on the north bank.

5. You are given a boolean expression consisting of a string of the symbolstrueand falseand with exactly one operationand, or, xorbetween any two consecutive truth values. Count the number of ways to place brackets in the expression such that it will evaluate to true. For example, there is only 1 way to place parentheses in the expressiontrue andfalsexortrue such that it evaluates to true. Solution: Let there bensymbols, andn1 operations between them. We solve the following two subproblems: How many ways are there to place brack- ets to make the expression starting from at thelthsymbol and ending atrth symbol evaluate to true (T), and many ways are there to place brackets to make the expression starting from at thelthsymbol and ending atrthsymbol evaluate to false (F)? For example in trueandfalsexortrue, T(1,2) would be the number of ways of making trueandfalse evaluate to true with correct bracketing (in this case, T(1,2) = 0). The base case is that T(i, i) is 1 if symboliistrue, and 0 if symboliisfalse. The reverse applies to F(i, i). Otherwise, for each subproblem, we split the expression around an operator m so that everything to the left of the operator is in its own bracket, and everything to the right of the operator is in its own b racket to form two smaller expressions. For example, splitting the sample expression around xor would give (trueandfalse) xor (true). We then evaluate the subproblems on each of the two sides, and combine the results together depending on the type of operator we are splitting by, and whether we want the result to evaluate to true or false. We solve both subproblems in parallel:

T(l, r) =

r^1

m=l

TSplit(l, m, r)

F(l, r) =

r^1

m=l

FSplit(l, m, r)

TSplit(l, m, r) =

T(l, m)T(m+ 1, r)
if operatormis and,
T(l, m)F(m+ 1, r) + T(l, m)T(m+ 1, r) + F(l, m)T(m+ 1, r)
if operatormis or,
T(l, m)F(m+ 1, r) + F(l, m)T(m+ 1, r)
if operatormis xor.

FSplit(l, m, r) =

T(l, m)F(m+ 1, r) + F(l, m)F(m+ 1, r) + F(l, m)T(m+ 1, r)
if operatormis and,
F(l, m)F(m+ 1, r)
if operatormis or,
T(l, m)T(m+ 1, r) + F(l, m)F(m+ 1, r)
if operatormis xor.
Note that the equations inside the TSplit and FSplit functions are chosen to
correspond with the truth tables of the corresponding operator.
The complexity isO(n^3 ). There areO(n^2 ) different ranges thatlandrcould
cover, and each needs the evaluations of TSplit or FSplit at up ton1 different
splitting points.

6. A company is organising a party for its employees. The organisers of the party want it to be a fun party, and so have assigned a fun rating to every employee. The employees are organised into a strict hierarchy, i.e., a tree rooted at the president. There is one restriction, though, on the guest list to the party: an employee and their immediate supervisor (parent in the tree) cannot both attend the party (because that would be no fun at all). Give an Algorithm that makes a guest list for the party that maximises the sum of the fun ratings of the guests. Solution: Let us denote byT(i) the subtree of the treeT of all employees which is rooted at an employeei. For each such subtree we will compute two quantities, I(i) andE(i). I(i) is the maximal sum of fun factors fun(i) of employees selected from subtreeT(i) which satisfies the constraint and which must include the rooti. E(i) is the maximal sum of fun factors of employees selected from the subtreeT(i) but which does NOT includei. These two quan- tities are easily computed by recursion on subtrees, starting from the leaves.

For every employeeiwhose (immediate) subordinates arej 1 ,... , jmwe have

I(i) = fun(i) +

1 km

E(jk)

E(i) =

1 km

max(E(jk), I(jk))

Notice that in the definition ofE(i) we have the option to either include the
children ofior exclude them, whatever produces larger value ofE(i). The final
answer is max(I(n), E(n)) wherenis the root of the corporate treeT. Clearly
such algorithm runs in time linear in the number of all employees.

7. You haven 1 items of sizes 1 andn 2 items of sizes 2. You would like to pack all of these items into bins, each of capacity C, using as few bins as possible. Solution: We will solve subproblemsP(i, j) of packingimany items of size s 1 andjmany items of sizes 2 for all 1i n 1 and all 1j n 2. Let C/s 1 =K. The recursion step is essentially an exhaustive search: opt(i, j) = 1 + min 0 kK

opt(ik, jb(Ck s 1 )/s 2 c)

Thus, we try all options of placing between 0 andK many items of sizes 1
into one single box and then fill the box to capacity with items of sizes 2 , and
optimally packing the remaining items. The algorithm runs in timeO(K n 1 n 2 ).

8. You are givennactivities and for each activityiyou are given its starting time si, its finishing timefi and the profitpiwhich you get if you schedule this activity. Only one activity can take place at any time. Your task is to design an algorithm which produces a subsetS of thosenactivities so that no two activities inSoverlap and such that the sum of profits of all activities inSis maximised. Solution: Sort all activities by finishing timefi. We solve the following sub- problems for alli: What is the maximum profit opt(i) we can make if we are to choose between activitiesa 1 , a 2 ,… , AI and such that activityiis the last activity we do? Recursion is simple:

opt(i) = max{opt(j) :fj< si}+pi
prev(i) = arg max{opt(j) : fj< si}

Finally, the solution to the original problem is profit of max 1 inopt(i) and
the sequence of jobs can be obtained starting withm= arg max 1 inopt(i)
and then backtracking viam,prev(m),prev(prev(m)),.. ..

9. Your shipping company has just receivedNindividual shipping requests (jobs). For each requesti, you know it will requiretitrucks to complete, paying youdi dollars. You haveT trucks in total. Devise an algorithm to select jobs which will bring you the largest possible amount of money. Solution: This is just the standard knapsack problem withtibeing the size of theithitem,diits value and withT as the capacity of the knapsack. Since each transportation job can be executed only once, it is a knapsack problem with no duplicated items allowed. The complexity isO(N T).
10. Again your shipping company has just receivedNindividual shipping requests (jobs). This time, for each request i, you know it will requireeiemployees andtitrucks to complete, paying youdidollars. You haveEemployees and T trucks in total. Devise an efficient algorithm to select jobs which will bring you the largest possible amount of money. Solution: This is a slight modification of the knapsack problem with two constraints on the total size of all jobs; think of a knapsack which can hold items of total weight not exceedingE units of weight and total volume not exceedingT units of volume, with itemihaving a weight ofeiinteger units of weight andti integer units of volume. For each triplet(e, t, i) such that eE, tT, iNwe solve the following subproblem: choose a sub-collection of items 1… ithat fits in a knapsack of capacityeunits of weight andtunits of volume, which is of largest possible value, putting such a value in a 3D table of sizeETN whereN is the number of items (in this case jobs). These values are obtained using the following recursion: opt(i, e, t) = max{opt(i 1 , e, t), opt(i 1 , eei, tti) +di}.

The complexity isO(N ET)

11. Because of the recent droughts,nproposals have been made to dam the Murray Darling river. Theithproposal asks to place a damximeters from the head of the river (i.e., from the source of the river) and requires that there is not another dam withinrimetres (upstream or downstream). What is the largest number of dams that can be built? You may assume thatxi< xi+1. Solution: We solve this by finding the maximum value among the following subproblems for everyin: Find the largest possible number of dams that can be built among proposals 1… i, such that theithdam is built. The base case is opt(1) = 1. The recursion is: opt(i) = 1 + max{opt(j) : xixj>max(ri, rj), j < i}

We do anO(n) search at every dam proposali. Thus, the total complexity is
O(n^2 ).

12. You are given annnchessboard with an integer in each of itsn^2 squares. You start from the top left corner of the board; at each move you can go either to the square immediately below or to the square immediately to the right of the square you are at the moment; you can never move diagonally. The goal is to reach the right bottom corner so that the sum of integers at all squares visited is minimal.

a) Describe a greedy algorithm which attempts to find such a minimal sum
path and show by an example that such a greedy algorithm might fail to
find such a minimal sum path.
b) Describe an algorithm which always correctly finds a minimal sum path and
runs in timen^2.
c) Describe an algorithm which computes the number of such minimal paths.
d) (Very Tricky!) Assume now that such a chessboard is stored in a read only
memory. Describe an algorithm which always correctly finds a minimal sum
path and runs in linear space (i.e., amount of read/write memory used is
O(n)) and in timeO(n^2 ).

m

n

Solution: a)Start at the top left square, and always go to the immediate square below or to the right that has the smallest integer. This algorithm fails with the following example:

0 1 1

5 1000 1000

5 5 0

The algorithm will get a score of 1002, instead of the correct answer of 15.

b)We solve all subproblems of the form What is the best score we can get arriving at the cell at rowiand columnj? The base case is that opt(1,1) = board(1,1), and opt(i, j) = for alliandj that are off the board. The recursion is:

opt(i, j) = board(i, j) + min{opt(i 1 , j),opt(i, j1)}.

The complexity isO(n^2 ).

c)Solve the following subproblem: What is the minimum number of ways to reach rowiand columnjwith the score opt(i, j)? The base case is ways(1,1) = 1 and ways(i, j) = 0 for alliandjthat are off the board. The recursion is:

ways(i, j) =

ways(i 1 , j) if opt(i 1 , j)<opt(i, j1)
ways(i, j1) if opt(i 1 , j)>opt(i, j1)
ways(i 1 , j) + ways(i, j1) if opt(i 1 , j) = opt(i, j1)

The complexity is once againO(n^2 )

d) This is a very tricky one. The idea is to combine divide and conquer with dynamic programming. Note that to generate optimal scores at a rowi you only need the optimal scores of the previous row. You start running the previous algorithm from the top left cell to the middle rowbn/ 2 c, keeping in memory only the previous row. You now run the algorithm from the bottom right corner until you reach the middle row, always going either up one cell or to the left one cell. Once you reach the middle row you sum up the scores obtained by moving down and to the right from the top left cell and the scores obtained by moving up and to the left from the bottom right cell and you

pick the cellC(n/ 2 , m) in that row with the minimal sum. This clearly is
the cell on the optimal trajectory. You now store the coordinates of that
cell and proceed with the same strategy applied to the top left region for
whichC(n/ 2 , m) is bottom right cell, and also applied to the bottom right
region of the board for whichC(n/ 2 , m) is the top left cell. The run time is
O(nn+nn/2 +nn/4 +.. .) =O(n 2 n) =O(n^2 )

13. A palindrome is a sequence of letters which reads equally from left to right and from right to left. Given a sequence of letters, find efficiently its longest subsequence (not necessarily contiguous) which is a palindrome. Thus, we are looking for a longest palindrome which can be obtained by crossing out some of the letters of the initial sequence without permuting the remaining letters. Solution: LetSidenote theith letter of the string. Solve the subproblem: What is the longest palindrome within the substring starting at letteriand ending atj. The base case is that opt(i, i) = 1, as a single letter is a palindrome by itself. We solve this using the recursion:

opt(i, j) =

1 ifi=j,
2 ifi+ 1 =jandSi=Sj,
opt(i+ 1, j1) + 2 ifSi=Sjandi < j 2 ,
max{opt(i, j1),opt(i+ 1, j)} else

and a function from pairs of natural numbers into pairs of natural numbers

pred[(i, j)] =

(i, i) ifi=j,
(i, j) ifi+ 1 =jandSi=Sj,
(i+ 1, j1) ifSi=Sj andi < j 2 ,
(i, j1) ifSi 6 =Sj and opt(i, j1)opt(i+ 1, j)
(i+ 1, j) else

To reconstruct the palindrome, backtrack iterating function pred[(i, j)] starting
with (1, n) and recoding values ofiandjwhenSi=Sj. The complexity of
this algorithm isO(n^2 ), wherenis the length of the string.

14. A partition of a numbernis a sequencep 1 , p 2 ,… , pt(we call thepk parts) such that 1p 1 p 2 .. .ptnand such thatp 1 +.. .+pt=n.

(a) Find the number of partitions ofnin which every part is smaller or equal
thank, wheren, kare two given numbers such that 1kn.

(b) Find the total number of partitions ofn.

Solution: (a) Let numpart(k, m) denote the number of partitions of min
which every part is at mostk. Then for allmnumpart(1, m) = 1 because the
only way to representmwithk= 1 would be as a sum ofmones; fork 2
the value of numpart(k, m) satisfies the recursion

numpart(k, m) = numpart(k 1 , m) + numpart(k, mk)

The first term on the right counts number of partitions ofmwhen no part is
equalkand the second term counts the number of partitions when there exists
at least one part equal tok, which we subtract frommand look at the number
of partitions of the remaindermkin which all the parts are also at mostk.
Note that numpart(k, m) are computed in order of the value of the summ+k.
(b)We run the previous algorithm; the solution is numpart(n, n).

15. We say that a sequence of Roman letters A occurs as a subsequence of a sequence of Roman lettersBif we can obtain A by deleting some of the symbols ofB. Design an algorithm which for every two sequences A and B gives the number of different occurrences ofAinB, i.e., the number of ways one can delete some of the symbols ofBto getA. For example, the sequence ba has three occurrences in the sequence baba: baba, baba, baba. Solution: LetAibe theithletter ofA, andBj be thejthletter of B. Solve the subproblems: How many times do the firsti letters of A appear as a subsequence of the firstj letters of B. The base case is ways(1,1) = 1 if A 1 =B 1 and 0 otherwise; also, clearly, ways(i, j) = 0 ifi > j. The recursion is, for alli < j

opt(i, j) =

0 , ifi > j
opt(i, j1), ifAi 6 =Bj
opt(i 1 , j1) + opt(i, j1) ifAi=Bj

Note that in the second case whenAi=Bjwe have two options: we can map
AiintoBjbecause they match, but we can also map the firstimany letters of
Aintoj1 many letters ofB, so we have the sum of these two options. The
complexity isO(nm) wherenis the length ofAandmis the length ofB.

16. We are given a checkerboard which has 4 rows and n columns, and has an integer written in each square. We are also given a set of 2npebbles, and we

want to place some or all of these on the checkerboard (each pebble can be placed on exactly one square) so as to maximise the sum of the integers in the squares that are covered by pebbles. There is one constraint: for a placement of pebbles to be legal, no two of them can be on horizontally or vertically adjacent squares (diagonal adjacency is fine).

(a) Determine the number of legalpatternsthat can occur in any column (in
isolation, ignoring the pebbles in adjacent columns) and describe these
patterns.

Call two patternscompatibleif they can be placed on adjacent columns
to form a legal placement. Let us consider sub-problems consisting of the
firstkcolumns 1 k n. Each sub-problem can be assigned a type,
which is the pattern occurring in the last column.
(b) Using the notions of compatibility and type, give an O(n)-time algorithm
for computing an optimal placement.

Solution: (a)There are 8 patterns, listed below.

1 2

O

3

O

4

O

5

O

6

O

O

7

O

O

8

O

O

(b)Lettdenote the type of pattern, so thattranges from 1 to 8. We solve our subproblem by choosingkcolumns from our set of patterns, such that each column is compatible with the one before. The subproblem is: What is the maximum score we can get by only placing pebbles in the firstkcolumns, such thekthcolumn has patternt. The base case is that opt(0) = 0. The recursion is:

opt(k, t) = score(k, t) + max{opt(k 1 , s) :sis compatible witht}

Here, score(k, t) is the score obtained by using patternton columnk. The compatibilities are as follows:

(a) pattern 1 is compatible with all 8 patterns (including itself);

(b) pattern 2 is compatible with all patterns except 2,6 and 8
(c) pattern 3 is compatible with all patterns except 3 and 7;
(d) pattern 4 is compatible with all patterns except 4 and 6;
(e) pattern 5 is compatible with all patterns except 5,7 and 8;
(f) pattern 6 is compatible with all patterns except 2,6 and 8;
(g) pattern 7 is compatible with all patterns except 3,5,7 and 8;
(h) pattern 8 is compatible with all patterns except 2,5,6,7 and 8.

The complexity isO(n), as the number of patterns is constant.

17. Skiers go fastest with skis whose length is about their height. Your team consists ofnmembers, with heightsh 1 , h 2 ,… , hn. Your team gets a delivery ofm npairs of skis, with lengthsl 1 , l 2 ,… , lm. Your goal is to design an algorithm to assign to each skier one pair of skis to minimise the sum of the absolute differences between the heighthiof the skier and the length of the corresponding ski he got, i.e., to minimise

1 in

|hils(i)|

wheres(i) is the index of the skies assigned to the skier of heighthi.
Solution: First observe that if we have two skiersiandjsuch thathi< hj,
thens(i)< s(j). If this were not the case, we could swap the skis assigned to
iandj, which would lower the sum of differences. This implies that we may
initially sort the skiers by height, and sort the skis by length, and find some
sort of pairing such that there are no crossovers (similar to question 4). Also,
if you have equal number of skiers and skis, you would giveithskierithpair of
skis.
We now solve the following subproblem: What is the minimum cost of matching
the firstiskiers with the firstj > iskis such that each of the firstiskiers gets
a ski? The base case is opt(i, i) =

i
k=1|hklk|. The recursion forj > iis:

opt(i, j) = min{opt(i, j1),opt(i 1 , j1) +|hilj|}.

To retrieve the assignment, we start at (i, j) wherei = nandj =m. If
opt(i 1 , j1) +|hilj|<opt(i, j1) thens(i) =jand we try again at

(i 1 , j1). Otherwise, we try again at (i,j1). If at any point we reach
i=j(our base case), we simply assigns(k) =kfor all 1ki.
The complexity of the initial recursionO(nm). The complexity of retrieving
the  assignment isO(m), as each time we run the algorithm,j decreases by
exactly 1.

18. You have to cut a wood stick into several pieces. The most affordable company, Analog Cutting Machinery (ACM), charges money according to the length of the stick being cut. Their cutting saw allows them to make only one cut at a time. It is easy to see that different cutting orders can lead to different prices. For example, consider a stick of length 10 m that has to be cut at 2, 4, and 7 m from one end. There are several choices. One can cut first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 m, the resulting stick of 8 m, and the last one of 6 m. Another choice could cut at 4, then at 2, then at 7. This would lead to a price of 10 + 4 + 6 = 20, which is better for us. Your boss demands that you design an algorithm to find the minimum possible cutting cost for any given stick. Solution: Let x(i) be the distance along the stick the ith cutting point is at. Solve the following subproblem: What is the minimum cost of cutting up he stick completely from cutting pointito cutting pointj. The base case is opt(i, i+ 1) = 0. The recursion is:

opt(i, j) =x(j)x(i) + min{opt(i, k) + opt(k, j) :i < k < j}.

The complexity isO(n^2 ), wherenis the number of cutting points on the stick.
Note: always cutting the stick as close to its middle as possible does not always
produce an optimal solution; try making a counter example.

19. For bit stringsX=x 1… xm,Y =y 1… ynandZ=z 1… zm+nwe say that Z is an interleaving of X and Y if it can be obtained by interleaving the bits in X and Y in a way that maintains the left-to-right order of the bits in X and Y. For example if X = 101 and Y = 01 thenx 1 x 2 y 1 x 3 y 2 = 10011 is an interleaving of X and Y, whereas 11010 is not. Give an efficient algorithm to determine if Z is an interleaving of X and Y. Solution: Solve the following subproblem: Do the firstibits of X and the firstjbits of Y form an interleaving in the firsti+jbits of Z? The base case is opt(0,0) = true, and opt(i, j) = false ifi <0 orj <0. The recursion is:

opt(i, j) = (opt(i 1 , j) ANDzi+j=xi) OR (opt(i, j1) ANDzi+j=yj).

The complexity isO(nm).

20. Some people think that the bigger an elephant is, the smarter it is. To disprove this you want to analyse a collection of elephants and place as large a subset of elephants as possible into a sequence whose weights are increasing but their IQs are decreasing. Design an algorithm which given the weights and IQs of n elephants, will find a longest sequence of elephants such that their weights are increasing but IQs are decreasing. Solution: Sort the elephants in order of decreasing IQs. The problem now becomes finding the longest increasing subsequence of elephant weights.
21. You have been handed responsibility for a business in Texas for the next N days. Initially, you have K illegal workers. At the beginning of each day, you may hire an illegal worker, keep the number of illegal workers the same or fire an illegal worker. At the end of each day, there will be an inspection. The inspector on theithday will check that you have betweenliandriillegal workers (inclusive). If you do not, you will fail the inspection. Design an algorithm that determines the fewest number of inspections you will fail if you hire and fire illegal employees optimally. Solution: Observe that the minimum and the maximum number of illegal workers you could possible have on the evening of dayiare max(Ki,0) and K+i. We solve the following subproblem: What is the minimum number of inspections I have failed on dayiassuming that on that day I have jmany illegal workers? The base case is opt(0, K) = 0, since we start with 0 failed inspections before the first day begins. Let failed(i, j) return 1 if thejfalls out of the range of [li, ri], and return 0 otherwise. The recursion is: for allisuch that 1iN and alljsuch that max(0, Ki)jK+i,

opt(i, j) = failed(i, j)+min

{

opt(i 1 , j1) ifj 1 max(0, K(i1)),
 ifj 1 <max(0, K(i1))
opt({ i 1 , j),
opt(i 1 , j+ 1) ifj+ 1K+i 1
 ifj+ 1> K+i 1

Note that the first option in the cases corresponds to hiring an illegal worker
on the morning of dayi, providing that the number of workers on the previous
day was achievable over the period ofi1 days (you start withKworkers, so

afteri1 days you must have at leastK(i1) workers which happens if
you kept firing one worker every day); the second corresponds to keeping the
same number of illegal workers as on the previous day and the third option
corresponds to firing a worker from the previous day. The final answer is equal
to min
max(KN,0)jK+N

opt(N, j).

The complexity isO(N^2 ), as there areN days, and at most 2N+ 1 possible
values of illegal worker each day.

22. Given an array of N positive integers, find the number of ways of splitting the array up into contiguous blocks of sum at most K. Solution: Solve the subproblem: What is the number of ways I can split the firstielements into contiguous blocks of sum at mostK. The base case is opt(0) = 1. For 1j < ilet sum(j, i) is the sum of all numbers fromA[j] to A[i] inclusive. The recursion is:

opt(i) =

{opt(j1) : 1ji,sum(j, i)K},

The complexity isO(n^2 ), as each subproblem requires aO(n) search.

23. There are N levels to complete in a video game. Completing a level takes you to the next level, however each level has a secret exit that lets you skip to another level later in the game. Determine if there is a path through the game that plays exactly K levels. Solution:The subproblems are: Can I reach theithlevel after playing exactly klevels? The base case is opt(0,0) = true. The recursion is:

opt(i, k) = opt(i 1 , k1) OR (j < i1)(opt(j, k1) AND link(j, i))

Here link(j, i) is true if and only if leveljhas a secret exit to leveli. The final
answer is opt(K, N). The time complexity isO(N^2 ).

24. Given a sequence ofnpositive or negative integersA 1 , A 2 , …An, determine a contiguous subsequenceAitoAj for which the sum of elements in the subse- quence is maximised. Solution:We solve the subproblem: What is the maximum sum of elements ending with integeri? The base case is opt(0) = 0. The recursion is:

opt(i) =Ai+ max(0,opt(i1).

Here, we take the maximum of 0 and opt(i1) because we may either choose
to addAito the previous block, or start a completely new block. To determine
the actual block, we may also solve the following recursive function for alli:

start(i) =

{

start(i1) if opt(i1)> 0 ,
i if opt(i1) 0

To get the block, we simply find the elementisuch thatopt(i) is maximised.
The block with maximum sum is [start(i), i]. The complexity isO(n).

25. Consider a row of ncoins of valuesv 1 , v 2 , …vn, where nis even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first. Solution: DP has a very important role in the field of game theory. Let opt(i, j) fori, jtwo integers such thatji+1 an even number and 1i < jn denote the maximal amount of money we can definitely win if we play on the subsequence between coins at the positioni and positionj. Then opt(i, j) satisfies the following recursion

opt(i, j) = max{vi+min{opt(i+2, j),opt(i+1, j1)}, vj+min{opt(i+1, j1),opt(i, j2)}}

The options inside the min functions represent the choice your opponent takes,
either to continue taking from the same end as you took or from the oposite
end of the sequence. The problems to find opt(i, j) are solved in order of the
size ofji. The complexity isO(n^2 ), because this is how many pairs ofi, j
we have and each stage of the recursion has only constant number of steps (
table lookups and 2 additions plus two min and one max operations.