Data Structures Homework for Week 2.
Questions are taken from Adam
Drozdek Data structures and
algorithms in C++, Course Technology
2005 (3rd ed.), unless otherwise
noted.
This homework does not need to
be handed in.
Exercises 5.12
2, 3, 11,
14.
Supplemental
questions.
1. We saw an
algorithm with worst case complexity of
O(n2)
for the pillar problem. What input would cause the algorithm to realize this
worst case?
2. Consider a
sequence of
n
integer values (positive and negative). For concreteness assume that the integer
sequence is stored in an array A. The maximum consecutive sub-sequence
sum is the maximum value of the sum of a consecutive sub-sequence of A. For
example if A is the sequence -2, 11, -4, 13, -5, -2, 6 the answer is 20, that
is, 11 + (-4) + 13.
Determine an
algorithm that finds the maximum consecutive sub-sequence sum of a sequence of
integers. An
O(n2)
algorithm should be relatively easy to come up with. However, there is a very
compact
O(n)
algorithm.
Posted: Thu - January 11, 2007 at 02:18 PM