CSE 2320 - Homework 6

1
CSE 2320 - Homework 6 (You can solve all of P3 and parts of Knapsack. 
Total points: 115/100 (points past 100 are bonus) Topics: Memoization, Greedy, Dynamic Programming (Knapsack: unbounded, 0/1, fractional)
P1 (4 pts) Given this solution information, for the unbounded Knapsack problem below, recover the choices that gave the optimal
answer for knapsack capacity 19. Show your work (highlight or circle cells).
Item | A| B| C| D|
Weight| 3| 4| 7| 8|
Value | the item values are hidden as they should not be used in recovering the solution.
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| 11| 12| 13| 14| 15| 16| 17| 18| 19|
picked | | | | A| B| B| A| C| D| D| A| B| B| A| C| C| D| A| B| B|
Items picked for capacity 19: ………………………………………………
P2 (61 pts) Given the item types below, solve the following problems. Fill in the answer in the table and show your work below.
Item: A B C D
Weight: 3 4 6 7
Value: 4 7 10 12
Unbounded Knapsack 0/1 Knapsack Fractional Knapsack
Dynamic Programming $$:
Items:
$$:
Items:
Greedy $$:
Items:
$$:
Items:
$$:
Items:
2
a) (20 pts) Solve the unbounded Knapsack problem. Recover the items in the solution and show how you did that (e.g. highlight or circle
cells). Show your work as done in class.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A, 3, 4
B, 4, 7
C, 6, 10
D, 7, 12
b) (20 pts) Solve the 0/1 knapsack problem below (15pts). Use a star to show if the current item was used or not in the solution (8pts).
Recover the items in the solution and show how you did that (e.g. highlight or circle cells) (7 pts). Show your work as done in class.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A, 3, 4
B, 4, 7
C, 6, 10
D, 7, 12
c) (8 pts) What items will a Greedy algorithm based on the ratio, choose for an unbounded knapsack problem of size 14? Show your
work.
3
d) (8 pts) What items will a Greedy algorithm based on the ratio, choose for a 0/1 knapsack problem of size 14? Show your work.
e) (5 pts) What items will a Greedy algorithm based on the ratio, choose for a fractional knapsack problem of size 14? Assume you have
only one of each item. Show your work.
P3 (50 pts) Consider this recursive function:
int foo(int N){
if (N <= 1) return 5;
int res1 = 3*foo(N/2);
int res2 = foo(N-1);
if (res1 = res 2)
return res1;
else
return res2;
}
a) (6 points) Write the recurrence formula for the TIME COMPLEXITY of this function, including the base cases for N=0. You do NOT
need to solve the recurrence. Remember not to confuse the time complexity of the function with what the function calculates.
b) (8 points) Draw the tree that shows the function calls performed in order to compute foo(5) (the root will be foo(5) and it will have a
child for each recursive call.) Also show what each call returns by using an arrow pointing back from the child to the parent.
4
In a file called foo.c implement the following functions:
c) (10 pts) int foo_iterative (int N) - ITERATIVE solution of this code.
d) (20 pts) … foo_memoized(…. ) - the MEMOIZED solution. The function signature can be whatever you want. YOU MUST
PRINT THE RECURSIVE and BASE CASE CALLS. They should show the N that the function was called for and the text should be
indented based on the depth. See Homework 4 for a sample print with indentation based on the depth (min_rec_2_rec_calls_tree.txt )
and the code that does that (print_rec_call.txt).
e) (6 pts) int foo_wrapper(int N) - a wrapper function that calls the foo_memoized.
Your code should not show memory errors with Valgrind. (6 points penalty of it does)
If main does not call your other functions, they cannot be graded and you get 0 points.
Pseudocode for the main function:
print(Enter N:)
N <- integer read from user
while (N!=-1){
res1 = foo_iterative(N)
print(iterative result: res1)
res2 = foo_wrapper(N)
print(memoized result: res2)
print(Enter N:)
N <- integer read from user
}
Remember to include your name at the top.
Write your answers in this document or a new document called 2320_H6.pdf. It can be hand-written and scanned, but it must be uploaded
electronically. Place 2320_H6.pdf and foo.c in a folder called hw6, zip that and send it.