CS 136 - Summer 2020 - Assignment 2

Due Date: Friday, June 5, 2020 at 9:00 pm Sunday, June 7, 2020 at 9:00 pm.


In this assignment, you must only use the C features covered in class up to Section 04 – slide 52.

In this assignment, you must use iteration (loops), i.e., you may not use recursion. The only exception is q2a-recursion.

No int in any of the questions or your tests can exceed +/- 2,147,483,647. None of our private tests will intentionally cause an integer overflow.

Question 1: printf("Madness\n")

[15 marks correctness]

This question involves printing out patterns using iteration.

Review the provided sample.expect files to see how each shape is drawn. Remember, only print newlines after each line of your output: you must not print any "extra" (double) newlines.

BLACK QUESTION (moderate collaboration allowed)

  1. [q1a-xbox]: xbox(width, height) draws a box with a given width and height and draws an 'X' in its centre.

GOLD QUESTION (no collaboration allowed)

  1. [q1b-saturn]: saturn(diameter) draws a solid, filled circle with a ring in its centre. The circle is filled with '*'; the outside of the circle is empty (' '). The ring is three characters tall; the outer characters of the ring are '=', the inner characters '#'. There are several algorithms to determine if a point lies on the inside or the outside of a circle; we recommend using the Midpoint circle algorithm.


[5 BONUS marks]
  1. [q1c-cube]: cube(dimension) draws a perspective cube with dimension as its width and height, and dimension / 2 (rounded up) as depth.

Question 2: Recursion versus Iteration

[20 marks correctness]

BLACK QUESTION (moderate collaboration allowed)

my_pow(b, e) returns b to the power of e.

count_digits(n) returns the number of digits in n, for example, 1234 => 4.

sum_digits(n) returns the sum of all digits in n, for example, 1234 => 1 + 2 + 3 + 4 = 10.

is_prime(n) returns true if n is prime, and false otherwise. The Sieve of Eratosthenes is a simple and easy to implement primality test.

  1. [q2a-recursion]: Implement all four functions (my_pow, count_digits, sum_digits, and is_prime). You must use recursive algorithms; you may not use any iterations (loops)!
  2. [q2b-iteration]: Implement all four functions (my_pow, count_digits, sum_digits, and is_prime). In addition, also implement fibonacci, a function that calculates the Fibonacci Number (see Assignment 1). You must use iterative algorithms (loops); you may not use any recursion!

Question 3: Reading input (iteratively)

[20 marks correctness]

Benford's Law states that in many naturally occurring collections of numbers, smaller digits (e.g., 1) appear more often as leading significant digits compared to larger digits (e.g., 9). We think this law is cool because it models many naturally occurring phenomena, especially those that follow an exponential growth pattern (populations, for example). We will get back to Benford's Law later.

BLACK QUESTION (moderate collaboration allowed)

Histrograms are a particular type of visualization for distributions, frequently used in descriptive statistics. They mostly presented as a bar-chart: on the x-axis, you have an arbitrary number of categories (oftentimes called "bins" or "buckets"); on the y-axis, you have the count (or tally) of values in each category.

  1. [q3a-histogram]: Implement the function draw_hist(..). This function draws a histogram for exactly ten categories. The bar for each category is one character wide ('#'), and there is a one-character gap between each bar as well as between the y-axis and the first bar (' '). The histogram also has numbers along the y-axis every 5 units; use the following statement to print the number and the y-axis: printf("%2d |", ...). (The printf-command "%2d" instructs printf to print the digit with at least two characters, which makes formatting easier. You can assume that no count in any category will exceed 99.) The x-axis is made of dashes (-); the labels on the x-axis, which represent the 10 categories, are the integers 0 ... 9. Make sure to analyze single.expect to learn more about the output format.

GOLD QUESTION (no collaboration allowed)

Now, let's get back to Benford's Law:

  1. [q3a-benford]: Write a program that reads an arbitrary number of integers from input, counts the occurrences of the integers 1 ... 9 as leading significant digits, and prints out these counts in the form of a histogram.

If you think about Benford's Law, it make sense why it holds true for the leading significant digits of a series of numbers. But does it also hold true if you look at all digits in a series of numbers? For example, in the two numbers 38014184 and 14711827 (population of Canada and Ontario) the digits 0, 2, and 3 appears once, the digit 7 twice, the digits 4 and 8 thrice, and the digit 1 five times.

  1. [q3c-benford-reanalyzed]: Write a program that reads an arbitrary number of integers from input, counts the occurrences of the integers 0 ... 9 within these numbers, and prints out these counts in the form of a histogram.


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

Question 4: Look and Say

[20 marks correctness]

GOLD QUESTION (no collaboration allowed)

The look-and-say sequence is a fun sequence of numbers where every number is generated by counting the number of unique digits of each kind in the previous number. We adopt one of a few variations of this sequence. Please pay attention to how we define our sequence below.

In the example below, our look-and-say sequence beginning with the seed 1:

1, 11, 21, 1112, 3112, 211213, 312213, 212223, 114213, 31121314, 41122314, ...

To generate a member of the sequence from the previous member, read off each unique digit in the previous member from 0 to 9, counting the total number of times the digit appears in the previous member.

For example, suppose that a member in the sequence is 1112. We will generate the next member in the sequence as follows.

In "1112", we check for any occurence of "0". Since there is no "0", we move on to "1". There are three "1" in "1112", and we can read this off as "three 1". Next, there is one "2", which we can read off as "one 2". Last, there are no digits between "3" and "9" in "1112", so we ignore these digits. This leaves us with "three 1" and "one 2", which becomes "3112".

Going through the sequence above results in:

For this assignment question write a program that reads exactly two integers, seed and n, from input and prints out the first n members of the look-and-say sequence starting with the number seed. Use printf("%d\n", ...); to print each member. If any of the errors below occurs, print out the error message "Invalid inputs.\n" and exit.


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

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.