Homework #3
COSC 5110
Analysis of Algorithms
1. Exercise 6.4.
2. Exercise 6.8.
3. Exercise 6.22.
4. In the Minimum Array Partition problem we are given an array A[1..n] of n integers. The
goal is to partition A into contiguous subarrays such that the maximum subarray sum is
minimized. For a small example, suppose
A = [ 24 0 88 -59 -54 13 20 -11 22 ].
An optimal partition is
[ 24 0 88 -59 -54 ] [ 13 ] [ 20 ] [ -11 22 ],
with a score of 20.
(a) Design an efficient algorithm for the Minimum Array Partition problem, argue its correctness, and analyze its run time.
(b) Implement your algorithm and solve the instances in the files test500, test1000, and
test2000. The first line of each file is a number n and the second line contains n integers
separated by spaces. Your algorithm should print an optimal partition and its score.
Submit your code and its output on these instances on WyoCourses.
1
