P R E L I M I N A R Y S P E C I F I C A T I O N Due 2:00 am, Friday, 14 February 2020 CPSC 223b Homework #2 The Bin Packing Problem REMINDER: Do not under any circumstances copy someone else's code for this assignment, give your code to someone else, or make it publicly available. After discussing any aspect of the assignment with anyone other than a member of the teaching staff (such discussions must be noted in your log file), do not keep any written or electronic record and engage in some mind-numbing activity before you work on the assignment again. Sharing ANY related document (e.g., code or test cases) is a violation of this policy. Since code reuse is an important part of programming, you may study published code (e.g., from textbooks or the Net) and/or incorporate it in a program, provided that you give proper attribution in your log file and in your source file(s) (see the syllabus for details) and that the bulk of the code submitted is your own. Note: Removing/rewriting comments, renaming functions/variables, or reformatting statements does not convey ownership. (40) Write a program % ./Binpack BIN_SIZE [ITEM_SIZE]* [-opt | -ff | -bf | -ffd | -bfd]* (where % is the shell prompt) that prints the number of bins needed to store a set of items. Here BIN_SIZE is the capacity of each bin and must be a positive integer. [ITEM_SIZE]* is a sequence of zero or more item sizes, each of which must be a positive integer that is less than or equal to BIN_SIZE. [-opt | -ff | -bf | -ffd | -bfd]* is a sequence of zero or more flags, each either -opt or -ff or -bf or -ffd or -bfd. The flags specify how to compute the assignment of items to bins: -opt Use backtracking to find the minimum number of bins required. -ff Use the first-fit heuristic: Process the items in the left-to-right order that they appear on the command line, and place each item in the lowest-numbered bin in which it fits. -ffd Apply the first-fit heuristic, but first sort the list of items in decreasing order of size (non-increasing order in the event of ties). -bf Use the best-fit heuristic: Process the items in the left-to-right order that they appear on the command line, and place each item in the bin that would have the least amount of room remaining (the lowest- numbered such bin in the event of ties). -bfd Apply the best-fit heuristic, but first sort the list of items in decreasing order of size (non-increasing order in the event of ties). Note that the notation above implies that all item sizes must *precede* the first flag. Binpack prints each number of bins using a statement like printf ("MMMM %d\n", numberofBins); where MMMM is the current flag (blank-padded to four characters). When more than one flag is specified, the corresponding numbers of bins appear on separate lines in the same order as the left-to-right order that the flags appear on the command line. Flags may be specified more than once. Examples: % ./Binpack 100 31 41 59 26 53 58 97 93 23 84 62 64 33 % ./Binpack 100 31 41 59 26 53 58 97 93 23 84 62 64 33 -opt -opt -opt 8 -opt 8 % ./Binpack 96 14 14 14 14 14 14 33 33 33 33 33 33 49 49 49 49 49 49 -ff -ffd -ff 10 -ffd 6 % ./Binpack 96 14 14 14 14 14 14 33 33 33 33 33 33 49 49 49 49 49 49 -bfd -bf -bfd 6 -bf 10 Use the submit command to turn in the source file(s) for Binpack, a Makefile, and your log file (see the specification for Homework #1). YOU MUST SUBMIT YOUR FILES (INCLUDING YOUR LOG FILE) AT THE END OF ANY SESSION WHERE YOU WRITE OR DEBUG CODE, AND AT LEAST ONCE EVERY HOUR DURING LONGER SESSIONS. (All submissions are retained.) Notes ~~~~~ 1. Each command-line argument specifying a flag must be one of the strings "-opt", "-ff", "-bf", "-ffd", or "-bfd". Each argument specifying the BIN_SIZE or an ITEM_SIZE must be a string that is a sequence of digits. 2. If any requirement listed above is violated, Binpack prints a one-line message and exits immediately. The content of the message is unimportant; all that matters is that it contain exactly one newline character. 3. The general form of backtracking for this problem is something like: int bp (...) { if the partial assignment has placed every item in some bin return the number of bins used for each bin where the next item can be placed (including one empty bin) place the item in that bin call bp() recursively with the extended partial assignment to find the minimum number of bins needed to place all of the items given that the items already placed cannot be moved remove the item from the bin return the minimum number of bins found by any of the recursive calls } 4. To reduce the amount of backtracking required to find the optimal solution, Binpack uses the following heuristics: A. Presort the item sizes in non-increasing order. B. Compute a lower bound on the number of bins by summing the item sizes, dividing by the capacity, and rounding up if the result is not a whole number; and quit when an assignment using that number of bins is found. C. Keep track of the smallest number of bins found previously (initially this is just the number of items) and do not consider any partial assignment that would use at least as many bins. D. If the next item is the same size as an item that has already been placed in a bin by the partial assignment, skip placing the next item in any bin with a lower number. Rationale: If there are two items of the same size, and you have already tried placing the first in bin I and the second in bin J for some I < J, then you cannot get a better result by placing the first in bin J and the second in bin I. E. If two bins have the same amount of room remaining, skip placing the next item in the higher-numbered bin. Rationale: If bins I and J for some I < J have the same amount of room remaining, and you have already tried placing the next item in bin I, then you cannot get a better result by placing it in bin J. Heuristics D and E will be worth at most 5 points each. In addition, since tests requiring more than one of these heuristics count toward both limits, the penalty for not implementing either of them will be at most 8 points. 5. You may implement the sorting algorithm of your choice since efficiency should be irrelevant for the number of bins used in the tests; but you must start from scratch. In the unlikely event that you do not know ANY algorithm for sorting, you may read about one in a book or on-line, but then the Gilligan's Island Rule applies. 6. The only new C constructs needed for this assignment are * command-line arguments * strcmp() (for identifying command-line arguments) * arrays (for holding item sizes, assignments to bins, etc.); C99 allows the size of an array to be any expression, not just a constant as in K&R C * recursion (for implementing backtracking) You may NOT use structs, pointers, or pointer notation (other than the declaration of the arguments to main()). 7. The source for /c/cs223/Hwk2/Binpack is ~170 lines (~100 lines ignoring comments, blank lines, and brace-only lines). There are also two other, instrumented versions: * Hwk2/BinpackI prints the total number of backtracks used by -opt * Hwk2/BinpackX prints the sequence of placements/removals of items in/from bins and the number of backtracks used by -opt In addition, both versions accept the flags -optA Use backtracking without heuristic A -optB Use backtracking without heuristic B -optC Use backtracking without heuristic C -optD Use backtracking without heuristic D -optE Use backtracking without heuristic E -optBC Use backtracking without heuristics B and C ... -optBCDE Use backtracking without heuristics B, C, D, and E so that you can gauge the effect of the heuristics. 8. The public test script will be /c/cs223/Hwk2/test.Binpack. To run it, type % /c/cs223/Hwk2/test.Binpack The script runs the command % make Binpack to create the executable Binpack. It then runs each test, capturing the output in a temporary file and comparing it with the file containing the expected output. If the two outputs are identical, the test is passed. The command % /c/cs223/Hwk1/test.Binpack 02 03 05 runs only Tests #02, #03, and #05 (you may specify any set of tests here). The command % /c/cs223/Hwk1/Tests/t01 | cmp - /c/cs223/Hwk1/Tests/t01.B and the command % /c/cs223/Hwk1/Tests/t01 | diff - /c/cs223/Hwk1/Tests/t01.B run Test #01 using your Binpack and compare the output with what is expected. Here /c/cs223/Hwk2/Tests/t01 is a shell script (i.e., a sequence of shell commands) that executes your Binpack one or more times; /c/cs223/Hwk1/Tests/t01.B is a text file that contains the expected output; cmp prints the first character where the files differ; and diff prints the lines where they differ but uses a looser definition for "identical". 9. Backtracking will be worth at most 25 points. A. Hints: * Using ceil() to compute the lower bound is more trouble than it's worth. * You do not need to output where each item is placed. B. Point to Ponder: How large can the ratio of N(ff)/N(opt) be? NN(bf)/N(opt)? N(ffd)/N(opt)? N(bfd)/N(opt)? C. Reading Kernighan & Ritchie, Chapters 2, 3, 4; Section B2 Kernighan & Ritchie, Section 5.10 (command-line arguments) CS-223-01/29/20