Describe a recursive relation and clearly define subproblems

Assignment Help Computer Engineering

Reference no: EM133703756

In the perfect split problem, you are given a list of n positive numbers and we want to determine whether the n numbers can be partitioned into two subsets (say A and B) such that the sum of elements in the subset A is equal to the sum of elements in the subset B. Design and analyze the best algorithm you can come up for this problem. If it helps assume that the numbers are bounded by some large number M. Your algorithm should run in time O(nS) where S is the total sum of all the input numbers. (hint: dynamic programming, does it remind you of a problem we saw in a previous homework?) Also describe how to reconstruct the optimal solution (i.e., the sets A and B). Full credit will only be given to solutions that clearly describe a recursive relation and clearly define subproblems that are needed to solve the original problem. (Bonus: What would you change if instead of 2 subsets, you wanted to construct 3 subsets with equal sum of elements?)

Reference no: EM133703756

Questions Cloud

Identify skills needed in organization and self-motivation : Identify and utilize skills needed in organization and self-motivation. Demonstrate ability to set and accomplish specific tasks and goals.

What compliance standard requires companies : What compliance standard requires companies to "develop, implement, and maintain a comprehensive written information security program that contains

Describe the elements of a high-level architecture : Describe the elements of a high-level architecture and the data collection systems that are essential for the weather station.

Call light of patient with diabetes : The LPN answers the call light of a patient with diabetes. The patient has a mild tremor, slight diaphoresis, and is fully oriented

Describe a recursive relation and clearly define subproblems : describe a recursive relation and clearly define subproblems that are needed to solve the original problem. (Bonus: What would you change if instead of 2 subset

What is the name of the cemetery : What is the name of the cemetery? Make a sketched map of the cemetery, including fences, paths, and other major features.

What religious order or other organization operated this irs : What church, religious Order or other organization operated this IRS? What can you learn about this Church, Order or organization?

Should ask if the user wants to run the program again : Error check inputs. Output to the screen a calendar representing that month, in the same form as shown in the sample run below. Finally, the program should ask

How can they be overcome before companies can make more use : how can they be overcome before companies can make more use of cryptocurrencies like bitcoin?

User Account

All Pages