Reference no: EM132958989

Question 1: Recall the FOLDS AND CUTS problem from Assignment 2, where you are given a rectangular strip of paper P of length t with n ≥ 0 vertical folds, located at distances f1, f2 ... fn, A from the left end of P. Let fn+1 = 1. In the "dual" version of the problem, you are also given a nonnegative integer k. You want to cut P along exactly k < n folds, such that the maximum length of the k + 1 resulting strips is as short as possible. We'll denote this length by L(n, k).

More generally, for any i in the range [01..n], let Pi denote the strip of paper of length fi+i that has folds at distances f1, f2,f3 , fi. If we cut Pi, along exactly j folds, where 0 ≤ j ≤ i, such that the maximum length of the j + 1 resulting strips is as short as possible, we denote the resulting maximum length by L(i, j).

For example, if f1, f2, ....fi are 1,3,7, respectively, f4 = t = 10, and k = 2 then cutting at 3 and 7 is optimal, resulting in a max length L(3, 2) = 4. Also for this example, L(2, 1) = L(2, 2) = 4, while L(2,0) = 7.
1. When k < n, explain why L(n, k) ≤ l.
2. When k < n, explain why L(n, k) ≥ l/ l/k+1 .
3. Write a recursive definition of L(i, j) when 0 ≤ j ≤ i. You do not need to provide a justification for your recurrence.
4. Using your recurrence, give a memoized algorithm for computing L(n, k) .
5. Explain the runtime of your algorithm.

A rectangular strip of paper P of length £ has n vertical folds, located at distances f1, f2, .....fn , fn from the left end of P. We'll let 10 = 0 and fn+i = 1, and assume that all of the fi are distinct. See Figure ??.

For a given positive M, you want to cut P along a minimum number of folds so that the resulting strips {Si, ... , sk} each have length at most M. You can assume that M > fil4 - fi, for any i, 0 ≤ i ≤ n.

Question 2: Olaf has a collection of m types of ornaments, each with a unique colour (labelled from 1 to m), and a tree T with n vertices. He is very peculiar about decorating the tree. Each vertex v can be assigned an ornament of colour cv between integers 4 and I.,. In addition, to maximize the contrast between two ornaments along a single edge, he would like the sum of icu - c„) across all edges uv in T, or the beauty of T, to be as large as possible. The beauty of a tree with just one node is 0.

1. Show that an optimal assignment of ornaments exist such that either cv = 4 or ri, for every v.

2. Let BEAuTY(vre) denote the maximum beauty of v's subtree if ce, = 4 and let BEAUTY(V, r) denote the maximum beauty of v's subtree if cv = rv. Provide recurrences for BEAUTY(V, .e) and BEAUTY(V, r) (these recurrences can depend on each other), and give the expression for the maximal beauty of T.

3. Explain the runtime of the dynamic programming algorithm based on your recur¬rence. (You don't need to write the dynamic programming algorithm.)

Question 3: You are the manager of the Abbotsford branch of a large multinational company, and your company just bought out a small business based in Brampton, Ontario. However, your company has not found a manager for the Brampton branch yet, so they have asked you to oversee both branches until the end of the year. There are n days remaining in the year.

Because you will be spending a fair amount of time in Brampton, you have determined that it will be more convenient to stay in hotels in both cities, rather than continuing to rent your apartment in Abbotsford. You cannot stay in either location for more than 7 days because you do not want to be away from either branch for too long. You must determine how to split your time between Abbotsford and Brampton in a way that minimizes the total cost of your hotels and flights.

The cost of your flight/hotel depends on the day (weekends/holidays might be more expensive, or there might be promotions on certain days) and the city. You are given four arrays that provide the cost of the hotels and flights for each day.

The arrays fA, hi., hA, and hB, each of length n, are defined as follows:

fA[i] is the cost of flying to Abbotsford on day i
fs[i] is the cost of flying to Brampton on day i
hA [i] is the cost of staying in a hotel in Abbotsford on day i

hB [i] is the cost of staying in a hotel in Brampton on day i

Question 4: You are looking to minimize the cost of accommodations plus flights, subject to the constraint that you cannot spend more than 7 days in one location. You can assume that your flights are always in the morning (so if you are flying between cities on day i, you only have to pay for a hotel in your destination city that day).

Let CA [i] be the lowest possible value of the objective function for days 1 to i, assuming you are staying in Abbotsford on day i. Similarly, let CB[i] be the lowest possible value of the objective function for days 1 to i, assuming you are staying in Brampton on day i. In either case, assume that you are staying in Abbotsford on day 0. The solutions to Tutorial 7 provide recurrences for these values.

1. Using the recurrences from Tutorial 7, write pseudo-code for an iterative dynamic programming algorithm that takes fA, fB, hA and hB as input and populates the arrays CA and CB for every value 1 < i < n. Note: it is acceptable to leave min() operations in your pseudo-code instead of writing out an inner loop.

2. State the running time of your algorithm from part 1 as a function of n. No justification needed.