CS 216 Lab #7

Submit within a week of the lab date

x2go troubles?, such as tab key not working? Want to use Macros?

(for more instructions on macros, see lab 8)

fun with C functions: oddeven.c

Using functions and the stack: funct7.a

Write a function that calls another function. You will be processing a string, and for each character, calling an unknown function to check it. Your function simply processes the string, counting how many characters pass the test. How each character is tested will be determined by the second function. This is a very good technique for controlling complexity in a program.

strchk will simply go through a string (The "argument" $a0 will be the address of the string), call checkch and count how many characters pass the test. Make no assumptions about the length of the string. Do not pass the terminating zero-byte to checkch.
checkch gets a character argument (in $a0, according to the convention) and returns either 0 or 1 in $v0

All the output is handled by the main program, which you do not have to write.

Since your function is calling another, you will have to save some registers. You must use the register conventions, in particular, be sure to save $ra and any $s-registers that you use. You can expect the t-registers to be used by the function that you have to call.

The statement of the question reads as follows:

## Write a function "strchk" that returns
## the number of characters in a string $a0
## that return a 1 when passed to the
## "checkch" function.
## Otherwise checkch returns 0.
## do not rely on the label "str" or the 
## particular implementation of "checkch"

Having fun with C functions: oddeven.c

This week's C program is more fun than practical, it is designed to allow you to work with a few functions.
Three are quite simple, and the other, "rearrange", is to rearrange the numbers in an array so that all the even numbers come first, then all the odd numbers.
The ordering among each set of numbers does not matter, so the mipsmark tests will print out the sums of each set.

Well, now I can ask you to also implement 2 more functions, "sum" and "firstodd" -- that needs to return the index of the first odd number in the rearranged array (or any array for that matter).

Finally, I would like you use the function "swap" of two values in "rearrange". "swap" is as found in the "C Programming Language." The arguments need to be pointers (addresses).

Scanning up and down an array

Quicksort is an elegant O(n log n) algorithm that uses a function "partition" (C. A. R Hoare, CACM Algorithm 63, 1960) It is a bit tricky, basically there are two pointers, one starting at the beginning of the array and moving up, until an out of place element is found, the other starting at the end, and moving down (decrementing), [or left, depending on how you draw your array.]
When the two pointers cross, you are done. Otherwise, once two out of place numbers are found, you swap them.
This would be a good way to implement "rearrange" as there is a simple test for "out of place": a number is either odd or it is even. A bitwise and (&) can tell you that.

The suggested method should be O(n). Avoid needless swaps. My swap also counts the number of swaps. Case 1 will fail unless you use it, case 3 can be done with 1 swap, and will fail if you do more.
(This would count as conditionally passing, and cost 1 point)

The problem statement is as follows:

/*  write a function "rearrange" that will rearrange the numbers in an array,
	such that all the even numbers come first.
	You may assume that the array will contain both odd and even numbers.
    USE the function "swap" provided. It will exchange the two integer values
        pointed to by its two arguments.
        Use this in "rearrange" A goal is to minimize the number of swaps.
    write a function "firstodd" that will return the index of the first 
	odd number in an array
    write a function "sum" that will sum the numbers in an array

The main program will use these functions to print the sum of even numbers
	and the sum of odd numbers. Each group of numbers may appear in any order.
*/

Your functions must conform to these prototypes (as swap does):

void swap(int*, int*);	// swap the values pointed to
void rearrange	(int a[], int length);  // use swap to put even numbers first
int  firstodd 	(const int a[], int length);  // return index of first odd number in a
int  sum	(const int a[], int length);  // sum the numbers in a

const means that the values in the array will not change - a promise the compiler will enforce.

Place your functions between the cut lines.
Use mipsmark and submit cs216 as usual

Back to cs 216
Home page of Lin Jensen