CS 136 - Summer 2020 - Assignment 1

Due Date: Friday, May 29th, 2020 at 9:00 pm Sunday, May 31, 2020 at 9:00 pm Monday, June 1, 2020 at 9:00 pm Tuesday, June 2, 2020 at 9:00 pm.


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 (we will learn more about this later).

BLACK QUESTION (moderate collaboration allowed)

Question 1: Using printf

[10 marks correctness]

You must write a program in main.c that prints the text below 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.

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.

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

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!

GOLD QUESTION (no collaboration allowed)

Question 2: Manipulating State

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

This assignment making cookies. A cookie bakery consumes dough and chocolate chips as ingredients and uses them to bake cookies. Both dough and chips are added into a bowl; once the desired amounts of both ingredients are in the bowl, they can bake one cookie!

A cookie is made of at least 10 units of dough, and at most 30. (If a cookie is too small, it's not really worth baking it; if it is too big, it will break too easily and make a mess.) The ratio between chocolate chips and dough must be between 1:4 (20% chips, 80% dough) and 1:2 (one third chips, two thirds dough). (If there are not enough chips, the cookie is not chocolat-y enough; if there are too many, you might experience a chocolate-overload.)

You must complete the program main.c that simulates the operation of a bakery, using these six functions:

We have built an interactive I/O suite that reads "commands" in plain text from input, and then calls the appropriate functions in your main.c file. This allows you to interactively test your code from input. Check bakery.h for an overview of all available commands and simple.in and ratios.in for examples. For now, we have intentionally hidden the code of this interactive function from you.

For this question, the Marmoset basic tests ("public" tests) will be the same as the basic I/O test.


Question 3: Integer Arithmetic

[10 marks correctness]


For questions a. through c., the public test will be identical to the assertions provided in each respective main function; for d., the public test will only insure that your program compiles.

BLACK QUESTION (moderate collaboration allowed)

  1. Implement div_towards(dividend, divisor) and div_away(dividend, divisor). Both functions return the division of dividend over divisor as an integer. div_towards rounds towards 0 and div_away rounds away from 0.

GOLD QUESTION (no collaboration allowed)

  1. Implement div_round((dividend, divisor)). The function returns the division of dividend over divisor as an integer. div_round rounds toward the closest integer; in case of a tie (e.g., 5 / 2 = 2.5, which is equally close to both 2 and 3), it rounds away from 0.
  2. Implement fibonacci(n). This function calculates and returns the Fibonacci number of n.
[5 BONUS marks]

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.

  1. Implement fibonacci_print(n). This function displays all Fibonacci numbers from F0 to Fn. There should be one Fibonacci number per line, e.g., F(2) = 1 for F2. The output should start with F0. See example.expect for an example.

Question 4: 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 introduce you to some of the features of C and Seashell 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. Other operations allow one to determine the top element of the stack (top), find out if the stack is empty (is_empty), and so on (more details below). The image below illustrates some standard behaviour of a stack:

In this question you will be using different testing techniques to test whether an implementation is correct or not. The implementation you are given and the one used for public tests will be correct. Some of the stack-implementations used in private 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. 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)

Assess functional correctness using I/O testing

We have provided you with an I/O-based testing client (test_io.c). 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 based testing client allows you to place a sequence of stack operations in an .in-files. 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-files. Note that all I/O tests are independent from each other.

The commands available in the I/O-based 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.)

Since there is no .c-file for you to modify, we have provided an integrity.txt file, where you must complete your integrity statement.

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

Assess functions correctness using assertion-based testing

We have provided you with a basic assert-based testing client (test_assertion.c). Add more assertion-based 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. You can assume that

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


BLACK QUESTION (moderate collaboration allowed)

Question 5: Style

[20 marks style]

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.