Proof of optimality of algorithm

In summary: The process of creating the partition can be thought of as putting dividers into the array, and then taking the sum of the integers in each divider. So the sum of the integers in each segment would be the sum of the integers in the divider and the next integer in the array.In summary, the algorithm to partition an array into segments so that the sum of the integers in every segment does not exceed a given value is O(n). The algorithm is optimal when the number of segments produced by the algorithm is minimized.
  • #1

Homework Statement


Given an array of positive integers A[1, . . . , n], and an integer M > 0, you want to partition the array into segments A[1, . . . , i1], A[i_1 + 1, . . . , i2], . . . , A[i_k−1 + 1, . . . , ik], so that the sum of integers in every segment does not exceed M, while minimizing the number of segments k. You can assume that M ≥ A for all i (which guarantees that such a partition exists). Design an O(n) greedy algorithm for solving this problem and prove that it is optimal (i.e. that the obtained partition has the smallest possible number of segments).

Homework Equations

The Attempt at a Solution


The algorithm is very easy just keep adding the values in the array until you see that the sum is greater than M, then start a new segment.

How can I prove that it's optimal?
 
Physics news on Phys.org
  • #2
Sebastian Martinez said:
How can I prove that it's optimal?
Try using induction on the number of segments m found by the algorithm. The base case where m=1 is trivial, as it's not possible to have fewer than one segment, provided n>0.
Then try to prove that, if the algorithm produces a partition with the minimum number of segments whenever it comes up with an m-segment partition, it will also do so when it comes up with an m+1 segment partition.
 
  • #3
andrewkirk said:
Try using induction on the number of segments m found by the algorithm. The base case where m=1 is trivial, as it's not possible to have fewer than one segment, provided n>0.
Then try to prove that, if the algorithm produces a partition with the minimum number of segments whenever it comes up with an m-segment partition, it will also do so when it comes up with an m+1 segment partition.
So we can prove the m+1 by expanding the array with k elements in a way that their sum is less than M?
 
  • #4
Think about the partition the algorithm has produced with m+1 segments. What can we say about the sub-partition consisting of the first m segments, compared to any other possible partition of that part of the array?
 
  • #5
andrewkirk said:
Think about the partition the algorithm has produced with m+1 segments. What can we say about the sub-partition consisting of the first m segments, compared to any other possible partition of that part of the array?
it has the least number of segments in that part of the array
 
  • #6
On reflection I think that induction hypothesis may be harder than necessary. An easier one to prove, because it's more closely aligned with how the algorithm works, is the proposition P(n), which says that, when the algorithm completes the n-th segment, there is no other n-segment partition that can hold a greater number of consecutive elements (starting with the first element) than the one the algorithm has created.

P(1) is very easy to prove, and proving P(m+1) from P(m) is also fairly easy. Having proven that, it's then only a few steps to show that if the algorithm divides the array into m segments, no other partition can divide it into only m-1 segments.
 
  • #7
Yo are you in Manfred's algorithm class too?
 
  • #8
I'm not sure about adding values in the array in order, consider the case for M = 9, A[8] = {1 2 3 4 5 6 7 8}

Scanning in order results in 5 segments:

{1 2 3} {4 5} { 6} {7} {8}

but 4 segments are possible.

{1 8} {2 7} {3 6} {4 5}

I'm wondering if there are cases where taking values from near the start, near the middle, and near the end is needed. Seems that the basic idea is to have the sum of each segment close to or equal to M, or to minimize the sum of the k instances of {M - sum of each segment}.
 
  • #9
rcgldr said:
Scanning in order results in 5 segments:

{1 2 3} {4 5} { 6} {7} {8}

but 4 segments are possible.

{1 8} {2 7} {3 6} {4 5}
It is not made clear in the OP, but I took it that the elements of the array are sorted in ascending order (they may even be consecutive integers), and they have to retain their order in the partition, both within and between segments. So the above partition into four segments is not permissible - it preserves order within but not between segments.
The reason I interpreted it that way is that I'm pretty sure no O(n) algorithm can work otherwise, because a sort would be needed to find the optimal partition, and sorting is O(n^2). In addition, the use of the word 'segment' suggests that the only disturbance allowed is making a cut. If rearranging were allowed, I think the word 'subset' would have been used instead.
The process of creating the partition can be thought of as putting dividers into the array between selected elements, without disturbing the order.
 
  • #10
andrewkirk said:
I took it that the elements of the array are sorted in ascending order (they may even be consecutive integers), and they have to retain their order in the partition, both within and between segments.
Your interpretation is how the statement reads, but it seems too simple to be the intended problem.
 

1. What is "Proof of optimality" in algorithm design?

"Proof of optimality" refers to the process of demonstrating that a given algorithm is the most efficient or optimal solution to a specific problem. This involves mathematical analysis and comparison with other potential solutions.

2. Why is it important to have a proof of optimality for an algorithm?

Having a proof of optimality ensures that the algorithm is the most efficient solution to a problem, which can save time and resources in the long run. It also helps to establish the validity and reliability of the algorithm for use in real-world applications.

3. How is the optimality of an algorithm determined?

The optimality of an algorithm is determined through mathematical analysis, such as time and space complexity analysis, and comparison with other potential solutions. This involves considering factors such as efficiency, accuracy, and scalability.

4. Can an algorithm be proven to be optimal for all cases?

No, an algorithm may be optimal for a specific problem or set of inputs, but not necessarily for all cases. Different algorithms may be optimal for different inputs or scenarios.

5. Are there different levels of optimality for algorithms?

Yes, there are different levels of optimality for algorithms. An algorithm may be considered optimal in terms of time complexity, but not space complexity, or vice versa. It is important to consider multiple factors when determining the optimality of an algorithm.

Suggested for: Proof of optimality of algorithm

Replies
1
Views
653
Replies
1
Views
923
Replies
2
Views
990
Replies
2
Views
980
Replies
2
Views
955
Replies
2
Views
1K
Replies
1
Views
828
Back
Top