CS 136 – Fall 2020 – Assignment 1

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


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

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


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:

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.

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: