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.

https://www.youtube.com/watch?v=8NPzLBSBzPI

Reading (in addition to the above)

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 The flags have the following meanings: 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
Fatal error: bad argument: -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 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
                            one-character look-ahead
     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 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").

  4. 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>.)

  5. Pack reads from the command line and writes to stdout but does no other input/output.