Sometimes a slight change in a problem can significantly alter the form of its s

Question

Sometimes a slight change in a problem can significantly alter the form of its solution. For example, find a simple algorithm for solving the following problem and classify it using big-theta notation: Divide a group of people into two disjoint subgroups (of arbitrary size) such that the difference in the total ages of the members of the two subgroups is as large as possible.

1. Ignore the need to describe “big theta” ().

2. In the first algorithm, a group may not be an “empty group.” Also, for the second algorithm, provide a strong argument for why your solution is optimal — you aren’t required to prove it — but your logic should convince everyone in your group. Be sure your algorithm performs well with “edge cases” such as 15 one year olds, or a group of 15 one year olds and a single 99 year old senior.

Explanation / Answer

It is trivial in the way that it requires you to find only the minimum element (in case the subgroups should contain at least 1 member), otherwise it is already solved.
,we have ruled out the possibility of a set being an empty set. So all we have to do is just a linear search to find the min age and then put it in a set B. SetA now has all the other ages excet the age of setB,which is the min age.So here is the max difference of the total ages of the two sets,as high as possible

start the function with generate(baseVec,"",0,0) where "" stand for an empty vector.

The algo can be drastically improved by applying it to a sorted array, hence adding a test condition to stop branching, but the idea stays the same.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.