Reference no: EM13943758
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
|
What is maximum you will be willing to pay for investment
: An investment promises to pay an annuity of $150 monthly payments for seven years, but the payments do not start now. The first payment will be received 3 years from today. What is the maximum you will be willing to pay for this investment if your re..
|
|
Estimate bad debt expense under percentage of credit sales
: At December 31, 2009, Garner has a $1,000 credit balance in its allowance for doubtful accounts. Estimate the bad debt expense under the percentage of credit sales method.
|
|
Find the horizontal and vertical area moment of inertias
: Find the horizontal and vertical area moment of inertias of the cross-section shown with respect to its centroid.
|
|
What was your percent return
: HydroTech Corp stock was $50 per share a year ago when it was purchased. Since then, it paid an annual $4 per share dividend. The stock price is currently $55. If you owned 500 shares of HydroTech, what was your percent return?
|
|
State how you would recover the actual set s given a .
: Prove correctness of your greedy algorithm by stating and proving the loop invariant.
|
|
What is this years dividend yield
: Suppose a company has net income of 1,000,000 and a plowback ratio of 40%. There are 50,000 shares of stock outstanding. The company plans to increase dividends by 22% each year for the next 2 years and apply a 2.25% growth rate to dividends each yea..
|
|
Treasury bond or a corporate bond
: Dana intends to invest $25,000 in either a Treasury bond or a corporate bond. The Treasury bond yields 5 percent before tax and the corporate bond yields 6 percent before tax
|
|
At the end of an investors three year horizon
: A coupon bond which pays interest of $50 annually, has a par value of $1000, mature in 5 years, and is selling today a $114.52 discount from par value. the current yield on this bond is? Stock A has a current price of $40.00, a beta of 2.5, and divid..
|
|
Calculate the ending accounts receivable balance
: Beginning accounts receivable were $10,000. All sales were on account and totaled $700,000. Cash collected from customers totaled $650,000. Calculate the ending accounts receivable balance.
|