ALGORITHMS FINAL 1. (60 pts.) Imagine a thief entering a house. In the house, there are...

Transcribed Image Text:

ALGORITHMS FINAL 1. (60 pts.) Imagine a thief entering a house. In the house, there are infinitely many items that can have only one of three different weights: 1 kg, 3 kgs, and 5 kgs. All of the items are discrete. The thief has a bag capacity of n kgs and strangely, he wants to steal the "smallest number of items". (a) (10 pts.) Give a mathematical recursive formulation for C(n) where C(n) denotes the smallest number of items the thief can steal using a bag capacity of n. (b) (5 pts.) Show that this problem has the overlapping subproblems property. (c) (15 pts.) Write a recursive algorithm (as a pseudocode) that returns the smallest number of items the thief can steal using a bag capacity of n. (d) (5 pts.) Show that the greedy choice of taking the largest weight items into the bag first fails to lead to an optimal solution. (e) (15 pts.) Write a dynamic programming algorithm (as a pseudocode) for finding the smallest number of items the thief can steal using a bag capacity of n. (f) (10 pts.) Provide the running time of your dynamic programming algorithm. Explain. ALGORITHMS FINAL 1. (60 pts.) Imagine a thief entering a house. In the house, there are infinitely many items that can have only one of three different weights: 1 kg, 3 kgs, and 5 kgs. All of the items are discrete. The thief has a bag capacity of n kgs and strangely, he wants to steal the "smallest number of items". (a) (10 pts.) Give a mathematical recursive formulation for C(n) where C(n) denotes the smallest number of items the thief can steal using a bag capacity of n. (b) (5 pts.) Show that this problem has the overlapping subproblems property. (c) (15 pts.) Write a recursive algorithm (as a pseudocode) that returns the smallest number of items the thief can steal using a bag capacity of n. (d) (5 pts.) Show that the greedy choice of taking the largest weight items into the bag first fails to lead to an optimal solution. (e) (15 pts.) Write a dynamic programming algorithm (as a pseudocode) for finding the smallest number of items the thief can steal using a bag capacity of n. (f) (10 pts.) Provide the running time of your dynamic programming algorithm. Explain.

Answer rating: 100% (QA)

This looks like an exam question about algorithms specifically focusing on recursion greedy algorithms and dynamic programming Heres a stepbystep brea... View the full answer