COSC 2006 –Data Structures I Assignment #2 Due: Monday, October 14, 2013 Recursion and Sorting A classic problem in computer science is known as the “bin-packing” problem. Say you’ve got a collection of items, each one has a certain weight, and a bunch of boxes that you can put them in, but the boxes can only hold a certain weight before they’ll break. The problem is, how do you pack the boxes to use as few boxes as possible? In our version of the problem, all the boxes are the same size. This is considered a hard problem, not because it’s challenging to program (well, it is a little) but because the best solution is a lot of work to find. In fact, the only way to get the best solution is to try all possible rearrangements of items into bins (and that’s a lot: for n items, there are n! arrangements). But there are easier solutions that do not give the best results. What we’re going to do is we’re going to try out five different possible solutions and compare the results: The “first fit”, the “first fit with sorting”, the “best fit”, the “best fit with sorting”, and the “optimal fit”. The “optimal fit” is the perfect solution, but it takes way too long in most cases (and in fact it won’t work for one of the two data sets we will test). You should find the first four solutions. The “optimal fit” is optional. If you solve it, you will get one bonus mark. Here is the first fit algorithm: 1. Start out with all the items outside of bins, and only one bin (the “leftmost”). 2. Attempt to place an item in a bin, starting from the leftmost. 3. If there is not enough room in any of the bins, create a new one to the right of the others, and place it there. 4. Repeat step 2-4 for every item. The best fit is a slight variation: 1. Start out with all the items outside of bins, and only one bin. 2. Find the bin with the least space left in it that can still fit the item (a variation of the “find the minimum value” algorithm); place the item in that bin. 3. If there is not enough…