Due Thursday, 12 February 2009


CPSC 223b   Homework #N1   Algorithms and Storage Allocation
 
Algorithms may be stated in any language understood by a reasonably intelligent
being with common sense but no problem-specific knowledge (code must be very
well commented).  Solutions are due IN CLASS, not in my mailbox, ... .

REMINDER (The Gilligan's Island Rule):  When discussing an assignment (either
programming or nonprogramming) with other students, you may write on a board or
a piece of paper, but you may not take any written or electronic record away
from the discussion.  Moreover, you must engage in a full hour of mind-numbing
activity (such as watching back-to-back episodes of Gilligan's Island) before
you work on the assignment again.  This will ensure that you can reconstruct
what you learned from the discussion, by yourself, using your own brain.


P1. (7 points) Let X be an array of N doubles, so that the product of the
    elements in any contiguous subarray of X is well-defined (if the subarray
    is empty, the product is 1).  Describe a divide-and-conquer algorithm for
    finding the smallest, POSITIVE such product.  For example, with

	  I:   0    1    2    3    4    5    6    7    8    9
	X[I]:  3   -.1   4   -1   -5   -.9   2   -6   .5    0

    the smallest product is .4 and corresponds to the subarray X[1..3].
    Explain why your algorithm works as well as how.  Assuming that N is even,
    give a recurrence for the number C(N) of comparisons it requires (you need
    not solve this recurrence).  Hint:  The attached excerpt from Bentley
    describes a similar problem.

P2. (7 points) Design a dynamic programming algorithm for solving the problem
    posed in P1.  Explain why your algorithm works as well as how.  Give a
    recurrence relation for the number C(N) of comparisons it requires (you
    need not solve this recurrence).  Hint:  Dynamic programming is what
    Bentley calls "scanning".

P3. (6 points) Let X be an N x N array of integers so that the sum over any
    two-dimensional subarray of X is well-defined (if the subarray is empty
    the sum is zero).  Describe an algorithm that finds the largest such sum.
    Estimate how the running time of your algorithm grows as a function of N.
    Hint:  Try to reduce the problem to the one-dimensional version described
    in Bentley.

    Note:  Only partial credit will be awarded for an algorithm whose run-time
      is not o(N^4); i.e., if R(N) denotes the runtime of your algorithm when
      run on an N x N array, then R(N) / (N*N*N*N) must tend to 0 as N grows
      larger and larger.

P4. (6 points) Consider the n x n matrix

    [ a(1,1)  a(1,2)                                                  a(1,n)  ]
    [ a(2,1)  a(2,2)  a(2,3)                                                  ]
    [         a(3,2)  a(3,3)  a(3,4)                                          ]
    [                    .       .        .                                   ]
    [                            .        .         .                         ]
    [                                     .         .          .              ]
    [                                          a(n-1,n-2) a(n-1,n-1) a(n-1,n) ]
    [ a(n,1)                                               a(n,n-1)   a(n,n)  ]

    where all entries not shown are zero.  Describe three distinct schemes for
    storing the entries shown above in a one-dimensional, zero-based array B
    with 3n entries.  For each scheme include both a high-level description of
    where entries are stored as well as a loop-free, nonrecursive algorithm to
    compute where a(i,j) is stored given i and j.

P5. (1 point) How much time did you spend doing the first four problems?

								CS-223-01/28/09