CS 136 – Fall 2020 – Assignment 2

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


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!

Source: https://www.youtube.com/watch?v=r7x-RGfd0Yk.

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:

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.


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.


[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.


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:

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:

Suggestions & Hints:

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.


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

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: