C Programming

Due Date: 9/28 (by 11:55PM)
Submit using WebCT: assignment HW1

Late Penalty: 25% per day. No submissions will be accepted after 10/2 at 11:55PM.

You may not share code with anyone else, you must work alone!
Feel free to discuss the project with anyone, just make sure you don't share code in any form! You are expected to write all the code you submit (do not submit code you find on the WWW!!!).

This assignment involves the creation of C program which can be compiled under FreeBSD. We will test your code on the CS BSD machines (monica.cs.rpi.edu, ashley.cs.rpi.edu, mary-kate.cs.rpi.edu) using gcc as the compiler.

Program that sorts (signed) integers according to the number of bits set to '1'

Sorting Order

Below is an example of the output expected from your program. The command line shown tells the program to sort the list of numbers 1, 12, 1234, -1, -100, 45:

./hw1 1 12 1234 -1 -100 45
BEFORE:
1        00000000000000000000000000000001 (1)
12       00000000000000000000000000001100 (2)
1234     00000000000000000000010011010010 (5)
-1       11111111111111111111111111111111 (32)
-100     11111111111111111111111110011100 (28)
45       00000000000000000000000000101101 (4)
AFTER:
1        00000000000000000000000000000001 (1)
12       00000000000000000000000000001100 (2)
45       00000000000000000000000000101101 (4)
1234     00000000000000000000010011010010 (5)
-100     11111111111111111111111110011100 (28)
-1       11111111111111111111111111111111 (32)

The qsort function is a general sorting function that is part of the standard C library. This function uses the quicksort algorithm to sort an array of things, where things could be any data type (including user defined data types such as structures).

qsort can't possibly figure out the appropriate order for array elements unless you tell it how to determine whether one element is larger than another. To accomplish this, you must pass the address of a function to qsort, it will then call this function each time it needs to compare two things.

Keep in mind that qsort calls a function you specify, so it needs to know how to call that function (what kind of parameters to pass, what the return value means). Rather than have some complex mechanism for the programmer to tell qsort how to call the comparison function, qsort has only one way it will call the function and we must build comparison functions that work according to what qsort expects. The comparison function you pass to qsort (you pass the address of the comparison function), must have the following prototype:

int compareFunction(const void *a, const void *b);

compareFunction can be whatever you want to name your function, and the parameters a and b can have whatever names you want. The only restrictions are that your function returns an int and that the two parameters are of type void *.

comparision function parameters

comparison function return value

Example comparison function

/* This comparison function orders things according to their value
   as unsigned integers */

int unsignedCompare( const void *a, const void *b) {
  /* assume that a and b are pointers to unsigned */
  unsigned int x,y;

  x = *((unsigned *)a);
  y = *((unsigned *)b);

  /* return value must be:
        < 0 when x is less than y,
        > 0 when x is greater than y, and
        0 when x == y.
  */
  if (xy) return(1);
  else return 0;
}

Calling qsort

void qsort(void *base, size_t nmemb, size_t size,
           int(*compar)(const void *, const void *));

/* Sample main that calls qsort using the unsignedCompare function
   defined earlier */

int main(int argc, char **argv) {
  int nums[] = { 1, 3, -1, 45, 33 };
  qsort(nums,5,sizeof(int),unsignedCompare);
  return(0);
}

Submission of your homework is done using WebCT (webct.rpi.edu). Once you log in to WebCT and access the CompOrg site, you should click on assignments, then select HW1. Upload your hw1.c file to webct. Make sure your browser is supported before you attempt to upload a file (there is a link to "Check Browser"). Dave will demonstrate submission using WebCT in class.

For this assignment, the file hw1.c is all you need to submit. For future assignments may need to submit multiple files...

Don't send compiled code, only send your C program!

Multiple Submissions: You can resubmit as many times as you want, WebCTwill make sure we get the last file you submit.

Grades will be determined by testing your program with various command line parameter values. We will only test with valid command lines, so you don't have to handle nonsense like:

./hw1 hi there dave

You can assume you are given a list of numbers on the command line. The numbers will all be possible to represent as a 32 bit signed ints.

To get full credit for this assignment your program must satisfy the following requirements:

• Compile using gcc, and run on the CS BSD computers.

• Display the correct binary representation and bit counts for the numbers passed on the command line

• Sort the numbers correctly (according to the number of bits that are 1 in the representation of the number).

• You must use qsort!

• Develop and test out various functions you need independently (before putting them all together). For example, write a function that will print out the binary representation of an integer, and test it. Write another that counts the bits set to 1 in an integer. Write a program to play with qsort to make sure you understand how to use it., etc.

• Make sure you test your code with lots of different kinds of input! Don't just use positive intgers when testing, try negative numbers (and 0!). Make sure your program always deals with all the numbers specified on the command line.