Tutorial 4 – Solutions
COMP3121/9101
1. You are traveling by a canoe down a river and there are n trading posts along the way. Before starting your journey, you are given for each 1 ≤ i < j ≤ n the fee F(i,j) for renting a canoe from post i to post j. These fees are arbitrary. For example it is possible that F(1,3) = 10 and F(1,4) = 5. You begin at trading post 1 and must end at trading post n (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 post i. The base case is opt(1) = 0. The recursion is:
Copyright By PowCoder代写 加微信 powcoder
opt(i) = min{opt(j) + F (j, i) : 1 ≤ j < 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{opt(j) + F (j, i)}, i > 1.
(Note: argmin 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 post n giving the sequence {n, from(n), from(from(n)), . . . , 1}. Reverse this to get the boat’s journey.
The complexity is O(n2) because there are n subproblems, and each subproblem takes O(n) to find the best previous trading post.
2. You are given a set of n types of rectangular boxes, where the ith box has height hi, width wi and depth di. 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 6n boxes 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 box B1 can go on top of a box B0 then B0 precedes box B1 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 number i? The recursion is
opt(i) = max{opt(j) + hi : over all j such that wj > wi and dj > di}. The final solution of the problem is the maximum value returned by any of
these subproblems, i.e., max1≤i≤6n opt(i).
The complexity is O(n2). There are 6n different subproblems, and each sub- problem requires us to search through O(6n − 1) boxes to find ones that have a base large enough to stack the current box on top.
3. You have an amount of money M and you are in a candy store. There are n 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 money M is the capacity of the knapsack. The complexity is O(Mn).
4. Consider a 2-D map with a horizontal river passing through its centre. There are n cities on the southern bank with x-coordinates a1 . . . an and n cities on the northern bank with x-coordinates b1 . . . 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 the ith city on the northern bank to the ith city on the southern bank.
Solution: List out the cities on the northern side by index from left to right sorted by x-coordinate. (For example, {1, 4, 6, 8, 2, . . .} would indicate that
city 1 has lowest x-coordinate, city 4 has second lowest x-coordinate, etc.) Do the same for the southern side, to obtain another sequence. Observe that making the maximum possible bridge connections that don’t cross each other is equivalent to finding the longest common subsequence in both sequences (i.e. a maximal subsequence of cities which appear in the same order). Two cities are considered matching if you can build a bridge between them, and not matching otherwise. The complexity is O(n log n) to sort the coordinates, and O(n2) to do longest common subsequence, giving the overall complexity of O(n2).
Another way of doing it is to sort the cities on the south bank according to their x coordinates 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 symbols true and false and with exactly one operation and, or, xor between 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 are 2 ways to place parentheses in the expression true and false xor true such that it evaluates to true.
Solution: Let there be n symbols, and n − 1 operations between them. We solve the following two subproblems: How many ways are there to make the expression starting from at the lth symbol and ending at rth symbol evaluate to true (T), and how many ways to do the same but evaluate to false (F)? For example in “true and false xor true”, T(1,2) would be the number of ways of making “true and false” evaluate to true with correct bracketting (in this case, T(1, 2) = 0).
The base case is that T(i, i) is 1 if symbol i is true, and 0 if symbol i is false. 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 bracket to form two smaller expressions. For example, splitting the sample expression around “xor” would give “(true and false) 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:
TSplit(l, m, r) =
FSplit(l, m, r) =
T(l, r) = TSplit(l, m, r)
F(l, r) = FSplit(l, m, r) m=l
T(l,m)×T(m+1,r)
if operator m is ‘and’,
T(l,m)×F(m+1,r)+T(l,m)×T(m+1,r)+F(l,m)×T(m+1,r)
if operator m is ‘or’, T(l,m)×F(m+1,r)+F(l,m)×T(m+1,r)
if operator m is ‘xor’.
T(l,m)×F(m+1,r)+F(l,m)×F(m+1,r)+F(l,m)×T(m+1,r)
if operator m is ‘and’,
F(l,m)×F(m+1,r)
if operator m is ‘or’, T(l,m)×T(m+1,r)+F(l,m)×F(m+1,r)
if operator m is ‘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 is O(n3). There are n2 different ranges that l and r could cover, and each needs the evaluations of TSplit or FSplit at up to n 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 by T(i) the subtree of the tree T of all employees which is rooted at an employee i. For each such subtree we will compute two
quantities, I (i) and E (i). I (i) is the maximal sum of fun factors fun(i) of employees selected from subtree T(i) which satisfies the constraint and which must include the root i. E(i) is the maximal sum of fun factors of employees selected from the subtree T (i) but which does NOT include i. These two quan- tities are easily computed by recursion on subtrees, starting from the leaves. For every employee i whose subordinates are j1, . . . , jm we have
I(i) = fun(i) + E(jm) 1≤k≤m
E(i) = max(E(jm), I(jm)) 1≤k≤m
Notice that in the definition of E(i) we have the option to either include the children of i or exclude them, whatever produces larger value of E(i). The final answer is max(I(n),E(n)) where n is the root of the corporate tree T. Clearly this algorithm runs in time linear in the number of all employees.
7. You have n1 items of size s1 and n2 items of size s2. 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 subproblems P(i,j) of packing i many items of size s1 andjmanyitemsofsizes2 forall1≤i≤n1 andall1≤j≤n2. Let C/s1 = K.
The recursion step is essentially an exhaustive search:
opt(i,j)=1+ min opt i−k,j− 0≤k≤K
C − k s1 s2
Thus, we try all options of placing between 0 and K many items of size s1 into one single box and then fill the box to capacity with items of size s2, and opti- mally packing the remaining items. The algorithm runs in time O(K n1 n2) = O(C n1 n2). Thus, such an algorithm runs in exponential time in the size of the input, because input takes only O(log2 C + log2 n1 + log2 n2 + log2 s1 + log2 s2) many bits to represent.
8. You are given n activities and for each activity i you are given its starting time si, its finishing time fi and the profit pi which 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 subset S of those n activities so that no two activities in S overlap and such that the sum of profits of all activities in S is maximised.
Solution: Sort all activities by finishing time fi. We solve the following sub- problems for all i: What is the maximum profit opt(i) we can make if activity i is 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 maxi≤i≤n opt(i) and the sequence of jobs can be obtained starting with m = arg maxi≤i≤n opt(i) and then backtracking via m, prev(m), prev(prev(m)), . . ..
9. Your shipping company has just received N shipping requests (jobs). For each request i, you know it will require ti trucks to complete, paying you di dollars. You have T trucks in total. Out of these N jobs you can take as many as you would like, as long as no more than T trucks are used in total. Devise an efficient algorithm to select jobs which will bring you the largest possible amount of money.
Solution: This is just the standard knapsack problem with ti being the size of the ith item, di its value and with T 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 is O(NT).
10. Again your shipping company has just received N shipping requests (jobs). This time, for each request i, you know it will require ei employees and ti trucks to complete, paying you di dollars. You have E employees and T trucks in total. Out of these N jobs you can take as many of them as you would like, as long as no more than E employees and T trucks are used 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 exceeding E units of weight and total volume not exceeding T units of volume, with item i having a weight of ei integer units of weight and ti integer units of volume. For each triplet e ≤ E, t ≤ T,i ≤ N we solve the following subproblem: choose a sub-collection of items 1 . . . i that fits in a knapsack of capacity e units of weight and t units of volume, which is of largest possible value, putting such a value in a 3D table of size E × T × N where N 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,e−ei,t−ti)+di}.
The complexity is O(NET).
11. Because of the recent droughts, n proposals have been made to dam the Murray river. The ith proposal asks to place a dam xi meters from the head of the river (i.e., from the source of the river) and requires that there is not another dam within ri metres (upstream or downstream). What is the largest number of dams that can be built? You may assume that xi < xi+1.
Solution: We solve this by finding the maximum value among the following subproblems for every i ≤ n: Find the largest possible number of dams that can be built among proposals 1 . . . i, such that the ith dam is built. The base case is opt(1) = 1. The recursion is
opt(i)=1+max{opt(j) : xi−xj >max(ri,rj),j
The complexity is once again O(n2)
(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 row i you only need the optimal scores of the previous row. You start running the previous algorithm from the top left cell to the middle row ⌊n/2⌋, 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 cell C(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 which C(n/2,m) is bottom right cell, and also applied to the bottom right region of the board for which C(n/2, m) is the top left cell. The run time is O(n×n+n×n/2+n×n/4+. . .) = O(n×2n) = O(n2)
13. A palindrome is a sequence of at least two 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: Let Si denote the ith letter of the string. Solve the subproblem: What is the longest palindrome within the substring starting at letter i and ending at j. The base case is that opt(i, i) = 1, as a single letter is a palindrome by itself. We solve this using the recursion:
if i + 1 = j and Si = Sj ,
opt(i,j)= opt(i+1,j−1)+2
max{opt(i, j − 1), opt(i + 1, j)} else
ifS =S andi