Question 1 (14 marks) (Based on exercise 6.1 of DPU textbook) A substring (or continuous subsequence) of a sequence S is a subsequence made up of consecutive positions of S. For example, if S is
5; 15; 30; 10; 5; 40; 10
then 15; 30; 10 is a substring of S but 5; 15; 40 is not. Consider the problem of nding the substring of maximum sum: Input: A sequence a1; a2; : : : ; an of numbers.
Output: A substring of maximum sum.
Note that a substring of length 0 has sum 0.
a) Design and write (in pseudocode) a linear-time dynamic programming algorithm that solves this problem. (Note that this is to nd such a substring, not just its sum.)
b) Implement your algorithm from (a) in C + +, or Java. Hand in your code and I=O from at least three suitable test cases that demonstrate how well it handles various situations.
Question 2 (6 marks) Computing the number of combinations of size k of a set of n items
C(n; k) =
n
, where
n
=
n!
on a computer can be awkward. Computing the numerator
k
k
(n k)!k!
and
denominator separately and then dividing tends to over ow the integer representation for
the intermediate calculations; on the other hand, computing the overall result as the product of oating-point ratios nk nk 11 : : : n 1k+1 can introduce rounding errors.
To get a correct integer answer without over owing, we can use Pascal’s Formula, which de nes the number of combinations using the following recurrence:
C(i; j) =
C(i 1; j 1) + C(i 1; j) if 1 j i 1
1
if j = 0 or i = j
The recurrence is unde ned if j > i, or if either i or j is negative.
Design and write a dynamic programming algorithm based on the above recurrence that will compute nk given n and k.
1
