Assignment $2$: Knapsack Problem $-$ Brute Force vs$.$ Dynamic Programming

$$

Objective:

The goal of this assignment is to compare the performance of the brute force and dynamic programming solutions to the Knapsack Problem. You will analyze the efficiency of both approaches across varying input sizes.

$$

Instructions:

Part $1$: Implement the Algorithms

$1.$ Brute Force Solution:

o Implement a recursive brute$-$force solution to the Knapsack Problem.

o Explore all subsets of items to find the optimal solution.

o Note: you can use you implementaion from lab$3.$

$2.$ Dynamic Programming Solution:

o Implement a bottom$-$up dynamic programming approach using a table to store intermediate results.

o Note: you can use your implementaion from lab$7.$

$$

Part $2$: Experimental Setup

$1.$ Generate random test cases for the Knapsack Problem:

o Item weights and values should be randomly generated.

o Knapsack capacities should vary to reflect different constraints.

$2.$ Test for increasing input sizes:

o Number of items:$5,10,15,20,25.$

o Capacity of the knapsack should also increase proportionally.

o You need to use the same lists for both algoritms.

$$

Part $3$: Measure Execution Times

$1.$ Use a$$time$$module to record execution times for:

o The brute force solution.

o The dynamic programming solution.

$2.$ Record execution times for each input size.

$$

Part $4$: Analyze Results

$1.$ Plot the execution times:

o X$-$axis: Number of items.

o Y$-$axis: Execution time.

o Two lines: one for brute force, one for dynamic programming.

$2.$ Discuss:

o Which solution is faster for larger input sizes and why?

o Relate the results to the theoretical time complexities of both algorithms.

$$

Deliverables:

$1.$ A table showing execution times for each algorithm at different input sizes.

$2.$ A graph comparing execution times.

$3.$ A detailed discussion analyzing the results.

$$

Provide the code in the Appendix.