1 the subset-sum problem is defined as follows given a set

Assignment Help Theory of Computation

Reference no: EM13380165

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 {b₁, b₂,....., b_n} 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 = {a_1,a₂,........, a_n} in which AB= b₁a₁ +b₂a₂ +......+ b_na_n. Where a_i is either 0 or 1.

Algorithm:

- For i= 1 to 2ⁿ (We have 2ⁿ different combinations set to be checked)

1. Create all the possible combinations of Array A and do:

- Compute Sum = 1028_Create all the possible combinations of Array.png

- If Sum = K then there is a subset sum to K. This subset B'= {b₁a₁, b₂a₂, ......, b_na_n}when a_i representing 1.

- return the subset B'

- Otherwise return there is no subset sum to K.

The run time is O(2ⁿ) 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 {b₁, b₂,....., b_n} 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.

Reference no: EM13380165

Questions Cloud

In numerical integration and in many other cases we need a : in numerical integration and in many other cases we need a polynomial named legendre polynomial. often the zeros i.e.

1 five reactors linked by pipes are shown in the following : 1. five reactors linked by pipes are shown in the following figure. the rate of mass flow through each pipe is computed

1 social changeshow have the recent changes in information : 1. social changeshow have the recent changes in information technology affected society? are these changes for the

Write a program that calculates an employees wage for a : write a program that calculates an employees wage for a week. an employees wage is calculated as followsi if the number

1 the subset-sum problem is defined as follows given a set : 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

1 write a script to help users calculate compressed file : 1. write a script to help users calculate compressed file size. prompt the user to enter the original size of a file

Question 1you are required to undertake a detailed analysis : question 1you are required to undertake a detailed analysis of the avl tree sorting algorithm for avlsort.to do this

1distinguish between the terms lsquoerp implementation and : 1.distinguish between the terms lsquoerp implementation and lsquoerp configuration2.explain the purpose of the entity

Introductionthis is an individual assignment in which you : introductionthis is an individual assignment in which you can explore the use of extensible files in web programming

User Account

All Pages