Problem 7-1 (Texting—A Long Time Ago)                   21+6 points

You may or may not be old enough to remember how people used to write text messages a while back: on a standard issue phone, the N = 26 letters would be assigned in groups of three or four to the K = 8 keys ❖2 to ❖9 on the dial pad, and in order to type the l th  letter on a particular key, one would tap that key l times in rapid succession.

Consider a text for which the frequency fi  ∈ N of each letter i = 1,...,N is known.1   Typing this text on a phone would require T = ： · fi  taps, where pi  is the position of letter i on its key. Clearly, if one wishes to minimize T, the optimal assignment of letters to keys—in alphabetical order—depends on the text in question; more precisely, on the frequencies fi.  In particular, having groups of just three or four letters may be suboptimal.

In this task you will develop an algorithm that given (general) K , N, and frequencies f1 ,..., fN finds an assignment of the letters 1,...,N in alphabetical order to the keys 1,...,K such that T is minimized.

(a)  (4  points)   First,  let  us  consider  the  problem  of a single key.   For  1  ≤  i  ≤  j  ≤  N,  let

C[i,j] :=：k(j) =i (k − i + 1) · fk, which is the number of taps required to type only the letters

i,...,j in the text if they are all assigned to a single key (in alphabetical order).

A naive solution to fill the C[ · , ·] would take O(N3) time.  Instead, provide pseudocode of an O(N2) algorithm Phone-C(N, F) that fills the array C[ · , ·] for all places where i ≤ j.

Assume that F = (f1 ,..., fN ) is an array storing the frequencies.

(Hint: Rephrase C[i,j] in terms of a recurrence equation.)

In the following you may assume that you have direct access to the filled array C[ · , ·].  For 1 ≤ n ≤ N and 1 ≤ k ≤ K, define T[n,k] to be the smallest possible number of taps required to type only the letters 1,...,n in the text if they are assigned to keys 1,...,k.

(b)  (2 points)  For n = 1,...,N, what is T[n,1] (in terms of C)?

(c)  (5 points)  Derive a recurrence relation for T[n,k] and justify it.  Note that in part  (b) you already considered the base case of this recurrence.

(Hint: Your recurrence equation may use both T and C.)

(d)  (5 points)   Devise a polynomial-time (in N and K) algorithm Phone-TD(N,K, C) (write pseudocode) that fills table T[ · , ·] in a top-down, recursive fashion with memoization.

(e)  (5 points)   Provide pseudocode for an algorithm Phone-BU(N,K, C) that fills T[ · , ·] in a bottom-up manner. Analyze the running time of your algorithm.

(Hint: Fill the table in column-major order, i.e., fill the first column, then the second, etc.)

(f)  (Extra Credit)(6 points)  Finally, develop a procedure Phone-Find(N,K, T) (write pseu- docode) that uses the filled T[ · , ·] to output an assignment of the letters to the keys such that the text can be typed with T[N, K] taps.  Write pseudocode and analyze the running time of your algorithm. If it leads to a faster Phone-Find, you may modify your algorithm Phone-BU to make it store auxiliary values (accessible to Phone-Find).

Problem 7-2 (Longest Increasing Subsequence)                  10 points

Given an array of distinct numbers A = (a1 ,..., an), your goal is to find the length of the longest increasing subsequence contained inside A. For example, if A = (10, 11, 12, 1, 8, 2, 7, 3, 4), then the answer is 4, achieved by subsequence (1, 2, 3, 4).

(a)  (4 points)  Without designing any new dynamic programming algorithms, show how to solve the problem in time O(nlog n) plus the time to solve the longest common subsequence problem studied in class.

(b)  (4 points)  While part (a) already gives us O(n2 ) solution, here we will design a more direct O(n2 ) dynamic programming algorithm for a related problem.  Let p[i] denote the length of the largest increasing subsequence among a1 ...ai  which  contains ai  as its last element.  Write a recursive formula for the p[i] using p[j] for j < i, and show how to compute all p[i]’s by dynamic programming in time O(n2 ).

(c)  (2 points)   Assuming you solved part (b), use the values p[1],..., p[n] to design an explicit O(n2 ) algorithm for the original problem (i.e., longest increasing subsequence without any restrictions on the last element).

Problem 7-3 (Checking Change)                                      11+4 points

You are working for company producing vending machines and you are investigating some problem reports from your customers.  In certain countries the machines seem to give change using too many coins instead of the minimum possible number.  This seems strange to you, so you try to find out for any given set of coins that your machine accepts and some common return values what the optimal number of coins should be.

Let C = (C[1],..., C[n]) denote the n coin denominations of a given currency, in increasing order.  Assume that C[i] > 0 and that C[i] is an integer value, for all 1 ≤ i ≤ n.  For example, in the US, we would have C = (1, 5, 10, 25) (when considering only the common coins).  We now want to write an algorithm CheckingChange(n,C, v) that for a given value v computes the minimal number of coins that sum up to exactly v.  If a certain value is impossible, the algorithm should return ∞. For example, if C = (1, 2, 5) and v = 17, the output should be 4, as 5 + 5 + 5 + 2 = 17. On the other hand, if C = (5, 10, 25), then the output for 15 should be 2 while the output for 13 should be ∞ .