Assignment Task
Dynamic Programming and Knapsack: bottom-up versus top-down. In class we discussed two versions of a DP algorithm for the Knapsack problem: a bottom-up version that computes the solutions to all subproblems (without repeating any solutions), and a top-down version that uses memoization (the book calls this the “memory functions” approach) to ensure that we solve only the subproblems that need to be solved. We discussed the notion that the top-down approach should be a constant factor faster than the bottom-up approach. This project explores this speedup, and looks for potential tradeoffs in this space.
1. Implement both of these algorithms in a language of your choice As a reference, see the book’s Section 8.2. Make sure your both of your algorithms work for any problem instance. Verify that your algorithms both have worst-case complexity of (nW) as analyzed in class.
Deliverable 1: Your implementation’s code and your verification of correctness.
2. Compare the performance of your two algorithms on arbitrary inputs. You may use a modified version of Knapsack random problem generator from Project 1; choose weights to be random integers between 1 and capacity W. Generate plots which show run times with respect to n, and plots which show run times with respect to W. Let n and W be as large as you need them to be to see a performance difference between your two algorithms.
Is the performance gap bigger when n is large or when W is large? If there is a difference, try to explain it.
Deliverable 2: Plots showing the time performance of your algorithm as a function of n and W for each algorithm, and discussion about the reasons for any performance differences between the two algorithms.
3. Compare the performance of your algorithms on special inputs. Now, craft inputs where all weights are relatively low (say, select the weights to be random integers between 1 and 10). Re-run the comparison between the two algorithms. Has the performance gap changed in any interesting way?
Deliverable 3: Plots showing the time performance of your algorithm as a function of n and W for each algorithm on special inputs, and discussion about the reasons for any performance differences between the two algorithms.
This CS5720 – IT Assignment has been solved by our IT experts at Schooling Best. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.
Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive,
plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.
