Exercise 3: Binary, Rectangle, Fibonacci, Prime

This is a programming exercise for you to solve on your own. You can submit but it will not be graded. Test cases are provided for the exercises so that you can test and check on your own if your code is correct. Feel free to discuss your solution with your peers or your TAs.

Prerequisite

You are able to access the CS1010 programming environment.
You are familiar with basic UNIX CLI and using terminal-based editor vim.
You have a GitHub account and have setup .gitconfig (see Exercise 1).

Learning Outcomes

Be comfortable writing correct C programs that involve if, else, loops, and logical statements.
Be able to decompose a more complex problem into smaller subproblems and write functions to solve the sub-problems.

Setup

Click on this link to accept the exercise.
Log in to one of the hosts of CS1010 programming environment (PE)
Run the following on the command line on one of the PE hosts:

~cs1010/get-ex03

You should see a new subdirectory ex03-<githubid> in your current working directory, where githubid is your GitHub ID.
Inside that directory, you should see a bunch of files:
- binary.c, rectangle.c, prime.c and fibonacci.c are the most important files. They are the skeleton C code that you should edit to solve the exercise.
- inputs and outputs are subdirectories that contain test inputs and test outputs. We use the same convention as Exercise 1 so you should be familiar with them.
- Makefile: This is the configuration for the tool make that we use to automate the compilation and testing of the programs.
- test.sh: This is a bash script for testing your code.

Solving The Assignments

Edit the .c files on the PE hosts to solve the corresponding question as described below.
You can assume that all test inputs are valid inputs.
To compile and run the given tests with the sample inputs and outputs, run on the command line,

make

This will compile all your C files and if there is no error, run the test scripts.

Submission

When you are ready, run the following command while you are in the exercise directory:

~cs1010/submit-ex03

The .c files will be uploaded to GitHub. You can submit multiple times. As an exercise is not graded, submitting your code only serves the purpose of archiving your work for backup purposes.

Question 1: Binary

In this question, you are asked to convert a number represented in binary format (using digits 0 and 1) into the decimal format (using digits 0 and 9). A number in decimal format is represented with based 10. The last digit (rightmost) corresponds to the unit of $10^0 = 1$ , the next digit (second last) corresponds to the unit of $10^1 = 10$ , and so on. So, one can write the decimal number, for instance, 7146 as $7 \times 10^3 + 1 \times 10^2 + 4 \times 10^1 + 6 \times 10^0$ .

A number represented in binary uses base 2 instead of base 10. The last digit corresponds to $2^0 = 1$ . The second last digit correponds to $2^1 = 2$ , the third last digit corresponds to $2^2 = 4$ , and so on. So, the binary number 1101, for instance, corresponds to $1 \times 2^3 + 1 \times 2^2 + 1 \times 2^0 = 13$ .

Write a program called binary that reads in a positive integer consists of only 0s and 1s from the standard input, treats it as a binary number, and prints the corresponding decimal number to the standard output.

Sample run:

ooiwt@pe113:~/ex03-ooiwt$ ./binary
1101
13
ooiwt@pe113:~/ex03-ooiwt$ ./binary
111
7
ooiwt@pe113:~/ex03-ooiwt$ ./binary
10110100
180

Question 2: Rectangle

Write a program called rectangle that reads two positive integers from the standard input, corresponding to the width and the height of the rectangle. The width and height must be at least 2. Draw a rectangle on the screen using the special ASCII characters #define "╔" "╗" "╝" "╚" "═" "║", which corresponds to the top left, top right, bottom right, bottom left, top/bottom edge, and left/right edge of the rectangle respectively. Strings consisting of these special characters have been given to you in rectangle.c and we have defined them as constants. For instance, "╔" is called TOP_LEFT, and to print this out, you can write

cs1010_print_string(TOP_LEFT);

ooiwt@pe113:~/ex03-ooiwt$ ./rectangle
2 2
╔╗
╚╝
ooiwt@pe113:~/ex03-ooiwt$ ./rectangle
2 10
╔╗
║║
║║
║║
║║
║║
║║
║║
║║
╚╝
ooiwt@pe113:~/ex03-ooiwt$ ./rectangle
10 10
╔════════╗
║        ║
║        ║
║        ║
║        ║
║        ║
║        ║
║        ║
║        ║
╚════════╝

Question 3: Fibonacci

The Fibonacci sequence is a sequence of numbers 1, 1, 2, 3, 5, 8, 13, ... Fibonacci numbers often appear in mathematics as well as in nature and have many fascinating properties.

The Fibonacci sequence can be constructed as follows. The first Fibonacci number is 1. The second Fibonacci number is also 1. Subsequently, the i-th Fibonacci number is computed as the sum of the previous two Fibonacci numbers, the (i-2)-th, and the (i-1)-th.

Write a program called fibonacci that reads a positive integer number n from the standard input, and print the n-th Fibonacci number to the standard output. Your program must not use recursion.

ooiwt@pe113:~/ex03-ooiwt$ ./fibonacci
1
1
ooiwt@pe113:~/ex03-ooiwt$ ./fibonacci
10
55
ooiwt@pe113:~/ex03-ooiwt$ ./fibonacci
83
99194853094755497

Question 4: Prime

Write a program called prime that reads a positive integer n from the standard input and either prints prime if n is a prime number, or prints not prime if n is not a prime number.

ooiwt@pe113:~/ex03-ooiwt$ ./prime
2
prime
ooiwt@pe113:~/ex03-ooiwt$ ./prime
14000605
not prime
ooiwt@pe113:~/ex03-ooiwt$ ./prime
99194853094755497
prime

Bonus: UNIX Pipe

If you look at the output from the last fibonacci example and the input to the last prime example, you will see that they are the same number. This means that the 83^rd Fibonacci number is prime!

Suppose now you want to ask, is the 13^th Fibonacci number a prime? How can we use the programs that we have wrote to do this? There are several ways

You can merge the two C files to create a new program that, given n, calculate the n-th Fibonacci number, then check if it is prime.
You can reuse the two programs you have already written. First, run fibonacci with input 13, then cut-and-paste the output as input to prime.

A better alternative is to use a | in a UNIX-based system. A |, called a pipe, basically interconnects the standard output of one command to the standard input of the second command. Consider the following:

ooiwt@pe113:~/ex03-ooiwt$ a | b

Whatever the program a prints to the standard output, will be read by the program b when it reads from the standard input. You have seen how the standard input can refer to a keyboard or a file, now you have seen how the standard input can also be another program!

Back to the original problem: how to check if the 83^rd Fibonnacci number is prime? You can run:

ooiwt@pe113:~/ex03-ooiwt$ ./fibonacci | ./prime
83
prime