## Description

Homework #4

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