SubSet Sum using Greedy & Dynamic Algorithms
Not what you're looking for?
1. SubsetSum (greedy algorithms)
A SubsetSum is defined as follows: given positive integers a1 . . . an (not necessarily distinct), and a positive integer t, find a subset S of (1 . . . n) such that ∑iε s ai = t, if it exists.
a) Suppose each ai is at least twice as large as the sum of all smaller numbers aj . Give a greedy algorithm to solve SubsetSum under this assumption.
b) Prove correctness of your greedy algorithm by stating and proving the loop invariant.
2) SubsetSum (dynamic programming) Now suppose that the ai values are arbitrary. Design a dynamic programming algorithm to solve the SubsetSum problem. The running time of your algorithm should be polynomial in both n and t.
a) Give the definition of the array A you will use to solve this problem and state how you find out if there is such a set S from that array.
b) Give the recurrence to compute the elements of the array A, including initialization.
c) State how you would recover the actual set S given A .
d) Analyze the running time of your algorithm (including the step reconstructing S), in terms of n and t. hide problem.
Purchase this Solution
Solution Summary
Subset Sums using greedy and dynamic algorithms are examined in the solution.
Solution Preview
Please see the attachment.
Problem #1 (Greedy Algorithm)
Suppose A is the array of positive integers with length n and it is sorted by the decreasing order. That is, A[0] >= A[1] >= A[2] >= ... >= A[n-1], t is a positive integer. We want to find a subset of A, such that the sum of the subset is equal to t. Suppose the subset is S.
(a) Here is the greedy algorithm.
SubSetSum(A, t, S)
BEGIN
1. Set S = {};
2. For i = 0 To n-1 Do
2.1 If t >= A[i] Then Do
2.1.1 S = S + A[i];
2.1.2 t = t - A[i];
2.2 End If
3. End For
4. If t==0 Then Return S
Else print "There is no solution. "
END
(b) Now I prove the correctness of the above algorithm.
The loop 2 is going from the biggest element to the smallest element of the array A. If t is greater than or equal to some A[i], then this A[i] must be in the subset S. ...
Purchase this Solution
Free BrainMass Quizzes
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.
C++ Operators
This quiz tests a student's knowledge about C++ operators.
C# variables and classes
This quiz contains questions about C# classes and variables.
Word 2010: Table of Contents
Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.
Excel Introductory Quiz
This quiz tests your knowledge of basics of MS-Excel.