Given a set of n positive integers, partition the integers into two subsets of equal or...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Given a set of n positive integers, partition the integers into two subsets of equal or almost equal sum. The goal is to partition the input numbers into two groups such that the difference between the sums of the elements in the two group is minimum or as small as possible. a) (8 pts) Since no polynomial solutions are known for the above problem, implement an exponential algorithm for finding the optimal solution for any instance of the problem and test it for small input samples. Identify the maximum input size for which an optimal solution is possible to obtain using your algorithm in reasonable time (for example 3 hours). Hint: Every possible partition (solution) can be represented by a binary array of size n. b) (8 pts) Implement one heuristic for solving the partitioning problem. Specify several input cases for the heuristic for which the heuristic performs different. Your input samples should include two cases in which the algorithm succeeds and fails to find the optimal solution. Compare the results of the heuristic to the results of the exponential algorithm using small input samples. Also, compare the results of the two heuristics using larger input samples. c) (4 pts) Although the general version of the partitioning problem in intractable, special cases of the problem may have polynomial solutions. For example, assume that each of the input integers are either x or 2x, for some positive integer x. Suggest a polynomial and optimal algorithm for finding the best partitioning in this case? Given a set of n positive integers, partition the integers into two subsets of equal or almost equal sum. The goal is to partition the input numbers into two groups such that the difference between the sums of the elements in the two group is minimum or as small as possible. a) (8 pts) Since no polynomial solutions are known for the above problem, implement an exponential algorithm for finding the optimal solution for any instance of the problem and test it for small input samples. Identify the maximum input size for which an optimal solution is possible to obtain using your algorithm in reasonable time (for example 3 hours). Hint: Every possible partition (solution) can be represented by a binary array of size n. b) (8 pts) Implement one heuristic for solving the partitioning problem. Specify several input cases for the heuristic for which the heuristic performs different. Your input samples should include two cases in which the algorithm succeeds and fails to find the optimal solution. Compare the results of the heuristic to the results of the exponential algorithm using small input samples. Also, compare the results of the two heuristics using larger input samples. c) (4 pts) Although the general version of the partitioning problem in intractable, special cases of the problem may have polynomial solutions. For example, assume that each of the input integers are either x or 2x, for some positive integer x. Suggest a polynomial and optimal algorithm for finding the best partitioning in this case?
Expert Answer:
Answer rating: 100% (QA)
I can provide you with a basic implementation of an exponential a... View the full answer
Related Book For
Discrete and Combinatorial Mathematics An Applied Introduction
ISBN: 978-0201726343
5th edition
Authors: Ralph P. Grimaldi
Posted Date:
Students also viewed these programming questions
-
THIRD AVENUE SOFTWARE HEALTH-CARE APP PROJECT This case is new for the ninth edition of Information Technology Project Management . The case provides an opportunity to apply agile and Scrum...
-
Given a set of N positive integers S={x1, x2, x3,, xk, xN}, decide whether S can be partitioned into two sets S0 and S1 such that the sum of numbers in S0 equals to the sum of numbers in S1. This...
-
Walmart Stores has run into opposition when it has tried to open stores in certain towns in the United States. Walmarts capital budgeting process has determined that these locations would be...
-
When a company files for bankruptcy, many of its personnel quit and the company finds it difficult to attract new employees to fill these roles. If you were working for a company that filed for...
-
1. What problems did IGT face before the implementation of the ERP system? 2. How does the new system help control processes? 3. Compared to the situation in 2002, what are the benefits of the ERP...
-
Aaron loans Victoria \($10,000\) with interest compounded at a rate of 8% annually. How much will Victoria owe Aaron if she repays the entire loan at the end of five years?
-
Assume you are risk-averse and have the following three choices. Which project will you select? Compute the coefficient of variation foreach. Expected Value S2,200 2,730 2,250 Standarod Deviation...
-
Tirtirogu Corp.'s bonds currently sell for $1,145.68 and have a $1,000 par value. They have a 7.50% annual coupon rate and a 15-year maturity. What is the bond's yield to maturity?
-
Develop a spreadsheet for computing the demand for any values of the input variables in the linear demand and nonlinear demand prediction models in Examples 1.7 and 1.8 in the chapter.
-
Newmarket Architects Inc. (NAI) creates six-month "zolling" aggregate plans, which are recomputed monthly. For competitive reasons (they would need to divulge proprietary design criteria, methods,...
-
Large countries are often interested in forming a regional free trade bloc to capture the efficiencies it can create. Do you think these agreements generally improve living standards in smaller...
-
Answer this letter to Ask Marilyn [28]: Youre at a party with 199 other guests when robbers break in and announce that they are going to rob one of you. They put 199 blank pieces of paper in a hat,...
-
Some economists have argued that one important role of rating agencies is to keep the managers of firms that issue bonds from using the funds raised in ways that would not be in the best interestsof...
-
Some people believe that the rise of regional trading blocs threatens free trade progress made by the World Trade Organization (WTO). What arguments can you present to counter this point of view? Do...
-
If the age at death of a 20-year-old U.S. woman is normally distributed with a mean of 76.4 years and a standard deviation of 8.1 years, what is the probability that she will live past 80?
-
5) Michigan Company has budgeted the following costs for the production of its only product: Direct Materials $35,000 Direct Labor 25,000 Variable indirect production costs 30,000 Fixed indirect...
-
Find the velocity, acceleration, and speed of a particle with the given position function. r(t) = (t 2 , sin t - t cos t, cos t + t sin t), t > 0
-
Find a maximum flow for the network shown in Fig. 13.23. The capacities on the undirected edges indicate that the capacity is the same in either direction. [However, for an undirected edge a flow can...
-
The following provides an outline for a proof of Theorem 17.18. (a) Consider a parallel class of lines given by y = mx + b, where m F, m 0. Show that each line in this class intersects each...
-
Use the Caesar cipher to encrypt the plaintext: "All Gaul is divided into three parts."
-
See Table 2.5 showing financial statement data and stock price data for Mydeco Corp. a. How did Mydecos book debt-equity ratio change from 2019 to 2023? b. How did Mydecos market debt-equity ratio...
-
See Table 2.5 showing financial statement data and stock price data for Mydeco Corp. a. Compute Mydecos PE ratio each year from 2019 to 2023. In which year was it the highest? b. What was Mydecos...
-
See Table 2.5 showing financial statement data and stock price data for Mydeco Corp. a. Compute Mydecos ROE each year from 2019 to 2023. b. Compute Mydecos ROA each year from 2019 to 2023. c. Which...
Study smarter with the SolutionInn App