MATHEMATICS 303



CS 315, Spring 2010, Writing Project 02

Due: Thursday, February 11, at 1:00pm, 10 Points, Please work individually

Read Section 4.1 in the textbook (the 3rd edition only, the maximum-subarray problem does not appear in previous editions), and then read the Wikipedia entry on the maximum sub-array problem,

Please submit a write-up of at least one page, as well as source code (no Python, please) to find the maximum-subarray in a given array. In your source, please provide a clear way to enter an array (editing the source code is acceptable).

Your write-up should address the following:

Describe the maximum-subarray problem

When does it arise?

Why is the maximum-subarray problem presented at this point in the textbook?

Why does the text present a more expensive algorithm for the maximum-subarray problem, if a linear-time algorithm for it exists? Give an overview of the algorithm presented in Section 4.1

Compare the linear-time algorithm presented in E 4.1-5 to Kadane’s algorithm presented in Wikipedia. Do these describe basically the same algorithm, or do they describe different algorithms? For your convenience, pseudo-code versions are provided below You should work through an example array, with BOTH algorithms, and include the tables in your write-up.

−2 |1 |−3 |4 |−1 |2 |1 |−5 |4 | |Array A:

In Moodle, please upload the MS Word document containing your write-up, as well as the source code implementing a version of it.

Kadane’s

n = A.length

max_so_far = 0

max_ending_here = 0

for j=1 to n

max_ending_here = max(0, max_ending_here + A[j])

max_so_far = max(max_so_far, max_ending_here)

return max_so_far

E 4.1-5

n = A.length

max.sum = -inf

ending.here.sum = -inf

for j=1 to n

ending-here-high = j

if ending-here-sum > 0

ending-here-sum = ending-here-sum + A[j]

else

ending-here-low = j

ending-here-sum = A[j]

if ending-here-sum > max-sum

max-sum = ending-here-sum

low = ending-here-low

high = ending-here-high

return (low, high, max-sum)

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download