## CPS616 |
## W2017 Lab 6 | |

## Worth: 4% |
## Analysis of Knapsack Pseudocode |
## Due: Friday March 24 |

## Team sizeThis lab can be done in teams of 1 or 2.## DeadlinePlease note that the Friday March 24th deadline is a hard one. This means that the late penalty is -100%. The reason for this is that Lab 7 will depend on it and a solution will be posted on the weekend. Of course the solution is more or less the solution to the written portion of the midterm.## Lab DescriptionIn this lab you will analyse the efficiency of a reduce by one algorithm to solve the knapsack problem and you will work on improving it by tweaking the algorithm in pseudocode.In lab 7, you will be asked to improve it further by turning it into a dynamic programming algorithm and also by paying attention to the implementation of some Java libraries. You will also be asked to profile the performance of the various versions in a very similar way to the profiling you did for the assignment.
## BackgroundIn this lab and lab7, you are asked to work on solutions to the Knapsack problem.You are provided with an algorithm (docx or pdf) to solve this problem. This is the algorithm from the midterm. Note that it is written in pseudocode. You will be asked to make modifications using proper pseudocode. To learn about this, please refer to the wikipedia link just provided as the pseudocode guidelines. ## LabThis lab can be done directly in the lab6 description (docx or pdf).## Additional Material- Textbook chapter 2.3, 2.4, 3.4
- Class handout on Analysis of Efficiency
- The knapsack problem is also defined on Page 7 of the class handout on Brute Force algorithms.
- Sum calculator
## Hand InThis lab is a paper submission to be handed in at the Computer Science office.- Hand in a printout of your marking sheet and written solution (docx or pdf).
- In addition to the lab itself you will need to also submit the Lab Submission Declaration on D2L. This lab will not be graded unless this declaration has been submitted
## Solutions |

Last modified Sunday, 26-Mar-2017 22:07:35 EDT