CSci 3501 Algorithms and Computability - Lab 5.

September 30. Due Monday, October 6 at 11:59pm

What to submit and when:

Lab assignment

Work in pairs

Lab overview and goals

The goal of the lab is to continue a study of approximation and optimal algorithms. Your goal is to solve two cases of a ``shopping cart'' problem:

Suppose you won a grocery shopping spree to fill your cart with items of varying values and sizes. The object is to place the largest value of these items as possible into your cart which has a capacity bound, B. For example, consider B = 40 and the following list of items:

  Item     Value ($)     Size (units) 
A 60 10
B 100 20
C 120 30

Which items would you choose?

You need to solve two cases of this problem:

  1. Design and implement an efficient algorithm for choosing from n random items of varying sizes and values that fit within the capacity bound B as to maximize value. Items may not be duplicated, other than duplicates within the existing random data set.
  2. Design and implement an efficient algorithm for choosing fractional parts of n random items of varying sizes and values that fit within the capacity bound B as to maximize value. Objects in the list may be broken into components of any size before being added to the cart.

Please answer the following questions:

  1. What is the Big-O efficiency of your algorithms in part 1 and part 2, given n items?
  2. Does your algorithm for Part 1 find the optimal solution? If yes, please explain why. If not, please give an example when it does not, show the optimal item combination.
  3. Does your algorithm for Part 2 find the optimal solution? If yes, please explain why. If not, please give an example when it does not, show the optimal item combination.

Programming requirements and what to submit


CSci 3501 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.