State how you would recover an actual set s

Assignment Help Computer Engineering

Reference no: EM1327802

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

Reference no: EM1327802

Questions Cloud

How to write a class template sortablevector : how to Write a class template SortableVector. The class should have a member function that sorts the vector elements in ascending order (your choice of the sorting method).

Provide recommendations for a new strategy : Provide recommendations for improvements or recommendations for a new strategy.

Basic concepts in finance-solution set : You currently receive $10,000 per year on annuity contract. It will expire in eight years. Someone wants to purchase the contract from you. If you can earn 12% on other investments of the same quality and risk, how much would you be willing to sel..

Perform systems analysis in a variety of industries : Analyze a company, its business position, and the attainment of a competitive advantage through the understanding and application of information systems and technologies. Perform systems analysis in a variety of industries and competitive situatio..

State how you would recover an actual set s : Prove accuracy of your greedy algorithm by stating and proving the loop invariant.State how you would recover an actual set S.

Explain bets are on that google which now brokers ads : Explain Bets are on that Google, which now brokers ads for US' newspapers and Google's strategy is based on effective management of micro targeted segments

Change is good impact leadership at work : After watching the Change is good movie clip, list three ways in which it can impact your leadership at work.

Employment and type vii : Can Title VII override the employment and conditions detailed in an employment contract.

Calculate the price elasticity of demand for paint : Calculate the price elasticity of demand for paint and Illustrate the calculations.

User Account

All Pages