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

- Before every assignment, make sure you read the
**updated**preamble. - Monitor the OFFICIAL A3 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.

- In this assignment, you
**may only use**the C features covered in notes up to the end of Section 04. - To avoid any possible issues with stack overflow, you
**may not use**recursion. - No
`int`

in any of the questions or your tests can exceed`± 2,147,483,647`

. None of our secret tests will intentionally cause an integer overflow.

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.

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

Larger values mean that the printout is larger by a factor of 2, 3, and so on (see`simple.expect`

for an example).

- [q1b-xbox]:
`xbox(width, height)`

draws a box with a given width and height and draws an`'X'`

in its centre.

**Hints:**

- Remember that you do not necessarily have to initialize loop variables with 0 or 1!

- [q1c-gamecube]:
`cube(dimension)`

draws a perspective cube with`dimension`

as its width and height, and`dimension / 2`

(rounded up) as depth.

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

- [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)! - [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!

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.

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

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

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

**Hints:**

- You may use our provided
`draw_hist`

-function. Alternatively, you may copy and paste your`draw_hist`

-function from part (a) into part (b). In this case, comment out the line`#include "hist.h"`

. - Make sure to use a divide-and-conquer approach: break down the problem into multiple parts and solve them separately.
- Make sure to avoid code redundancies, i.e., having the same code multiple times. Instead use helper functions!
- In part (b), you only have 9 categories to print (
`1 ... 9`

), although`>draw_hist`

requires 10 parameters (`c_0 ... c_9`

). Simply set the parameter`c_0`

to`0`

! - Remember that you may not use global mutable variables. This means that you have to store your tallies for
`0 ... 9`

in one of the functions, probably in`main`

. (There is a much better solution using arrays, which we will learn about later.) This also means that you maybe have to be a little bit "clever" when analyzing an integer. Remember that it is okay (for now) to write inefficient code.

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

.

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`

.

Complete the following functions:

`is_leap_year(year)`

determines if the year is a leap year, according to the Gregorian Calendar. Every year that is exactly divisible by four is a leap year, except for years that are exactly divisible by 100, but these centurial years are leap years if they are exactly divisible by 400.`days_in_month(year, month)`

returns the number of days in the corresponding month.`day_of_the_week(year, month, day)`

finds the "day of the week" for the given date. To determine this, you must start in`1589`

and then loop month-by-month, adding the number of days in each month until you arrive at the month in the date. Remember, Sunday is`0`

. This assignment is due on`day_of_the_week(2020, 10, 2) => 5`

(Friday). There are alternate "clever" ways to solve this problem, but you are not allowed to use those approaches.`print_calendar(year, month)`

prints a "pretty" calendar for the given month. For example,`print_calendar(2020, 1)`

prints the following output:====January 2020==== Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

We have provided a function`print_header`

to print the header (i.e., the first two lines). The header starts with Sunday (`Su`

). Your task is to properly align the dates in the calendar. To print an integer so it occupies two spaces, use the format string`"%2d"`

. Note that there are no additional spaces after the`31`

.

**Hints:**

- Be careful using online calendar generators to develop test cases to test your code. Unfortunately, we have noticed many online calendar generators are incorrect for calendars many years in the past. Google seems to be correct. You are probably best off testing with recent years, which are easily verifiable.

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

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.