## CPSC 223: Homework 2.

Due 2:00 AM, Friday, 3 February 2017

Extension 2:00 AM, Monday, 6 February 2017

#### P R E L I M I N A R Y S P E C I F I C A T I O N

REMINDER: Do not under any circumstances copy another student's code or give a copy of your code to another student. After discussing the assignment with another student, you may not take any written or electronic record away. Moreover, you must engage in a full hour of mind-numbing activity before you work on it again. Such discussions must be noted in your log file.

Bin packing is a significant problem in computer science. See https://en.wikipedia.org/wiki/Bin_packing_problem

In this assignment you will implement several (sub-optimal) solutions for one version of the problem. https://www.cs.ucsb.edu/~suri/cs130b/BinPacking.txt

There is a distinction between the online problem and the offline problem. In the former case, items appear sequentially, in real time. You must pack item n before even seeing item n+1. In the latter case, you have access to all items before you begin any packing. In general, the solutions to the offline problem are more efficient than the solutions for the online problem.

Here is a practical example which demonstrates the difficulty of online packing.

#### Program Specification

(40) Write a program "Pack" that processes command line arguments specifying the items to be packed and the algorithm(s) to use. The objective of the program is to pack all the items in the fewest possible bins.

You are given N items, of sizes s1, s2, ..., sN. All sizes are integers such that 0 < si <= 100. You have an infinite supply of bins of size 100. The goal is to pack the items in as few bins as possible.

```EXAMPLE:	20, 50, 40, 70, 10, 30, 80
```
The optimal packing would be three bins, such as:
```Bin 1: 20, 80
Bin 2: 50, 40, 10
Bin 3: 70, 30
```
Each bin is completely full.

Write a program

```  Pack [size]* [-next | -first | -best | -ffd | -bfd | -optm]+ -trace*
```
that performs various assignments of items to bins and prints the required number of bins. Here
• [size]* is a sequence of zero or more sizes, such that 0 < size <= 100
• [-next | -first | -best | -ffd | -bfd | -optm]* is a sequence of one or more flags (each either -next or -first or -best or -ffd or -bfd or -optm) that specify which algorithm to perform.
The flags have the following meanings:
• -next: online processing in order. see if the next item fits in the same bin as the last item. If not, then start a new bin.
• -first: online processing in order. check all previous bins and use first one that fits. If no fit, then start a new bin.
• -best: online processing in order. check all previous bins and use the one that has the tightest fit. If no fit, then start a new bin.
• -ffd: First fit decreasing, offline processing. Sort items in decreasing order, then apply first fit algorithm.
• -bfd: Best fit decreasing, offline processing. Sort items in decreasing order, then apply best fit algorithm.
• -optm: Optimal bin packing, per the paper by Korf (a variant of bfd). You may alternatively use the backtracking algorithm given above. This is an extra credit option worth at most 3 points out of 40. If you do not implement optm, merely use bfd and print a message "(using bfd)". NOTE: Packx does not implement Korf or backtracking.
• -trace: Flag used for debugging. If present, will print a line of output whenever an item is put in a bin. See examples below. If -trace is set, it applies to all algorithms on the command line. -trace itself may occur multiple times, but it is either off or on. Note: Trace also prints a line to stdout identifying the algorithm it is tracing. If an algorithm appears multiple times in the command line, the trace output occurs only once. If multiple algorithms are traced, the output order is next, first, best, ffd, bfd, optm, which might be different from the order of flags in the command line.
Pack prints the minimum number of bins using a statement like
```   printf ("%s %d\n", flagname, minbins);
```
where flagname is the current flag. When more than one flag is specified, Pack prints the corresponding minimum bin requirements on separate lines in the order specified on the command line. Flags may be specified more than once. Note that the item sizes must all PRECEDE the first function or trace flag on the command line.

All error output (usage and "Fatal Error" messages below) should be printed to standard error. The specific content of the error message will not be tested -- just that the error message is printed to standard error.) For example,

```   fprintf(stderr, "usage ...");
```
All other output should be printed to standard output. (Use normal printf.) Examples:
```% Pack
usage: Pack [sizes]* [-next | -first | -best | -ffd | -bfd | -optm]+ -trace*

% Pack 20 50 -40 70 10 30 80 -ffd
Fatal error: Invalid size: -40

% Pack 20 150 -40 70 10 30 80 -ffd
Fatal error: Invalid size: 150

% Pack 20 50 40 70 10 30 80 -bogus

% Pack 20 50 40 70 10 30 80
Fatal error: no algorithm specified.

% Pack 20 50 40 70 10 30 80 -first 4
Fatal error: Size option out of order: 4

% Pack 20 50 40 70 10 30 80 -first -next
-first: 4
-next: 5

% Pack -ffd
-ffd: 0

% Pack 20 50 40 70 10 30 80 -ffd -bfd -next
-ffd: 3
-bfd: 3
-next: 5

% Pack 20 50 40 70 10 30 80 -best -next -first
-best: 4
-next: 5
-first: 4

% Pack 20 50 40 70 10 30 80 -next -first
-next: 5
-first: 4

% Pack 20 50 40 70 10 30 80 -bfd -trace
Trace -bfd
arg: 0 val: 80 bin: 0 total: 80
arg: 1 val: 70 bin: 1 total: 70
arg: 2 val: 50 bin: 2 total: 50
arg: 3 val: 40 bin: 2 total: 90
arg: 4 val: 30 bin: 1 total: 100
arg: 5 val: 20 bin: 0 total: 100
arg: 6 val: 10 bin: 2 total: 100
-bfd: 3

% Pack 20 50 40 70 10 30 80 -best -trace
Trace -best
arg: 0 val: 20 bin: 0 total: 20
arg: 1 val: 50 bin: 0 total: 70
arg: 2 val: 40 bin: 1 total: 40
arg: 3 val: 70 bin: 2 total: 70
arg: 4 val: 10 bin: 0 total: 80
arg: 5 val: 30 bin: 2 total: 100
arg: 6 val: 80 bin: 3 total: 80
-best: 4

% Pack 10 20 30 40 50 -bfd -optm
-bfd: 2
-optm: 2 (using bfd)
```
Moreover, Pack should
• Fail "gracefully" (i.e., neither go into an infinite loop nor cause a memory dump) if any of the assumptions above is violated.
• Not make ANY assumptions as to the maximum length of the input
• Not use any global variables.
• Not execute a bin packing algorithm more than once, even if it appears multiple times on the command line.
• As stated above, when more than one flag is specified, Pack prints the corresponding minimum bin requirements on separate lines in the order specified on the command line. Flags may be specified more than once.
Use the submit command (see below) to turn in the source file(s) for Pack, a Makefile, and your log file (see below). You do not need to write your own Makefile. You may use the one in /c/cs223/hw2.

YOU MUST SUBMIT YOUR FILES (INCLUDING THE LOG FILE) AT THE END OF ANY SESSION WHERE YOU SPEND AT LEAST ONE-HALF HOUR WRITING OR DEBUGGING CODE, AND AT LEAST ONCE EVERY HOUR DURING LONGER SESSIONS. (All submissions are retained.)

#### Notes

1. When available, the public grading script will be /c/cs223/hw2/Tests/test.Pack (and my solution will be /c/cs223/hw2/Packx). To run it, type
```% /c/cs223/hw2/Tests/test.Pack
```
Unlike the previous assignment, Pack does not read standard input. It reads command line arguments. You can look at the test files to see how a specific test works. You may invoke a given test as follows:
```%  /c/cs223/hw2/Tests/test.Pack 01
```
(you may specify more than one test here).

If your output looks the same as what is expected, but your program still fails the test, there are probably some invisible characters in your output.

2. Keep track of how you spend your time in completing this assignment. Your log file should be of the general form (that below is fictitious):
```     ESTIMATE of time to complete assignment: 10 hours

Time     Time
Date  Started  Spent Work completed
----  -------  ----  --------------
1/13  10:15pm  0:45  Read assignment and relevant material in K&R
1/16   4:45pm  1:15  Sketched solution using a finite-state machine with
1/19   9:00am  2:20  Wrote the program and eliminated compile-time errors;
code passes eight tests
1/20   7:05pm  2:00  Discovered and corrected two logical errors; code now
passes eleven tests
1/23  11:00am  1:35  Finished debugging; program passes all public tests
----
7:55  TOTAL time spent

I discussed my solution with: Peter Salovey, Ben Polak, Tamar Gendler,
and Jonathan Holloway (and watched four episodes of The Simpsons).

*A brief discussion of the major difficulties encountered*
```
but MUST contain
• your estimate of the time required (made prior to writing any code),
• the total time you actually spent on the assignment,
• the names of all others (but not members of the teaching staff) with whom you discussed the assignment for more than 10 minutes, and
• a brief discussion (100 words MINIMUM) of the major conceptual and coding difficulties that you encountered in developing and debugging the program (and there will always be some).
This log will generally be worth 5-10% of the total grade.

N.B. To facilitate analysis, the log file MUST be the only file submitted whose name contains the string "log" and the estimate / total MUST be on the only line in that file that contains the string "ESTIMATE" / "TOTAL".

3. The submit program can be invoked in eight different ways:
```% /c/cs223/bin/submit  2  Makefile Pack.c time.log
```
submits the named source files as your solution to Homework #2;
```% /c/cs223/bin/check  2
```
lists the files that you submitted for Homework #2;
``` % /c/cs223/bin/unsubmit  3  error.submit bogus.solution
```
deletes the named files that you submitted previously for Homework #3 (which is useful if you rename a file or accidentally submit the wrong one);
```% /c/cs223/bin/makeit  4  Pack
```
runs "make" on the files that you submitted previously for Homework #4;
```% /c/cs223/bin/testit  5  Pack
```
runs the public test script for Pack using the files that you submitted previously for Homework #5; This may not be working. Use the testing instructions given above.
```% /c/cs223/bin/protect  6  Pack.c time.log
```
protects the named files that you submitted previously for Homework #6 (so they cannot be deleted accidentally);
```% /c/cs223/bin/unprotect  7  util.c time.log
```
unprotects the named files that you submitted previously for Homework #7 (so they can be deleted); and
```% /c/cs223/bin/retrieve  8  common.c time.log
```
and
```% /c/cs223/bin/retrieve  8  -d"2017/01/21 20:00" util.c
```
retrieve copies of the named files that you submitted previously for Homework #8 (in case you accidentally delete your own copies). The day and hour are optional and request the latest submission prior to that time (see the -d flag under "man co" for how to specify times).
4. When assignments are style graded, EVERY source file found in the submit directory will be reviewed. Thus prudence suggests using unsubmit to remove a file from the directory when you change its name or it ceases to be part of your solution. See http://zoo.cs.yale.edu/classes/cs223/doc/Style

Prudence (and a 5-point penalty for code that does not make) suggests that you run makeit ("makeit 2 Pack") after you have submitted the final version of your source files. Better yet, run testit ("testit 2 Pack").

5. The function exit() allows your program to stop immediately, without having to terminate any surrounding loops or to return to main() from a function. (To use it you must #include the header file <stdlib.h>.)
6. Pack reads from the command line and writes to stdout but does no other input/output.