Assignment 1, CS2101a 2012

Posted date: Tuesday, September 25, 2012

Due date: 11:59pm, Tuesday, October 9, 2012

This assignment consists of three parts.

Part one is a first experience with writing a C program interacting with the user. 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.

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 standard questions 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)

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