Homework 7 Solution

CS409 - Spring 2000

Due: Thursday, Mar 30

1. (10 pts) Do problem 3.5 on page 78 of Skiena.
   1. Goal: find the max contiguous sum in Theta(n²) time.
      This part is relatively easy. Build a table in which each row corresponds to a starting position and each column corresponds to an ending position.  Note that within a single row, the numbers represent the accumulated sum as we move through the vector of numbers.  It's easy to see that the table can be filled (from left to right) in O(n²) time. The table entry with maximum value corresponds to the desired subvector.
   2. Goal: find the max contiguous sum in Theta(n) time.
      This part is harder. Think about the sums you see, starting from the left end of the vector. As soon as that sum goes negative, you know you have a prefix that you'll never want to include in any maximal subvector. As long as the prefix is positive, it's always desirable to include it. So here's the algorithm: (1) starting from the left-hand end accumulate the sum, keeping track of the largest sum seen so far; (2) if this sum ever goes negative, we throw out this old sum and begin accumulating the sum starting from the adjacent number, again keeping track of the largest sum seen so far. This works because every prefix of the maximal subvector has to have a positive sum.

    

2. (10 pts) Do problem 3.6 on page 78 of Skiena.
   Hints: Use dynamic programming. You should assume that there is a 1 cent coin (d₁ = 1), so for any amount n there is always a way to choose coins to make that amount. Your algorithm should run in time O(nk) where n is the amount for which we are attempting to find change and k is the number of coin denominations. You may assume that the goal is simply to report the optimum number of coins rather than to produce a list of the coins used to achieve this optimum.  Explain your algorithm and analyze its running time. Your answer should be brief and it should be clearly expressed using a mix of English and pseudo-code. Answers that are unclear or excessively long will be penalized.

   The idea is to determine the minimum number of coins for an amount n by trying out each of the k different  coins as the first coin.  Once a coin is chosen, say the one with value d[i], then we recursively find the optimum number of coins for the smaller amount n-d[i].  Of course, we want to use dynamic programming, not recursion, so instead of making recursive calls we store optimal values in an array.  Here's the program:

   CoinOpt(n,d[1..n])):
    array opt[1..n];
    opt[1] = 1;        // We know that we have a one cent coin.
    for a = 2 to n do
        // Ignore any values where n-d[i] is negative.
        opt[a] = 1 + MIN(i=1..k) of opt(n-d[i]);
    return opt[n];
end.

   The running time is obviously O(nk) because there are two loops (the amount-loop and the minimization loop), one nested within the other. The outer loop has n steps and the inner one has k steps, so the total running time is O(nk).

    

3. (10 pts) Do problem 3.9 on page 79 of Skiena.

   The solution here is much like that of the coin problem. The idea is to try each of the strings as the end-part of string D.  Once a string is chosen, say one with length j, then we recursively find the optimum coding for the smaller string D[1..n-j].  Of course, we want to use dynamic programming, not recursion, so we store the optimal values in an array.  Here's the program:

   CompressionOpt(D[1..n],string[1..m,1,,k]):
   	// D is the data string; string represents the m text strings used for
   	// coding, each of length at most k.
   	array opt[1..n];	// opt[i] will hold best code-size for D[1..i]
   	for i = 1 to n do
   		Determine which strings s appear at the end of D[1..i];
   			// This takes O(mk) time.
   		opt[i] = 1 + MIN{over all such strings s) of opt(i-|s|);
   	return opt[n].

   Since the program consists of simple nested loops, it's obvious that it takes time O(nmk).

    

4. (10 pts) Do problem 3.10 on page 79 of Skiena.

   If we put all the names in a single array and use binary search then every access takes time proportional to (log 10000) or about 13.29. If we put the 4000 good customers in an array by themselves then 60% of the time our search will take time (log 4000) and 40% of the time our search will take time (log 4000 + log 6000).  The total expected time is thus: (log 4000) + 0.4 (log 6000) or about 11.97 + 5.02 = 16.99.  Thus the first option (using a single list) gives better expected performance.

   If we use linear search with unsorted arrays instead of binary search then the time for the first option is proportional to 5000 (i.e., we expect to search about half the list before we find the item we're looking for). For the second option, a good customer will be found in time proportional to 2000 (half the list of 4000) while other customers will take time 4000 (time to look through entire list of good customers) + 3000 (half the list of other customers). Thus the time using the second strategy will be proportional to 0.6(2000) + 0.4(7000) = 4000. Thus when using linear search on unsorted lists the 2-list strategy is better.