# CS 136 – Fall 2020 – Assignment 1

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

• Before every assignment, make sure you read the updated preamble.
• Monitor the OFFICIAL A1 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 02.
• 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).

### Question 1: Integer Arithmetic

[20 marks correctness]

As you have learnt, integer division in C shows behaviour that is different from "traditional" arithmetic division in Mathematics. Most notably, integer division in C always ignores the remainder. There are use cases, however, when the logic of your program requires the remainder to be considered, for example, when rounding to the nearest integer. In these cases, you may have to implement your own divide-functions to reflect the desired behaviour.

## BLACK QUESTION (moderate collaboration allowed)

1. [q1a-division] Implement `div_towards(dividend, divisor)` and `div_away(dividend, divisor)`. Both functions return the quotient 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. [q1b-rounding] Implement `div_round(dividend, divisor)`. The function returns the quotient of `dividend` over `divisor` as an integer. `div_round` rounds toward the nearest 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`.

Suggestions & Hints:

• For each of the two sub-question, check the `main` function in `main.c` for some examples on how to use `div_towards`, `div_away`, and `div_round` and some expected values.
• Make sure to test your implementations thoroughly.
• Do not forget to write documentation for all functions and remember the required components of the documentation.

For both sub-questions, the public tests will be identical to the assertions provided in each respective `main` function.

### Question 2: Binary Arithmetic and Integrated Circuitry

[25 marks correctness]

In this question, we will explore the connection between computer science and electrical engineering.

On the hardware side, the foundation of every computing device is an integrated circuit. Embedded in these "microchips" are electric circuits consisting of billions of transistors, which are grouped together to form gates. (We don't expect you to read, let alone understand the links above. Nonetheless, we wanted to share them with you because they contain some really neat foundational information.) Now, these gates are important for this question because gates implement operators in Boolean algebra (which finally brings us back to a topic we are all familiar with!).

Overall, there are seven common types of gates: the three basic gates, AND, OR, and NOT, and four secondary gates, NAND (Not AND), NOR (Not OR), XOR (eXclusive OR), and XNOR (eXclusive Not OR). The last four gates are called secondary because they can be expressed using a combination of the three basic gates.

## BLACK QUESTIONS (moderate collaboration allowed)

1. [q2a-gates] Implement the functions for the three basic gates, AND, OR, and NOT, and the functions for the four secondary gates, NAND, NOR, XOR, and XNOR. You may not use any built-in logical operators, i.e., `&&`, `||`, and `!` and you may not use any conditionals, e.g., `if`-statements. Instead, you should use arithmetic and comparison operators (for example, `+`, `*`, `<`, `!=`, and so on) to achieve the same behaviour.

Suggestions & Hints:

• Be aware that the parameters in all functions are of type `int`, not `bool`.
[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 02; it just requires a particularly clever application of your existing knowledge.

One fascinating properties of some of the gates is that they can implemented all other gates. In [q2a-gates] we saw that all secondary gates can be implemented using basic gates only. In the real world, all logic gates are oftentimes implemented using NAND-gates (or NOR-gates) only. This is called NAND logic (or NOR logic respectively). Using only a single gate type has certain advantages in terms of production cost and performance, but we will leave more details to the electrical engineers. In this bones question, you must implement the three basic gates using IMPLY-gate only.

Please refer to the truth table of the Boolean Implication (→) function below:

pq
FFT
FTT
TFF
TTT

For your convenience, we have already implemented `IMPLY`: feel free to use it in your program, and see the `main`-function for usage examples. In your implementation, you may only use the functions `IMPLY` (and `assert` for testing). You may not use any other function!

1. [q2b-implications] Implement `AND`, `OR`, and `NOT` using the `IMPLY` function.

For sub-question a., the public test will be identical to the assertions provided in the `main` function; for sub-question c., the public test will only ensure that your program compiles.

### Question 3: Recursion in C

[25 marks correctness]

Whenever algorithms are (mathematically) defined recursively, they can be directly transformed into a recursive C implementation. Remember that you may not use any loops in Assignment 1.

## BLACK QUESTION (moderate collaboration allowed)

1. [q3a-gcd] Implement `gcd(a, b)`. The function returns the greatest common divisor (GCD) of `a` and `b`.

## GOLD QUESTION (no collaboration allowed)

1. [q3b-fibonacci] Implement `fibonacci(n)`. The function returns the n-th Fibonacci-number, starting at `F(0) = 0`.

Suggestions & Hints:

• When testing, use sensible values for `n`, maybe below 40. Otherwise, your program might not finish before the forced timeout (`Program finished with exit code 255 (Timeout).`). This has something to do with memory management of function calls, which we will explore in Section 04. Stay tuned!)

For both sub-questions, the public test will be identical to the assertions provided in each `main` function.

### Question 4: Testing and Documentation

[10 marks completeness]

Testing your code thoroughly and documenting it are crucial parts of software development. Unfortunately, many programmers see these tasks as tedious and mundane: you just finished your project, why spend more time writing tests if the code already works, why spend more time documenting something that you know intimately? We understand your desire to move on, we are all on a tight schedule: we all have been there.

We, however, have learnt the hard way that both testing and documentation can save time in the long run. Here is an anecdote from the time I was a (Ph.D.) student: I was working on a project that processed camera input from a smart phone and performed some non-standard computations on the collected data (if you are curious: spatial analysis of a video stream using a series of non-standard Fourier transforms). It took me about three months to write the software (if you are curious: C++ and OpenCV), tune all parameters, and run extensive tests to verify that the computations were correct. After this, I handed the code over to a colleague. He came back after about half a year, telling me that the system did not work. Turns out that he was using a different phone with a different image sensor, which interfered with the data processing. As a result, the system had to be re-tuned. This could have been done in maybe two to three days. Unfortunately, I did not document any of the tuning-variables in my code. Because of this, I had to go through and make sense of whatever notes I could find from half a year ago in order to reconstruct the equations I used to calculate all parameters previously. It took about one month to do so. Believe me, it was not the time spent that frustrated me but the knowledge that I could have been done in a few days and that it was entire my fault that I was not.

## BLACK QUESTION (moderate collaboration allowed)

1. [q4a-documentation] Write documentation for the functions `bar` and `bat`. For `bar`, complete the purpose statement and the requires section, for `bat` complete the requires section. Remember to assert all requires statements!

## GOLD QUESTION (no collaboration allowed)

1. [q4b-assertion-tests] Write assertion-tests for the function `foo`. Analyze the function to assure that your tests cover all edge-cases. The `main`-function already contains one sample test for reference.
2. [q4c-io-tests] Write IO-tests for the function `foo`. Analyze the function to assure that your tests cover all edge-cases. The file `basic.in` and basic`.expect` already contain one sample test for reference (the same test as in [q4b-assertion-tests]. In `basic.in`, each row contains one test, and each test consists of three integers (which will be used as the parameters `a`, `b`, and `c` when calling `foo`). Likewise in `basic.expect`, each row contains one test result. You may either create a new IO-test files or add your test to the existing `basic`-test.

Since you are not implementing new functionality, the basic test for all three sub-questions will simply indicate if your code compiles.

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