CPS616

W2017 Lab 6

Ryerson University

Worth: 4%

Analysis of Knapsack Pseudocode

Due: Friday March 24


Team size

This lab can be done in teams of 1 or 2.

Deadline

Please 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 Description

In 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.

Background

In 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.

Lab

This lab can be done directly in the lab6 description (docx or pdf).

Additional Material

Hand In

This 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


This page is maintained by Sophie Quigley (cps616@scs.ryerson.ca)
Last modified Sunday, 26-Mar-2017 22:07:35 EDT