## CSci 3501 Algorithms and Computability - Lab 4.

#### September 23. Due Monday, September 29 at 11:59pm

What to submit and when:

• All submissions are electronic: by e-mail to and CC to all lab partners. Please do not delete your e-mail from "Sent mail" or your mailbox until the end of the semester.
• When working on the lab, please comment your work so that it is clear what contributions of each person are.
• At the end of the lab each group should send me the results of their in-class work. Please indicate if this is your final submission.
• If your submission at the end of the lab time was not final, please send me(CC to the lab partner(s)) a final copy before the due time. Please use the subject "3501 Lab N", where N is the lab number.

### Lab assignment

Work in pairs; work with a different partner than last time

#### Lab overview and goals

The goal of the lab is develop and implement an approximation algorithm to solve a Bin Packing Problem: find a way to pack N items of diffrent fixed sizes into 3 bins with capacity B each. The algorithm should try to minimize the amount of unused bin space (or, equivalently, the total unpacked amount).

Example: given B=20 and items of sizes

``````
12, 4, 8, 15, 9, 3, 1, 10
``````

you can pack the bins as [12, 8], [1, 4, 15], and [9, 10], with the leftover item of size 3.

It is proven that to find the optimal solution, one needs to consider all possibilities of packing which is exponential in N. However, there are good approximation algorithms that find a solution close to optimal in times polynomial in N. Your goal is to develop such an approximation algorithm, implement it, test it, and analyze its efficiency.

#### Specific requirements

• Your algorithm must be an approximation algorithm, it is not allowed to check all possibilities.
• Your algorithm does not have to find the optimal solution for all cases but it should find a good solution for most cases.
• The input includes the capacity of the bins followed by the number of items N followed by the items themselves separated by spaces. For instance, the input for the above problem is
``` 20 8 12 4 8 15 9 3 1 10 ``` Here B= 20, N = 8, and the 8 items follow. See the Scanner class which allows you to read data from Java console (standard input).
Your output should be the list of elements in each bin, the list of the unpacked items, and the amount of unused space. Please make your answers readable.
• You may use any of the algorithms implemented in Java Collections class. See this tutorial for details.

#### What to submit

• Your program, appropriately documented.
• The test data and the results.
• A clear explanation of your algorithm in English.
• A brief explanation of when your algorithm finds the optimal solution and when it does not. Give an example of data for which your algorithm finds a solution that is not optimal. As an extra credit, compute the maximal difference between your solution and the optimal one, show and justify your computations.
• Compute the efficiency of your algorithm in terms of Big-O (i.e. Big-Theta of the worst case). Clearly explain it. If your program is calling a library method to perform a task or uses a Collections data structure, include efficiency of these operations. If you have questions about these methods and operations, let me know.

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.