1. Set-partition problem, given a set S = {a, a, ..., an of positive integers (denoting...

Transcribed Image Text:

1. Set-partition problem, given a set S = {a₁, a₂, ..., an of positive integers (denoting asset values), requires partitioning into subsets S₁ and S₂ that minimizes the difference in the total values of S₁ and S₂. a) Identify a greedy procedure to accomplish Set- partitioning. Does your procedure always produce the best partitioning? Either prove that or provide a counter-example. (8 pts) b) Now imagine the assets are held in gold/silver/ copper bullion: that is each asset a; is either a gold, silver, or copper coin. Revise your greedy procedure for partitioning these assets. (If it helps, assume a gold coin is worth 100 copper coins and a silver coin 10 copper coins.) Reason why it is either an algorithm or provide a counter-example.(7 pts) 1. Set-partition problem, given a set S = {a₁, a₂, ..., an of positive integers (denoting asset values), requires partitioning into subsets S₁ and S₂ that minimizes the difference in the total values of S₁ and S₂. a) Identify a greedy procedure to accomplish Set- partitioning. Does your procedure always produce the best partitioning? Either prove that or provide a counter-example. (8 pts) b) Now imagine the assets are held in gold/silver/ copper bullion: that is each asset a; is either a gold, silver, or copper coin. Revise your greedy procedure for partitioning these assets. (If it helps, assume a gold coin is worth 100 copper coins and a silver coin 10 copper coins.) Reason why it is either an algorithm or provide a counter-example.(7 pts)

Answer rating: 100% (QA)

ANSWER ANSWER A Greedy Algorithm One way to deal with the issue is mirroring how kids pick groups fo... View the full answer