CS 136 – Fall 2020 – Assignment 3

Due Date: Friday, October 2, 2020 at 9:00 pm.


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-tetromino]: The building blocks of Tetris are called Tetromions. While there are five basic tetrominos, we are only interested in "T-tetromino", the one that is shaped like a "T". Implement tetromino(scale, orientation). This function prints out the T-tetromino. The orientation up indicates that the T-tetromino is printed with the bar up (like the regular letter "T") and down indicates that the T-tetromino is printed with the bar down (like an upside-down letter "T"). scale indicates the size of the printout: a value of 1 means that the T-tetromino is printed with 'X'-characters on a 3 x 2 grid:
    Larger values mean that the printout is larger by a factor of 2, 3, and so on (see simple.expect for an example).

GOLD QUESTION (no collaboration allowed)

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


[5 BONUS marks]
  1. [q1c-gamecube]: 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, 123 => 3.

sum_digits(n) returns the sum of all digits in n, for example, 123 => 1 + 2 + 3 = 6 and -99 => 9 + 9 = 18.

is_prime(n) returns true if n is prime, and false otherwise. While there are several algorithms to test for primality, many efficient ones (e.g., the Sieve of Eratosthenes) require some sort of data storage that we have not taught you (yet). As a result, you may implement a simpler, yet less efficient algorithm.

  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]

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

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)

  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 |", ...). To help with formatting, you may 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. [q3b-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.


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

Question 4: Computer Dating

[30 marks correctness]

What day of the week were you born? Sometimes people get asked this question, and, while most remember their day of birth, we oftentimes do not memorize our "day-of-the-week of birth". Let's write a program that can help us answering this question! First, let's agree on a calendar. While almost each culture has established their own version of calendars, at varying levels of similarity, most of the world has settled on the Gregorian Calendar today, which we will be using in this assignment question. The Gregorian Calendar was codified in 1582 as an improvement over the Julian Calendar. (There are some hilarious conspiracy theories around this transition.) For this question, we will only consider dates from 1589 onward.

When making calculations including a calendar, we again have to set some ground rules. Normally in Computer Science we start counting at 0, but it is awkward to assign 0 to the month January; similarly, the first day of the month starts at 1 and not 0. As a result, the number for January will be 1 and December will be 12. There is, however, no convention for assigning days of the week to numbers, so we will assign Sunday to be 0, Monday to be 1, and Saturday to be 6. This will also make your calculations slightly more straightforward.

For this question, it is okay to have "magic numbers" in your code. For example, you do not have to define constants like number_of_days_in_march.

GOLD QUESTION (no collaboration allowed)

Complete the following functions:


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

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.