P R E L I M I N A R Y S P E C I F I C A T I O N Revised: 9/11/16 (trace output examples correction) Due 2:00 AM, Friday, 23 September 2016 CS-223 Homework #2 Bin packing 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 (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 pack all the items in the fewest possible bins. You are given N items, of sizes s1, s2, ..., sN. All sizes are such that 0 < si <= 1. You have an infinite supply of unit size bins. The goal is to pack the items in as few bins as possible. EXAMPLE: 0.2, 0.5, 0.4, 0.7, 0.1, 0.3, 0.8 The optimal packing would be three bins, such as: Bin 1: 0.2, 0.8 Bin 2: 0.5, 0.4, 0.1 Bin 3: 0.7, 0.3 Each bin is completely full. Write a program Pack [size]* [-next | -first | -best | -ffd | -bfd]+ -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 <= 1 [-next | -first | -best | -ffd | -bfd]* is a sequence of one or more flags (each either -next or -first or -best or -ffd or -bfd) 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. -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. 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, it 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. All error output (usage and "Fatal Error" messages below) should be 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]+ -trace* % Pack 0.2 0.5 -0.4 0.7 0.1 0.3 0.8 -ffd Fatal error: Invalid size: -0.400000 % Pack 0.2 1.5 -0.4 0.7 0.1 0.3 0.8 -ffd Fatal error: Invalid size: 1.500000 % Pack 0.2 0.5 0.4 0.7 0.1 0.3 0.8 -bogus Fatal error: bad argument: -bogus % Pack 0.2 0.5 0.4 0.7 0.1 0.3 0.8 Fatal error: no algorithm specified. % Pack 0.2 0.5 0.4 0.7 0.1 0.3 0.8 -first 0.4 Fatal error: Size option out of order: 0.400000 % Pack 0.2 0.5 0.4 0.7 0.1 0.3 0.8 -first -next -first: 4 -next: 5 % Pack -ffd -ffd: 0 % Pack 0.2 0.5 0.4 0.7 0.1 0.3 0.8 -ffd -bfd -next -ffd: 3 -bfd: 3 -next: 5 % Pack 0.2 0.5 0.4 0.7 0.1 0.3 0.8 -best -next -first -best: 4 -next: 5 -first: 4 % Pack 0.2 0.5 0.4 0.7 0.1 0.3 0.8 -next -first -next: 5 -first: 4 % Packx 0.2 0.5 0.4 0.7 0.1 0.3 0.8 -bfd -trace Trace -bfd arg: 0 val: 0.800000 bin: 0 total: 0.800000 arg: 1 val: 0.700000 bin: 1 total: 0.700000 arg: 2 val: 0.500000 bin: 2 total: 0.500000 arg: 3 val: 0.400000 bin: 2 total: 0.900000 arg: 4 val: 0.300000 bin: 1 total: 1.000000 arg: 5 val: 0.200000 bin: 0 total: 1.000000 arg: 6 val: 0.100000 bin: 2 total: 1.000000 -bfd: 3 % Packx 0.2 0.5 0.4 0.7 0.1 0.3 0.8 -best -trace Trace -best arg: 0 val: 0.200000 bin: 0 total: 0.200000 arg: 1 val: 0.500000 bin: 0 total: 0.700000 arg: 2 val: 0.400000 bin: 1 total: 0.400000 arg: 3 val: 0.700000 bin: 2 total: 0.700000 arg: 4 val: 0.100000 bin: 0 total: 0.800000 arg: 5 val: 0.300000 bin: 2 total: 1.000000 arg: 6 val: 0.800000 bin: 3 total: 0.800000 -best: 4 * Fail "gracefully" (i.e., neither go into an infinite loop nor cause a memory dump) if any of the assumptions above is violated. Moreover, Pack should not * Make ANY assumptions as to the maximum length of the input * Use any global variables. * Execute a bin packing algorithm more than once, even if it appears multiple times on the command line. Use the submit command (see below) to turn in the source file(s) for Pack, a Makefile, and your log file (see below). 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/test.Pack (and my solution will be /c/cs223/hw2/Packx). To run it, type % /c/cs223/hw2/test.Pack (here % is the shell prompt). The script uses make to create Pack. To run each test it redirects the test file (e.g., /c/cs223/hw2/Tests/t01.c for Test #01) to the standard input of Pack and redirects the standard output to a temporary file. Then it compares this file with the expected output for that input (e.g., /c/cs223/hw2/Tests/t01.cs for Test #01). Your program passes the test only if the two files are identical. To run your program on the file for Test #01, type % ./Pack < /c/cs223/hw2/Tests/t01.c To compare the output from your program with the expected output, type % ./Pack < /c/cs223/hw2/Tests/t01.c | cmp - /c/cs223/hw2/Tests/t01.cs (cmp outputs the first character where the files differ) or % ./Pack < /c/cs223/hw2/Tests/t01.c | diff - /c/cs223/hw2/Tests/t01.cs (diff outputs the lines where they differ but uses a looser definition for "identical") or % /c/cs223/hw2/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. To make all characters visible (except blanks), type % ./Pack < /c/cs223/hw2/Tests/t01.c | cat -vet or % ./Pack < /c/cs223/hw2/Tests/t01.c | od -bc 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). 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 util.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; % /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"2016/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 In your spare time, you might think about how to automate the tests in the online style sheet. That would be a pretty good homework assignment. 5. 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"). 6. You can implement Pack using standard arrays. You do not need dynamic arrays, stacks, linked lists, or other advanced data structures. You may use floats for the sizes. We will not test for double precision values. 7. 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 .) CS-223-00/11/16