辅导案例-WINTER 2020
ASSIGNMENT #2 CS246, WINTER 2020 Assignment #2 Due Date 1: Friday, 7 February, 2020, 5:00 pm Due Date 2: Friday, 14 February, 2020, 5:00 pm • Questions 1, 2, 3a, 4a, 5a are due on Due Date 1; the remaining questions are due on Due Date 2. • On this and subsequent assignments, you will take responsibility for your own testing. This assignment is designed to get you into the habit of thinking about testing before you start writing your program. If you look at the deliverables and their due dates, you will notice that there is no C++ code due on Due Date 1. Instead, you will be asked to submit test suites for C++ programs that you will later submit by Due Date 2. Test suites will be in a format compatible with A1Q4/5/6. So if you did a good job writing your runSuite script, it will serve you well on this assignment. • Design your test suites with care; they are your primary tool for verifying the correctness of your code. Note that test suite submission zip files are restricted to contain a maximum of 40 tests, and the size of each file is also restricted to 300 bytes; this is to encourage you not combine all of your testing eggs in one basket. • You must use the standard C++ I/O streaming and memory management (MM) facilities on this assignment; you may not use C-style I/O or MM. More concretely, you may #include the following C++ libraries (and no others!) for the current assignment: iostream, fstream, sstream, iomanip, and string. Marmoset will be setup to reject submissions that use C-style I/O or MM, or libraries other than the ones specified above. • We will manually check that you follow a reasonable standard of documentation and style, and to verify any assignment requirements that are not automatically enforced by Marmoset. Code to a standard that you would expect from someone else if you had to maintain their code. Further comments on coding guidelines can be found here: https://www.student.cs.uwaterloo.ca/˜cs246/current/ AssignmentGuidelines.shtml • You may not ask public questions on Piazza about what the programs that make up the assignment are supposed to do. A major part of this assignment involves designing test cases, and questions that ask what the programs should do in one case or another will give away potential test cases to the rest of the class. Questions found in violation of this rule will be marked private or deleted; repeat offences could be subject to discipline. Part 1 Note: there is no coding associated with this problem. We would like to write a program called change, which accepts one command-line argument, an integer (representing an amount of money, in cents). The program then gives the minimal combination of Canadian coins, toonies, loonies, quarters, dimes, nickels, and pennies (yes we know Canada no longer has pennies) whose total value equals the given amount on standard output. For example, if the command-line argument is 89 then the output is 3 quarters 1 dime 4 pennies Your task is not to write this program, but to design a test suite for this program. Your test suite must be such that a correct implementation of this program passes all of your tests, but a buggy implementation will fail at least one of your tests. Marmoset will use a correct implementation and several buggy implementations to evaluate your test suite in the manner just described. Your test suite should take the form described for runSuite in Assignment 1: each test should provide its argument in the file testname.args , and its expected output in the file testname.out. You have been provided with (what we Page 1 of 6 ASSIGNMENT #2 CS246, WINTER 2020 believe to be) a correct implementation of the change program (in compiled format). You may use this executable along with your produceOutputs script from Assignment 1 to generate the testname.out files for the testname.args files that you create. The collection of all testnames should be contained in the file suiteq1.txt. a) Due on Due Date 1: Zip up all of the files that make up your test suite into the file a2q1.zip, and submit to Marmoset. b) Due on Due Date 2: Nothing. Part 2 Note: there is no coding associated with this problem. You are given a non-empty array a[0..n− 1], containing n integers. The program sort sorts the array in descending order by reading the integer values for the array from standard input. The output of the program is a print of the sorted array starting from the largest element, with one element printed per line. For example, if the input is -9 4 5 -1 3 10 then SORT prints 10 5 4 3 -1 -9 Your task is not to write this program, but to design a test suite for this program. Your test suite must be such that a correct implementation of this program passes all of your tests, but a buggy implementation will fail at least one of your tests. Marmoset will use a correct implementation and several buggy implementations to evaluate your test suite in the manner just described. Your test suite should take the form described for runSuite in Assignment 1: each test should provide its input in the file testname.in , and its expected output in the file testname.out. You have been provided with (what we believe to be) a correct implementation of the sort program (in compiled format). You may use this executable along with your produceOutputs script from Assignment 1 to generate the testname.out files for the testname.in files that you create. The collection of all testnames should be contained in the file suiteq2.txt. a) Due on Due Date 1: Zip up all of the files that make up your test suite into the file a2q2.zip, and submit to Marmoset. b) Due on Due Date 2: Nothing. Page 2 of 6 ASSIGNMENT #2 CS246, WINTER 2020 Part 3 This question is almost identical to A1Q3 (where you wrote a bash script named averages). In this question, you will write a C++ program that does almost the same but with some new requirements. Sometimes students in a course must write midterms in different rooms. We would like to know how students perform in different rooms with the hope that room assignment has no effect on their performance. As a first measure, we can obtain the average mark obtained by students in each room. Write a C++ program (called averages in the examples below) that computes and prints the average marks obtained by students in each room. The program is provided a single command-line argument, the name of a file (from here on called the spreadsheet), that contains a line for each student that wrote the midterm. Each line contains three values (separated by a single space): nanaeem DC1350 72 The first value (nanaeem above) is the student’s userid, the second value (DC1350 above) is the room in which they wrote the exam and the third value (72 above) is the mark the student received on the midterm. The following example shows the output produced by the program: $ cat spreadsheet1.txt nanaeem DC1350 72 $ ./averages spreadsheet1.txt Room: DC1350 Number of Students: 1 Average: 72 If the course used multiple rooms for the midterm, i.e., the spreadsheet contains multiple room names, the program produces the output for each room by ordering them using lexicographical sorting on the room names. The following example illustrates this behaviour: $ cat spreadsheet2.txt mrasool MC4020 85 nanaeem DC1350 72 jdoe MC4020 42 j2doe DC1350 84 $ ./averages spreadsheet2.txt Room: DC1350 Number of Students: 2 Average: 78 Room: MC4020 Number of Students: 2 Average: 63 In the example above, note that the output for DC1350 appeared before the output for MC4020 as DC1350 is lexico- graphically ahead of MC4020. Also note the average for MC4020. The students in MC4020 had the marks 85 and 42 for a precise average of (85+42)/2, i.e., 63.5. The program outputs 63, i.e., it rounds down to the nearest integer. We have provided you with some starter code (averages.cc ). Add your code to this file. Be sure to follow the requirements in that starter code. Your code might be hand-marked and not following the instructions will cause you to lose marks. Artificial restrictions to force you to practice previously learned C features and use specific C++ features: • You must only read the spreadsheet file once. • You must use the stack allocated array rooms defined in the main function • You must implement the helper functions according to the provided documentation. You must use these helper functions in your program. Some implementation notes and hints: • In the a2 directory, you will find a program called args.cc, which demonstrates how to access command line argu- ments from a C++ program. You may use any part of that code in solving this problem. • If the program is not called with one argument, your program should print the following message to standard output and exits with a status code of 5. Page 3 of 6 ASSIGNMENT #2 CS246, WINTER 2020 ERROR: Program expects 1 argument. • You may assume that if the one argument is provided, it is a spreadsheet which is available and readable in the current directory and contains text that follows the format stated above, i.e., no error checking is required for the text file. In particular, note that each line in the spreadsheet must have three values, i.e., there cannot be random blank lines in the spreadsheet. • You may assume that adding marks for students to compute averages will never cause overflow. • The main function declares a stack-allocated array for storing Room information (the variable rooms in the main function). This means our program can only accommodate MAX unique rooms (set to 10 in averages.cc). Every time, the program encounters a unique room and there is no space to add this room, the program should print to standard output the following text: Maximum room limit reached. Room XYZ not added. where XYZ is the room that we were trying to add. The program must continue to the next record. • The statistics for individual rooms are printed AFTER all student records have been read. Your program must use the output operator for Room to create this output. See averages.cc for more details. Implementation help: A compiled binary of a correctly implemented solution is provided. You can use it to resolve any ambiguities in the problem requirements as well as generating your test suite. a) Due on Due Date 1: Design a test suite for this program. Call your suite file suiteq3.txt. Zip your suite file, together with any of the associated .in, .out and .args files, into the file a2q3.zip. b) Due on Due Date 2: Write the program in C++. Save your solution in a file named averages.cc. Part 4 Implement a simplified version of the Unix command wc; have a look at the man page, and try it out. Your implementation should be able to take input from either a single file name specified on the command line, or from stdin. You are to support the flags -c, -l, and -w. You may assume (without checking) that: • all input is valid, • each flag appears at most once, and you don’t have to worry about supporting combinations like -wc or -lcw, and • any file named on the command line exists, is readable, and appears after any of the other arguments. Your output may differ from that of the “real” wc with respect to whitespace usage. a) Due on Due Date 1: Design a test suite for this program. Call your suite file suiteq4.txt. Zip your suite file, together with the associated .in, .out, .args and any other text files, into the file a2q4.zip. b) Due on Due Date 2: Write the program in C++. Save your solution in a file named a2q4.cc. Page 4 of 6 ASSIGNMENT #2 CS246, WINTER 2020 Part 5 We typically use arrays to store collections of items (say, booleans). We can allow for limited growth of a collection by allocating more space than typically needed, and then keeping track of how much space was actually used. We can allow for unlimited growth of the array by allocating the array on the heap and resizing as necessary. The following structure simulates binary numbers by encapsulating a partially-filled array: struct BinaryNum { int size; // number of elements the array currently holds int capacity; // number of elements the array could hold, // given current memory allocation to contents bool *contents; // (pointer to) heap-allocated array of bools }; • Write the function readBinaryNum which returns a BinaryNum structure, and whose signature is as follows: BinaryNum readBinaryNum(); The function readBinaryNum consumes as many ones and zeroes from cin as are available, populates a BinaryNum structure in order with these, and then returns the structure. If a non-whitespace character that is not a one or a zero is encountered before the structure is full, then readBinaryNum fills as much of the array as needed, leaving the rest unfilled. If a non one or zero character is encountered, the first offending character should be removed from the input stream. In all circumstances, the field size should accurately represent the number of elements actually stored in the array and capacity should represent the amount of storage currently allocated to the array. • Write the function binaryConcat, which takes a BinaryNum structure by reference whose signature is as follows: void binaryConcat(BinaryNum &binNum); The function binaryConcat concatenates on to the end of the structure passed in as many booleans as are available on cin. The behaviour is identical to readBinaryNum, except that integers are being added to the end of an existing BinaryNum. • Write the function binaryToDecimal, which takes a BinaryNum structure by reference to const and returns an int. The signature is as follows: int binaryToDecimal(const BinaryNum &binNum); The function binaryToDecimal should return the decimal value equivalent of the binary number represented by the given BinaryNum structure. The behaviour of this function is undefined if the decimal equivalent of the binary number exceeds the maximum value that can be stored within an int. • Write the function printBinaryNum, which takes a BinaryNum structure by reference to const and a separator character, and whose signature is as follows: void printBinaryNum(std::ostream &out, const BinaryNum &binNum, char sep); The function printBinaryNum prints the contents of binNum (as many elements as are actually present) to the given stream out, on the same line, separated by characters denoted by sep, and followed by a newline. There should be a separator character between each element in the array, this means there should be none before the first element or after the last element. It is not valid to perform any operations on a BinaryNum that has not first been read, because its fields may not be properly set. You should not test this. Page 5 of 6 ASSIGNMENT #2 CS246, WINTER 2020 • Write the function for the left-shift operator << which takes a left hand operand BinaryNum structure by reference and a right hand operand int. The function returns a reference to the same BinaryNum structure that is passed as an argument. The signature is as follows: BinaryNum &operator<<(BinaryNum &binNum, int num); Assuming binNum is a BinaryNum variable and x is an int, the expression binNum << x (or equivalently operator<<(binNum,x)) will move each bit in binNum exactly x places to the left adding the appropriate number of zeroes onto the end of the number. As an example a BinaryNumber that when printed shows 1011011 if shifted left by 3 will then show 1011011000. For memory allocation, you must follow this allocation scheme: every BinaryNum structure begins with a capacity of 0. The first time data is stored in a BinaryNum structure, it is given a capacity of 4 and space allocated accordingly. If at any point, this capacity proves to be not enough, you must double the capacity (so capacities will go from 4 to 8 to 16 to 32 ...). Note that there is no realloc in C++, so doubling the size of an array necessitates allocating a new array and copying items over. Your program must not leak memory. A header file and test harness are available in the starter files binarynum.h and a2q5.cc, which you will find in your cs246/1201/a2 directory. Make sure you read and understand this test harness, as you will need to know what it does in order to structure your test suite. A sample test case that can be run using the test harness is also provided. Note that we may use a different test harness to evaluate the code you submit on Due Date 2 (if your functions work properly, it should not matter what test harness we use). a) Due on Due Date 1: Design a test suite for this program, using the main function provided in the test harness. Call your suite file suiteq5.txt. Zip your suite file, together with the associated .in and .out files, into the file a2q5.zip. b) Due on Due Date 2: Implement the required functions in the file binarynum.cc. Submit this file, the provided header, the provided test harness, and a Makefile in the file a2q5.zip. Your Makefile must build an executable called a2q5. Page 6 of 6