Issued on: Tuesday 1:00am, February 27, 2007.
Due by: Thursday midnight, March 15, 2007.
This assignment is designed to:
- gain familiarity with programming structured C programs from scratch
- gain experience writing functions and passing parameters
- gain experience with arrays, pointers and strings
- prepare for the midterm!
For this assignment, a paper submission and an electronic submissions are required. The electronic submission consists of source programs (one for each of the following questions: 2, 3, 4 and 5). The paper submission consists of the answer to Question 1.
These source programs can be sent by email to the instructor.
As usual, you need also an assignment ticket and an submission form, to be included in an envelope together with the paper submission.
The locker of CS211b is 99 at the groundfloor of Middlesex College.
You should use the gcc compiler to compile your programs. In particular, you must compile your programs with the -Wall switch to turn on all warnings:
gcc -Wall -o output cfile.cIf your compilation has warnings with the -Wall switch, fix them! Marks will be deducted for programs that generate warnings when compiled with -Wall. These warnings generally mean that you aren't following the rules... fixing the warnings will give you a better C program.
Your programs should contain sufficient comments that another person, familiar with the C programming language, can follow your algorithms and code. Your comments should include:
- Specification of each function, above its profile declaration
- Comments at the top of the file, which should list:
- Your name
- Your student number
- CS211b, and the assignment number
- The name of the C file
- A short explanation of the purpose of the program, in your own words
- Block and/or line-by-line comments within the code, which should provide sufficient explanation that another programmer can follow your code.
Answering a question asked in class.
In C programing, the word NULL designates the null pointer.
- (A) Using commands such as grep determine where and how this value is defined on obelix
Random Latin squares.
A Latin square of order n is an n by n array such that:
- each cell of the array contains a positive integer less or equal to n,
- in such a way that each value occurs once in each row and once in each column.
Here is an example.
1 2 3 2 3 1 3 1 2 The goal of this question is to realize a C program performing the following:
- (a) generate a random 5 by 5 array with integer entries in the range 1,...,5
- (b) if this array is a Latin square then go to step (c) otherwise return to (a)
- (c) display this Latin square and terminate.
Your program should contain at least three functions:
a function generating a random n by n array with integer entries in the range 1,...,n where n is a parameter of this function,
- a function checking whether a n by n array (with integer entries in the range 1,...,n) is a Latin square,
- a function displaying a n by n array with integer entries.
A matrix editor.
The goal of this question is to realize a C program that would allow the user to perform the following actions on entering one of the characters e, d, r, q respectively:
- enter a matrix with integer coefficients,
- display the entered matrix, if any,
- replace a value in the the entered matrix,
- quit the program.
After entering e, the user is asked
- to enter two integer numbers n and m, the respective numbers of rows and columns of the matrix,
- to enter the coefficients of the matrix line by line.
After entering r, the user is asked to enter three integer numbers i,j,v such that v becomes the new value at the intersection of Row i and Column j.
Some remarks:
- On invalid input, an error is reported and the user is asked to re-enter the requested input.
- The size of the matrix is known only at run-time, that is, when the user enters n and m, hence you will need to use pointers, similarly to what we did with the last example (slide 20) of the chapter on pointers.
Your program should contain at least three functions:
- a function for entering a matrix with integer coefficients,
- a function for displaying a matrix with integer coefficients,
- a function for replacing a value in a matrix with integer coefficients,
An efficient trick for sorting numbers.
The goal of this question is to modify the program for sorting on Slide 12 of the chapters on arrays. Three modifications are to be implemented:
- the user provides two positive integers s and r,
- the array tab must have size s and the entries must be random integers in the range -r...r,
- the algorithm for sorting is replaced by the algorithm below, called linear sort.
The principle of this algorithm as follows:
- First, the algorithm determines the smallest entry and the largest entry in the array to sort, let us call these values a and b respectively.
- Second, the algorithm allocates an auxiliary array of size b-a+1 and assigns each slot to zero.
- Third, the algorithm goes through all slots of the input array: if a slot with index i of the input array contains value v then the value of slot v-a in the auxiliary array is incremented by one.
- Fourth, the algorithm goes through all slots of the auxiliary array: if the j-th non-zero slot of the auxiliary array has index k and value v, then the slots of index from j to j+v-1 of the input array are all set to a+k.
- Fifth, the algorithm de-allocates the auxiliary array.
Implementing our tr command.
The goal of this question is to realize a C program implementing a utility similar to the tr command. This new command works as follows:
By word, we mean a word in the usual sense. So we can assume that each of the strings str1, str2, str3 consists of words (taken from some dictionary) and separated by white space.
- First, the user enters a character string str1.
- Second, the user enters a character string str2.
- Third, the user enters a character string str3.
- Fourth, the program replaces every occurrence in str3 of the i-th word of str1 by the i-th word of str2.
- Fifth, the program displays the translated version of str3.