# CS 136 – Fall 2020 – Assignment 2

Due Date: Friday, September 25, 2020 at 9:00 pm.

• Before every assignment, make sure you read the updated preamble.
• Monitor the OFFICIAL A2 Piazza Post for any corrections, updates, or frequently asked questions.
• The assignment files are available here (they are also provided in Seashell).
• The questions are listed in (approximate) course chronological order, not necessarily in order of their difficulty or the amount of effort required.

## LANGUAGE FEATURES

• In this assignment, you may only use the C features covered in notes up to the end of Section 03.
• More explicitly, you must use recursion, i.e., you may not use loops.
• No `int` in any of the questions or your tests can exceed `± 2,147,483,647` and none of our secret tests will intentionally do so (we will learn more about this later).

### Question 1: Imperialism

[10 marks correctness]

The Imperial and US customary measurement systems is a pre-industrial system of measurements for lengths, areas, volumes, and weights. While most countries have adopted the Metric system in lieu of any historic measurement system, we are still confronted with imperial units, so it is still useful to know how they work!

The following text decribes the relationship between several length-related imperial units:

```You take three barley corns, that gives you an "inch".
You then take 12 in, that gives you a "foot".
You take three ft, and it gives you a "yard".
If you take 1,760 yd, you get a "standard mile".

If you take 12.5% of a mi, you have a "furlong".
These fur you can divide into tenths and you get a "Gunter's Chain".
Each ch, you can split into 11, and you get a "fathom".

If you take 100 ftm, you get a "cable".
You can take ten cb and you get a "nautical mile";
a nmi of course being wildly different from a mi:
while the nmi is 72,960 in, the standard mile is exactly 63,360.

What a fantastically logical and consistent system of units!

Don't forget to put a newline (\n) after each line!
```

## BLACK QUESTION (moderate collaboration allowed)

[q1-imperialism] Implement a program in `main.c` that prints the text above exactly. Be aware that you may not use any numbers directly inside of your strings (inside of the quotes); instead, you must use `%d`. Review the notes for how to print special characters, such as, `\`, `"`, and `%`. Don't forget to put a newline (`\n`) at the end of every line, including the last line.

The text can also be found in `simple.expect` provided in Seashell. You can use the I/O Test to test your solution.

For this question, the Marmoset basic tests ("public" tests) will be identical to the simple test file provided. There will be no additional tests, except to ensure you have not violated the restrictions on printing numbers.

### Question 2: Testing with Stacks

[20 marks correctness]

When developing software, an important skill to learn is the discipline to implement and repeatedly use good tests. These questions are designed to recapitulate some of the features of C and Seashell from [A01 – q4] that can help you to perform testing. Please remember to use these techniques in all of your assignments.

In this question, you have to test the correctness of a stack-implementation. A stack is an abstract data type that provides a collection of elements with two principle operations:

• push adds an element onto the top of the stack.
• pop removes an element from the top of the stack.

The order that elements come off of the stack is the reverse order in which they were pushed. The name stack comes from a set of physical items stacked on top of one another, such as, a stack of books on your desk. Other operations allow one to determine the top element of the stack (top) or find out if the stack is empty (is_empty). The image below illustrates some standard stack behaviours:

In this question you will be using two different testing techniques to test whether an implementation of a stack is correct or not: assertion-testing and I/O-testing. The stack-implementation you are given and the one used for public tests will be correct. Some of the stack-implementations used in our secret tests, however, may not be correct.

Your task is to write a series of tests that allow you to distinguish between correct and incorrect stack-implementations. Ideally, your test will assess every aspect of the stack-implementation and, since the stack implementation is correct, all tests will pass. When run with an incorrect implementation, however, your tests should fail, thus exposing all incorrect implementations. Note that it is sufficient for the tests that you write for this question to trigger bugs; you do not have to determine or explain precisely what the bug is.

Hints:

• We have provided a working example in [q2-example] that illustrates how assertion-testing and I/O-testing work. Make sure you fully understand how this program uses global state and interacts with the `.in`-files (use the I/O Test button in Seashell) before you start solving this assignment question. Check `iotest_driver.h` for the input syntax.

## BLACK QUESTION (moderate collaboration allowed)

### [q2a-assertion-testing] Assess functional correctness using assertion-testing

We have provided you with a basic assert-testing client. Add more assertion-tests to the `main`-function, so that these tests are capable of determining if a stack-implementation is correct or not.

The complete interface for the stack implementation is provided for you in `stack.h`. Be sure to review that interface for more details of how a stack operates and all of the functions you need to test.

Do not remove the calls to `stack_create` and `stack_destroy` from the beginning / end of the `main`-function. We guarantee that these functions will always be implemented correctly: there is no need for testing these functions. We will explore the purpose of these functions later.

For this question, the public test will be identical to the assertions provided in the `main`-function.

Hints:

• This program will use only assertion testing so you should run it using the [RUN] button. You should not test this program using the [I/O Test].

### [q2b-io-testing] Assess functional correctness using I/O-testing

We have provided you with an I/O-testing client. It interacts with the stack through the Seashell I/O testing framework and `iotest_driver`. It thus allows you to test all stack functions (except `stack_create` and `stack_destroy`: you can assume that they are implemented correctly).

The I/O-testing client allows you to place a sequence of stack operations in an `.in`-file. The I/O Test will then execute these operations on the stack and compare their output with the desired output provided in the corresponding `.expect`-file. Note that all I/O tests are independent from each other.

The commands available in the I/O-testing client are listed in `iotest_driver.h`

See `simple.in` and `simple.expect` for an example on how write your own I/O tests. Remember that this is a basic test only; you must create more thorough tests to determine if there are bugs in the stack-implementation or not.

All your tests must be in the files `mytest.in` and `mytest.expect`. Do not create any other test files! (This is a limitation of Marmoset.)

For this question, the public test will be identical to the one provided in `simple.in`.

Hints:

• There is no add any code to `main.c`, but you must complete the Integrity Statement!

### Question 3: State Manipulation

[30 marks correctness]

In this question,you need to implement a workshop that assembles server barebones. To assemble one (1) server barebone, you need six (6) memory modules and two (2) CPUs from your inventory. A standard order of server barebones contains ten (10) units. This workshop requires several core functions to operate properly:

• `add_memory` adds memory modules to the inventory
• `add_cpus` adds CPUs to the inventory
• `assemble_barebones` assembles barebones using memory modules and CPUs from the inventory
• `deliver_barebones` deliveres a standard order and starts a new standard order
• `special_order` changes a standard order to a special order by changing the number of barebones to assemble

Your workshop implementation needs to keep track of certain information, for example, the current inventory and the number of barebones already assembled. This information has to be available throughout the entire program. There are multiple methods for achieving this, such as, global variables, passing stack memory structures, or pointers to heap memory. For now, you have to rely on global variables, which is the least elegant solution as it introduces more opportunities for side effects. (Later in this term, you will learn and use more elegenat solutions, and we might even revisit this assignment question.)

You also need the ability to issue commands to your workshop. One quite elegant solution is listing commands and parameters, if required, in a `.in`-file and then reading these commands and translating them into calls to the core-functions of your workshop. In this assignment, we have already taken care of the second part. It is your responsibility, however, to implement the core-functions and to come up with more `.in`-files to test your core functions extensively. The file `workshop.h` lists all available commands, and `simple.in` demonstrates one possible sequence of commands issued to the workshop.

Besides writing syntactically correct code, i.e., code that compiles, and semantically correct code, i.e., code that does what it is sopposed to do, we also expect you to write "good-looking"code, i.e., code that complies with out style guide.

## GOLD QUESTION (no collaboration allowed)

##### LANGUAGE FEATURES: For [only] this question, you may use global mutable variables.

Implement, test, and document all workshop functions:

• `add_memory(amount)` adds `amount` memory modules to the inventory and prints a success-message. If `amount` is non-positive, the function outputs an error-message and makes no changes to the inventory.
• `add_cpus(amount)` adds `amount` CPUs to the inventory and prints a success-message. If `amount` is non-positive, fhe function outputs an error-message and makes no changes to the inventory.
• `assemble_barebones()` assembles as many barebone servers as needed to fulfill the order or as many barebones as possible given the current inventory of memory modules and CPUs. The function outputs several messages indicating the result of the assembly-process. Please refer to the following figure (techincally a UML Activity diagram) to learn about the output-behaviour of the function. Also, refer to the `printf`-format strings.

• `deliver_barebones()` completes the current order and starts the next one if enough barebones have indeed be assembled. This is achieve by resetting the number of already assembled barebones. A messages indicates the success of the delivery.
• `special_order(order_size)` changes the amount of barebones of the current order to `order_size`. The new order size must be positive and cannot be smaller than the number of barebones already assembled. The function outputs an error if `order_size` is not positive or a different error if too many barebones have already been assembled.
• `reset_workshop()` sets the current order size to the default order size, the inventory to 0, and the number of assembled barebones to 0 as well.
• `display_status()` outputs details about the inventory and the current order. The order of output must be (1) memory modules, (2) CPUs, (3) order status.

Suggestions & Hints:

• We have listed the `printf`-format strings in all functions.

For this question, the Marmoset basic tests ("public" tests) will be the same as the one in `simple.in`.

### Question 4: Statistically...

[20 marks correctness]

Statistics offers us powerful mathematical tools to make sense of the world around us. While statistical methods come in all shapes and levels of complexity, even basic statistics can be useful. The most basic statistics that we can run on data is called descriptive statistics (or, in short: "descriptives"). Descriptives usually include:

Some of these descriptives are quite easy to find, such as Maximum, others have to be calculated, such as, Mean, which is derived from the sum of all samples devided by the sample size. Some of these descriptives can be found while reading in the sample data, such as Maximum and Mean, others can only be found when going through the data a second time, such as Standard Deviation. Finally, there are some descriptives, for example, Median and Mode, that require more in-depth data processing, such as, sorting data or transforming it into a histrogram (more about histograms in A03). Since you are just starting to program in C, the programming techniques that you can use are still somehow limited. For example, you can only read a value once from input using `read_int` and you cannot store values in an array or a list (yet).

In order to avoid problems in your code execution, limit the Sample size of your data to 10 or lower. Also, limit the absolute value of your samples to 10. We will do the same in your secret tests. You may also assume that there will be at least one sample in any test; your implementation does not have to work for empty input.

## BLACK QUESTION (moderate collaboration allowed)

##### LANGUAGE FEATURES: For [only] this question, you may use global mutable variables.
1. [q4a-STAT101] Implement the function `read_numbers`. The function reads an arbitrary number of integers from input and, after the last integer was read, prints Sample size, Minimum, Maximum, and Range of the read data. Please refer to `sample.expect` for an output example and check the `printf`-strings given in the function. Remember that you may not use any loops in this assignment! This means that you have to rely on recursion for reading an arbitrary number of integers. You also have to pass data between the recursive calls. Currently, you should know two ways to achieve this: accumulative recursion (recall from CS 115 and CS 135) and global variables. You may use whatever method you prefer; keep in mind, however, that you may not change the signature of `read_numbers`. This means that you might have to use helper- or worker-functions.

For this question, the Marmoset basic tests ("public" tests) will be identical to the simple test file provided.

As we have mentioned above, it is impossible to calculate many descriptives without revisiting read values for a second time. There are three ways to achieve this: you can either store the read values somewhere within your program, you can reset the input and read the data a second time, ot you can use recursion. To help you, we have implemented a function `read_and_record_int` that stores the read values, so you can "read" them for a second time. Please refer to `replay.h` for the full documentation. We also have provided links that lay out how to calculate some other descriptives; alternatively, you can use the equations below in your implementation:

Note that Mean uses `N` as divisor, whereas Variance uses `N-1`. This is called Sample Variance (in contrast to Population Variance).

## GOLD QUESTION (no collaboration allowed)

##### LANGUAGE FEATURES: For [only] this question, you may use global mutable variables.
1. [q4b-STAT102] Implement the functions `read_numbers` and `replay_numbers`. The purpose of these functions is to display more descriptives than you could in [q4a-STAT101]. To do so, the two functions have to work together. The implementation of `read_numbers` is likely to be very similar to the one [q4a-STAT101]; feel free to copy your code as a jumping-off point for your implementation. The function `replay_numbers` will likely be responsible for printing out Mean and Variance of the data. Please refer to `sample.expect` for an output example. Be aware that both Mean and Variance have to be calculated and rounded to two decimal places. For example, a Mean of `-1.361` would have to be displayed as `-1.36`, a Variance of `4.375` as `4.38`. Since you are not allowed to use floating point types (i.e., `float` and `double`), you have to work around this problem somehow.
2. For this question, the Marmoset basic tests ("public" tests) will be identical to the simple test file provided.

Hints:

• In your solution, you might have to use integer division (`/`), modulo (`%`), as well as `div_round` from A01.
• The printf-function has a useful feature for formatting number output: by using, for example, `%04d` instead of `%d`, the integer will be printed with at least four digits and leading zeros, if necessary. For example: `printf("%d.%04d", 12, 34);` outputs `12.0034` to the console.
• As awlays, you should calculate the expected test results using something other than your program. (Never ever use the program you want to evaluate for calculating the expected results!) While you can calculate all expected values manually, there are several websites that can potentiall help you with this task, e.g., CalculatorSoup.

## GOLD QUESTION (no collaboration allowed)

[5 BONUS marks]
##### LANGUAGE FEATURES: For [only] this question, you may use global mutable variables.

This is a bonus question. It is intentionally more difficult to implement than any other questions on this assignment, and we are not going to provide any guidance in solving this question. Keep in mind, however, that this question does not require any additional knowledge past Section 03; it just requires a particularly clever application of your existing knowledge.

The Standard Deviation is the square-root of the Variance:

1. [q4c-STAT498] Implement the functions `read_numbers. The purpose of these functions is to display more descriptives than you could in [q4b-STAT102]. Your program now has to also output the Standard Deviation of the read data. We have removed the replay-library, so you have to rely on the read_int-function and recursion alone. Since you are not allowed to use any function in math.h, which includes sqrt, or any floating point types, you probably have to implement your own square root method. A good starting point is the Babylonian method. Please refer to sample.expect for an output example. Be aware that Standard Deviation has to be calculated and rounded to one decimal place. The printed value sd must be the closest one to the actual square root of var, i.e., sd minimizes the error e, where e = |sd2 - var|.`
2. ``` ```
``` For this question, the Marmoset basic tests ("public" tests) test will only ensure that your program compiles. ```
``` Question 5: Style [20 marks style] BLACK QUESTION (moderate collaboration allowed) You don't need to do anything for this question. By having this question, we want to let you know that one or more of the questions on this assignment will be hand-marked for coding style and the quality of your tests. We are not stating which question(s) because you should use proper style and testing on all questions. Suggestions & Hints: Review what type of documentation we require. Give variables and (helper-) functions meaningful names. Don't reinvent the wheel!: use helper-functions to avoid redundant code. "Brevity is the soul of good coding!": most assignment problems can be solved in a dozen lines of code (or so). If you end up writing hundreds of lines of code, your solution is probably too complex and convoluted, and you are probably missing an easier approach. Remember that you can use [CTRL]+[i] ([CMD]+[i] on MacOS) to auto-indent your code. ```