IC221: Systems Programming (SP16)

Home Policy Calendar Resources

Lab 03: Basic C Programming

Table of Contents

Preliminaries

Lab Learning Goals

  1. To compile and execute basic C programs
  2. Write programs with format input and output with printf() and scanf()
  3. Programs using basic pointers and structures
  4. Programs using arrays

Lab Setup

Run the following command 

~aviv/bin/ic221-up

Change into the lab directory 

cd ~/ic221/lab/03

All the material you need to complete the lab can be found in the lab directory. All material you will submit, you should place within the lab directory. Throughout this lab, we refer to the lab directory, which you should interpret as the above path.

Submission Folder

For this lab, all scripts for submission should be placed in the following folder: 

~/ic221/lab/03

Only programs found in the folder will be graded.

Submission Instructions

To submit, make sure that all your programs are in the submission folder on a Computer Science department lab machine, i.e., a machine in MI302 or MI316. Then issue the command: 

~aviv/bin/ic221-submit

Follow the prompts and select the right submission to submit.

Common Mistakes:

  • You are not logged into a lab machine and are instead on your local machine. Solution: ssh into a lab machine and run the submit script.
  • You did not copy your code from your local machine to a lab machine. Solution: use sshfs to mount your account and submit your code, or use scp to copy your code.

If you still have trouble submitting your code, email your instructor.

Test Script

To help you complete the lab, I have provide a test script that will run basic tests against your program. The script is not designed to be comprehensive, and you will be graded based on a larger array of tests. To execute the test script, run it from anywhere within the lab directory. 

./test.sh

README file

You are required to submit and complete the README file in your submission folder.

Compiling your code:

To compile your code, use gcc the gnu c compiler using the following command: 

gcc -Wall -g manipulator.c -o manipulator

The -Wall option will provide additional warnings. The -g option will include debugging symbols in case you want to use the debugger.

Lab Description and Requirements:

In this lab you will be programming a single program called manipulator which will take in user input to construct an array, and then perform basic manipulations over that array as desired by the user. Here is a basic run of the program for reference: 

$> ./manipulator 
Enter the length:
4
Enter 4 numbers (space seperated):
1 2 3 4
Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
1
{ 1 2 3 4 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
2
{ 4 3 2 1 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
3
{ 4 1 2 3 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
4
{ 1 2 3 4 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
0
$>

Part 1: Reading Input from the User and Error Checking (20 points)

The first part of the lab is to get user input, error check that input, and populate the array. See the TODO PART 1 comments to direct you to the appropriate places to work. Below is some additional information to help you complete this task.

Error checking scanf()

Recall that in the prior lessons that in C we write output and read input using format strings, unlike in C++ which uses streams. In this part of the lab you will write a simple program that takes input from the user and manipulates that input in some way depending on the user choice. You must also error check user input. 

RETURN VALUES

     These functions return the number of input items assigned.  This
     can be fewer than provided for, or even zero, in the event of a
     matching failure.  Zero indicates that, although there was input
     available, no conversions were assigned; typically this is due to
     an invalid input character, such as an alphabetic character for a
     `%d' conversion.  The value EOF is returned if an input failure
     occurs before any conversion such as an end-of-file occurs.  If
     an error or end-of-file occurs after conversion has begun, the
     number of conversions which were successfully completed is
     returned.

What this means is that if a user enters something that is not a number, then scanf() will return 0, indicating that it could not properly convert the input into a number given the %d format directive. We can easily check for such a condition in our code: 

int a, res;
printf("Enter a number:\n");
res = scanf("%d",&a);
if( res == 0){
  printf("ERROR: Invalid input");
  //exit, return, or take some other action
}

Requirements

For this part of the lab you must complete the TODO labels that request user input for the user:

  • You must read in the desired length of the array to be manipulated. If the user input is not a number, you must return 1 and exit with the following print statement: 

    printf("ERROR: Invalid input\n");

  • You must read in the appropriate number of values into the array and check to make sure that they are valid integers. If the user input is not a number, you must return 1 and exit with the following print statement: 

    printf("ERROR: Invalid input\n");

  • You must set up the logic for dealing with user choice of operations. For example, this means if user chooses 0, then the loop should break, and if an invalid number is entered the loop should continue with the following error printed: 

    printf("ERROR: Invalid number. Choose again.\n\n");

Here is some sample output with the error conditions: 

$> ./manipulator 
Enter the length:
a
ERROR: Invalid input
$> ./manipulator 
Enter the length:
5
Enter 5 numbers (space separated):
1 2 a d a m
ERROR: Invalid input
$> ./manipulator 
Enter the length:
5
Enter 5 numbers (space separated):
1 2 3 4 5
Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
a
ERROR: Invalid input. Choose again.
Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
0
$>

Part 2: Printing the array in the right format (20 points)

For this part of the lab you must complete the print_array() function and properly pass the arguments to the array.

Passing Arrays as Function Arguments

When you pass arrays to functions you are not actually passing the array, but rather a reference to the array, i.e., a pointer. Recall that pointers and arrays are really the same thing. So if you have a function that takes an array as an argument, it is really taking a pointer. For example: 

void foo(int * a){
   //...
}

It remains ambiguous if a is a pointer to a array of integers or a single integer, but it is semantically and syntactically correct. If you want to disambiguate the fact that the function takes a reference to an array of integers, that is, a constant pointer, rather than an arbitrary pointer, you can specify it like such: 

void foo(int a[]){
  //...
}

Finally, when you pass an array, since you are only passing a reference, you are not providing any information about the length of the array. While you might be tempted to use sizeof(), that is incorrect. sizeof() returns the size in bytes required to store the data item, which for an array of integers is not the length of the array because each integer is 4 bytes.

To manage sizes of arrays, it is customary to pass both the reference to the array and the size of the array to the function to ensure that you do not access the array out of bounds. 

void foo(int a[], int len){
  //...
}

Requirements

  • You must complete the print_array() function and properly call it in the main() function when the user provides option 1.
  • The format output of the array must match the following example:
{ 0 1 2 3 4 }
  • The entire array must be printed with the appropriate values in the right order
  • Numbers must be space separated
  • There must be a leading and trailing brace, { and } respectively, which are also space separated.
  • Following printing the array, an additional new line should be printed
  • The array and the length of the array must be passed as arguments to printarray.

Sample output below: 

$> ./manipulator 
Enter the length:
5
Enter 5 numbers (space separated):
0 1 2 3 4 5
Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
ERROR: Invalid number. Choose again.

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
1
{ 0 1 2 3 4 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
0

Part 3: Reversing the array (25 points)

In this part of the lab you are going to complete the function to reverse the array.

Requirements

  • You must complete the reverse_array() function and properly call it in the main() function when the user provides the option 2.
  • You must print the array following the completion of the operation. (Hint: you've already written this operation, don't do something twice!)

Sample output: 

$> ./manipulator 
Enter the length:
5
Enter 5 numbers (space seperated):
0 1 2 3 4
Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
1
{ 0 1 2 3 4 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
2
{ 4 3 2 1 0 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
0

Part 4: Randomizing the array (25 points)

Random Integers

A random number generator is built into the C standard library: random() returns a random integer between 0 and 264-1. For the purposes of this lab, you'll only need random numbers in the range of the length of the array. To properly bound the random numbers being generated, use the modulo operator: 

int r = random() % bound; //produce random number between 0 and bound-1

Seeding Random Numbers

Additionally, as you test your program, you will likely want your random numbers to be deterministic, that is, be random but predictably random so that each run you get the same random numbers. To make things easier for you, I have seeded the random number generator like so: 

srandom(1845); //seed random number generator with seed 1845

Pseudocode for array randomization

Randomizing an array of values is equivalent for performing random swaps for items in the array. It is a bit overkill, but here is some pseudocode to use: 

foreach index i in array:
  choose a random index j
  swap array[i] with array[j]

Requirements

  • You must complete the randomize_array() and properly call it when the user selects option 3.
  • Your randomization routine must execute as the pseudocode above.
  • You must use the proper seed for testing purposes, as described above.

Here is some sample output: 

$> ./manipulator 
Enter the length:
5
Enter 5 numbers (space seperated):
0 1 2 3 4
Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
3
{ 3 1 2 4 0 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
0

Part 5: Sorting the array (10 points)

The last part of the assignment is the trickiest. You must write a array sort routine. You may or may not have had experience writing sort functions before, so I encourage you to look at insertion sort on wikipedia, which is perhaps the easiest to implement.

Requirements

  • You must complete the sort_array() and properly call it when the user selects option 4.
  • Any sorting function you implement will receive credit.
  • (Extra Credit: 5 points): Implement quicksort as your sort routine. Indicate so in your README if you have completed this extra credit. Do not submit non-working sort as it can impact your grade for this part.

Here is some sample output: 

$> ./manipulator 
Enter the length:
5   
Enter 5 numbers (space seperated):
0 1 2 3 4
Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
3
{ 3 1 2 4 0 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
4
{ 0 1 2 3 4 }

Choose an operation:
(0) : exit
(1) : print array
(2) : reverse array
(3) : randomize array
(4) : sort array
0