Create all the possible combinations of array a

Assignment Help Data Structure & Algorithms
Reference no: EM13309935

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.

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} {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.

These reference could help you :
1. Bron, C. and Kerbosch, J. "Algorithm 457: Finding All Cliques of an Undirected Graph." Comm. ACM 16, 48-50, 1973.
2. Tomita, E.; Tanaka, A.; and Takahashi, H. "The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments." Theor. Comput. Sci. 363, 28-42, 2006.

Reference no: EM13309935

Questions Cloud

Obtain the current in the inductor : An inductor has an inductance of 0.069 H. The voltage across this inductor is 56 V, What is the current in the inductor
What shape and distribution of mass should it have : To maximize the moment of inertia of a flywheel while minimizing its weight, what shape and distribution of mass should it have
Determine the ionization energy of hydrogen : Determine the ionization energy of hydrogen if the shortest wavelength in the Balmer series is found to be 3650 AO
A variable cross section data taken at two axial positions : An aqueous solution with a specific gravity of 1.12 flows through a channel with a variable cross section, data taken at two axial positions in the channel are shown here. Point 2 is 6.00 meters higher than point 1.
Create all the possible combinations of array a : 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..
How large an expansion tank do you specify : Fuel systems of modern cars are designed so thermal expansion of gasoline doesn't result in wasteful and polluting fuel spills. How large an expansion tank do you specify
Determine force exerted by the hydraulic cylinder on boom : A hoist mechanism is attached to the back of a pickup truck. The crate being moved by the hoist shown below weighs 200 lbs. Note: Point A is directly above point B and the vertical distance between points A and B is 16 inches.
Evaluate the equilibrium partial pressures of c2h6 : Calculate the equilibrium partial pressures of C2H6, N2, NH3, and C2H4. Peq(C2H6) = . Peq(N2) = . Peq(NH3) = . Peq(C2H4) = . (b) Calculate KP for this reaction. KP =.
At what distance from bottom of the hill did the car stop : on a windy day, a person on a cart (combined mass m of 70kg) begins at the top of a hill 10m hihg traveling at 3m/s, At what distance from the bottom of the hill did the car stop

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Graph in which every node is pivotal for at least two nodes

Give an example of a graph in which every node is pivotal for at least two di fferent pairs of nodes. Explain your answer.

  Conceptual model entity relationship diagram

Assume you are asked you to create a new entity-relationship diagram for a corporation for a customized shipment tracking system.

  Analyzing the use of database in an organization

Examine the use of databases in your company. Include what database applications are used. Conclude through proposing improvements.

  Determine the impedances of elements in laplace domain

Redraw the schematics with the impedance of each of the element shown in Laplace domain. Then determine the overall impedance of the entire circuit between the two ends of the shown circuit and express it in Laplace domain as a ratio of two polyno..

  System administrators database, network and application

What methods would you use to effectively manage a team of system administrators database, network, application working in your data center?

  Unctions for doing sort, search, display, replace, delete

create functions for doing sort, search, display, replace, delete, and add. You can use dynamic memory allocation for enlarge the size of pointer array for adding a new country.

  Calculations on rows and columns of an array

Make a menu bar with a document menu that includes a Perform Action command and an Exit command. The Perform Action command calculates either the sum or the average of rows or columns in array and displays result in a message box.

  Design a simple algorithm by giving pseudocode

Design a simple algorithm by giving pseudocode, for constructing a binary search tree T on n elements in O(nlogn) time with the property that any Find operation on T takes O(logn) time.

  Computing entropy of plaintext message

Compute the entropy of the plaintext message?

  Explain good algorithms to solve character pathfinding

You are working on the new computer game. One of implementation problems you are trying to solve is character pathfinding. What algorithms would be good to use and explain why?

  Discuss and define complex data binding

Discuss and define complex data binding and what benefits can this capability lend to a multiple table database application?

  Karatsuba''s divide-and-conquer algorithm

In class we discussed Karatsuba's divide-and-conquer algorithm for integer multiplication, which multiplies n-bit numbers by recursively multiplying n bit numbers. We take two numbers X and Y and split them each into their most significant half a..

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd