Description
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.
-
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.)
-
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
