CSE 326 Autumn 2001

Homework Assignment 1

Due:

Friday, October 12

Readings:

Weiss Chapters 1, 2, 3.

Problems:

1. Consider the “Elegant” Maximum Sum Subsequence algorithm (EMSS) which we discussed in class.

a) Run the algorithm on the following array. Show your work at each stage, including the internal structures. (You may do this however you like: by hand, copy/paste/edit the picture below, write and run the program, etc. Note that the array below is not exactly like the one in the slides.)

-7

3

10

1

-15

16

-2

-1

4

-7

-5

-5

22

-1

b) What is the time complexity of this algorithm?

c) Give a simple, but reasonably formal, proof that no algorithm for Maximum Sum Subsequence that handles unordered input can have a better time complexity than this one.

d) Extra credit Describe how EMSS decides whether to include a negative number in the current sequence. An intuitive, informal description is fine (i.e., English, not pseudocode).

2. Weiss 2.2. Briefly state why each statement is true or false.

3. Weiss 2.4. Hint: it may help to think about the functions cN and log^k(N) graphically, where c is a constant. Note that log^k(N) is shorthand for [log(N)] ^k.

4. Weiss 2.5.

5. Suppose you have a recursive algorithm which at each new stage creates A new sub-problems, each of size B units less than the input size of the previous stage. [So if the algorithm starts on a problem of size N, then its second stage will have A sub-problems, each of size N-B.] Further, this algorithm takes constant time C on inputs of size less than B.

a) Derive the recurrence equation for this algorithm.

b) Using your general result from (a), determine the solution of the following recurrence:

T(n) = {2T(n – 3) for n ³ 3}

{1 for n < 3}

c) Which recurrence is asymptotically larger, the one in (b), or the one below?

T(n) = {2T(n – 2) for n ³ 3}

{1 for n < 3}

6. Extra credit

a) What is the running time of the Sieve of Eratosthenes, described in Weiss 2.21?

b) Suggest a simple optimization to the Sieve algorithm as described by Weiss. Does your optimization improve the time complexity?