Assignment 1, CS2101b 2012
Posted date: Wednesday, January 25, 2012
Due date: 11:59pm, Wednesday, February 8, 2011
This assignment consists of three parts.
Part one is a first experience with writing a C program
interacting with the user in order to perform some calculations.
Here, we would like students to experience command line input,
and to understand and use C types such as int and float, as well
as the flow control structures studied in class.
Part two is an introduction to performance issues
with programs, more precisely with scalability and
data locality.
Part three provides you with a list of exercises
on UNIX and shell commands.
Please, read carefully the Assignment Submission Guidelines.
Part one: (30%)
The goal of the
exercise is to implement a simple calculator, called "calculator".
and which works as follows.
(1) First, the user is asked what she/he wants
to do. Three characters can be entered, each corresponding to a possible action.
q for quit
a for addition
m for multiplication
(2) In case of a or m,
the program asks the type of the operands
f for float
i for int
(3) Then the program
asks for the two operands, displays the result and returns to Step (1).
You are asked to write a C program implementing this calculator.
Your program should handle non-valid input values.
More precisely, you should consider the cases where the user
- enters other characters than q, a or m at Step (1)
- enters other characters than f or i at Step (2)
However, we assume that the user will always enter
valid operands at Step (3).
Part two: (40 %)
The goal of the
exercise is to experiment with the performance degradation
caused by high rate of cache misses.
To this end, you are required to implement a well-known
algorithm for sorting integer numbers and try it on larger
and larger input data sets.
This algorithm is the
counting sort algorithm. At its wikipedia page, you will find a detailed description of this algorithm.
- 1. Realize a C Program implementing the counting sort algorithm.
The input of this program is simply two positive integers n and k.
The integer n is the size of the array to be sorted.
The entries of this array are random non-negative integers
less or equal than k.
There will be no output for this program, since we are
only interested in its running time.
- 2. Set k to be the largest value of a C int.
Measure the running time for n = i * 100000000
where i is successively 1,2,3,4,5,6.
- 3. Theoretically, the number of operations performed
by the counting sort algorithm is (asymptotically)
proportional to n + k.
Do the experimental results of the previous question
reflect that fact?
If not, explain why. Hint: Try to estimate the number of
caches incured by the algorithm when both n and k
are larger than the size of the L1 cache.
Part three: (30 %)
In this exercise,
you are required to give a shell command line for each of the following 14
questions.
Note: for each question below, please test it once and record your test runs using
the script command.
-
1. Inside the directory ~/CS211/Asn1/
(if you do not have such a directory, create one),
create a folder whose name is your UWO username
-
2. list all the files under ~/CS211/Asn1/ such that
the folder you just created is listed at the bottom
-
3. cd to the folder you just created.
Use one command to create a file a.txt, whose content is:
hello
Create another file b.txt, whose content is: world
Concatenate the two files together and name the new file as c.txt
-
4. give at least two ways to display the content of the file a.txt
-
5. rename c.txt as d.txt
create a subfolder with the name hello inside the current folder
-
6. copy d.txt into the folder hello
-
7. remove the whole folder hello
-
8. create a symbolic link with name c.txt and pointing to d.txt
-
9. without leaving the current directory,
use two ways to print your home directory
-
10. find all files with the name d.txt inside your home directory
-
11. print the type of the file d.txt
-
12. give the user execute permission for
the file d.txt
-
13. use one command to cp all files ending with .txt
to the folder hello
-
14. gives the group user executable access only to
those files already executable in the current folder and
its subfolder hello