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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- grade 11 mathematics past papers
- mathematics grade 11 question papers
- mathematics revision questions
- mathematics grade 8 question papers
- springer mathematics journals
- 303 vs 30 06
- lee enfield 303 for sale
- british 303 enfield rifle markings
- us treas 303 soc sec
- 303 stainless steel plate suppliers
- anodizing 303 stainless steel
- us treasury 303 soc sec