Reference no: EM13189429
1. The subset-sum problem is defined as follows: given a set B of n positive integers and an integer K, can you find a subset of B whose elements' summation is equal to K? Design an algorithm to solve this problem. Address its correctness and running time.
Input: set B of n positive integers {b1, b2,....., bn} and an integer K.
Output: whether there exist such a subset of B called B' its elements summation is equal to K.
B'= BA, where A = {a1, a2,........, an} in which AB= b1a1 +b2a2 +......+ bnan. Where ai is either 0 or 1.
Algorithm:
- For i= 1 to 2n (We have 2n different combinations set to be checked)
1. Create all the possible combinations of Array A and do:
- Compute Sum = 
- If Sum = K then there is a subset sum to K. This subset B'= {b1a1, b2a2, ......, bnan}when ai representing 1.
- return the subset B'
- Otherwise return there is no subset sum to K.
The run time is O(2n) since it needs to go through all possible subsets to find the subset that sum to K.
2. Suppose you have a procedure that can partition a set of positive integers into two equal weight subsets. How could you use this procedure to solve the subset-sum problem?
To solve this we use reduction. In which prove that subset-sum problem can be reduce to partition problem and visa versa.
The set B of n positive integers whose element summation is equal to an integer K.
Partition reduces to Subset Sum:
Calculate Sum = 
, which is the summation of all the given numbers. A partition ≤ Subset Sum if K = Sum/2.
Subset Sum reduces to Partition:
Calculate Sum = , which is the summation of all the given numbers.
Calculate some number x= Sum - 2K. Create new set A by add x to the set B {b1, b2,....., bn} U {x}, where the summation now is B+x. it is possible to split the numbers in A into some subsets iff they can summing up to K:
Subset sum of B indicates partition of A means the set that adds up to Sum with x form a partition.
Partition of A indicates subset sum of B means the numbers which are put together with x must add up to K. Therefore, a partition exists iff some numbers in the B add up to K.
|
What is the ordered pair that defines the y-intercept
: Given the quadratic equation y = 5x2-3x+7 .What is the ordered pair that defines the y-intercept?
|
|
Discuss the black legend
: Discuss the Black Legend and how to compare this legend to what Spain's approach was to exploration, conquest, and colonization. do you think Spanish were worse, better, or about the same as other Europeans?
|
|
Derive the euler-lagrange differential equation
: Derive the Euler-Lagrange Differential Equation (rigorously). Explain any theorems or results that you use in the derivation (e.g. don't just say "by the fundamental theorem of the calculus of variations" without telling what the fundamental theor..
|
|
What are initial levels of real gdp and labor productivity
: In the economy of Cape Despair, the subsistence real wage rate is $15 an hour. Whenever real GDP per hour rises above $15, the population grows, and whenever real GDP per hour of labor falls below this level, the population falls.
|
|
Subset-sum problem
: Calculate some number x= Sum - 2K. Create new set A by add x to the set B {b1, b2,....., bn} U {x}, where the summation now is B+x. it is possible to split the numbers in A into some subsets iff they can summing up to K:
|
|
Define a relation r on the set of all integers z
: Define a relation R on the set of all integers Z by xRy iff x+y = 3k for some integer k. Is R an equivalence relation on Z? Why or why not?
|
|
What is the maximum number of chairs
: A furniture factory needs 32.5 ft2 of fabric to upholster on a chair. Its Dutch supplier sends the fabric in bolts of exactly 200 m2. What is the maximum number of chairs that can be upholstered by 3 bolts of fabric (1 m = 3.281 ft)?
|
|
The heaviest slave trade took place in the what century
: An alliance with portugal brought wealth and foreign recognition to kongo, as well as what? The heaviest slave trade took place in the what century?
|
|
What is the break-even sales (units)
: If fixed costs are $300,000, the unit selling price is $31, and the unit variable costs are $22, what is the break-even sales (units) if fixed costs are reduced by $30,000?
|