CS16, Winter 2010

el02: ("extra lab two")
Problem solving on arrays (Part 1)

el02 is offered as a recommended activity to help you study for the final exam.

It will not be graded, and is not offered for extra credit.

Since this is not graded:



Goals for this lab

This lab is an exercise in problem solving—writing various functions that operate on arrays.

As a warm up, we'll solve a problem you've no doubt seen before—returning whether an integer is odd or not.

Then, we'll solve three problems dealing with arrays—in each case by writing a function to solve the problem.

The three problems are:

  1. finding the minimum value in an array
  2. finding the maximum value in an array
  3. finding the index of the maximum value in an array

 

Prior Skills/Knowledge Needed

Before completing this lab, you should be familiar with the following:

Step by Step Instructions

 

Step 1: Log on to CSIL, create ~/cs16/el02 and copy this labs files:

 

The files for this lab can be found here:

And here:

~pconrad/public_html/cs16/10W/extraLabs/el02/files/*

 

Step 2: Familiarize yourself with the test harness files

This week's lab is about problem solving.

To allow you to focus on the problem as much as possible, we've provided a test harness for you.

A test harness is a software system that allows you to determine whether a piece of code you are developing has been written correctly or not.

So, before we start on the problem solving, we need to spend a little time getting familiar with the test harness.

Start by cd'ing into the directory ~/cs16/el02, and typing the command ls to list all of your files, as shown:

-bash-3.2$ ls
indexOfMax.c maxValue.c tdd.h testMaxValueMain.c isOdd.c minValue.c testIndexOfMaxMain.c testMinValueMain.c Makefile tdd.c testIsOddMain.c -bash-3.2$

As you can see, there are a lot of files here.

Let's try to make sense of these by dividing them into four groups.

Now, let's look at each of these groups of file in a bit more detail:

Group 1: stubs for functions

Each of these files contains

  • a function definition in stub form
  • a function that runs tests on the function just defined.

For example, isOdd.c contains the stub:

// return 1 if x is odd, otherwise return 0
int isOdd(int x)
{
  return -42; // stub @@@ FIX THIS 
}

Along with a void function that runs tests on isOdd:

int testIsOdd()
{
  int failures = 0; // this counts the number of failures

  // We use += to add the number of failures each time...

  failures += checkExpectInt("1: isOdd(1)",isOdd(1),1);
  failures += checkExpectInt("2: isOdd(2)",isOdd(2),0);
...

The other files are similar, but the functions are ones that work on arrays, such as:

// create a void function that multiplies two arrays of the same size and
// place the product into a third array 
void multiplyPairwise(int *a, int *b, int *result, int n)
{
  // In a stub for a void function, just do nothing and return
  return;  // stub @@@ FIX THIS
}

The files maxValue.c and minValue.c actually each contain two stubs, with a test function for each one.

indexOfMax.c
isOdd.c
maxValue.c
minValue.c

Group 2: main programs to run tests

For each of the files in Group 1, there is a corresponding file in Group 2 containing the main program that tests that function.

Each of these contains a main() that:

  • defines a variable failures that counts the number of failed tests
  • calls the corresponding test function
  • calls the function tddSummary(failures); which prints a one line report summarizing the results of the tests.

The definition of tddSummary is in tdd.c, and looks like this:

void tddSummary(int failures)
{
  if (failures==0)
    printf("All tests passed!\n");
  else
    printf("%d tests failed\n",failures);
}                          
             
testIndexOfMaxMain.c
testIsOddMain.c
testMaxValueMain.c
testMinValueMain.c

Group 3: Functions for Test-Driven Development

In lab02, we encountered functions like checkExpectInt(), checkExpectDouble(), etc.

It is tedious to have to include those functions in every single function we write.

A more efficient approach is to put those functions into a library and reuse them—much the same way we access printf and scanf out of #include <stdio.h>.

The file tdd.h contains function prototypes for these functions—just by putting #include "tdd.h" in each of the files in Group 1, we can put use these functions without having to define them all over again.

int assertTrue(char * label, int  assertion);
int checkExpectInt(char * label, int check, int expect);
int checkExpectDouble(char * label, double check, double expect, 
double tolerance); int checkExpectIntArray(char * label, int * check, int * expect, int n); void tddSummary(int failures);

Of course, it is still necessary to have the function definitions someplace. Those are in the file tdd.c—and when we compile, we have to mention that file, as in this example. (The -o testIsOdd part means that the executable file will be called testIsOdd):

-bash-3.2$ cc isOdd.c tdd.c testIsOddMain.c -o testIsOdd
-bash-3.2$ 

Try that—and then run the test program with ./testIsOdd—you should see the familar messages for failed tests from a stub:

-bash-3.2$ ./testIsOdd
Test 1: isOdd(1) FAILED: got -42 expected 1
Test 2: isOdd(2) FAILED: got -42 expected 0
...

Then, see if you can figure out the command you need to type to compile and run the test program that go with each of the folllowing (they are similar): indexMax.c, maxValue.c, minValue.c.


Having to type all of that each time we want to compile a file is also tedious—so there is a way to give the make command the information it needs to automate that process for us—that brings us to the only file in Group 4, namely the Makefile.

tdd.h
tdd.c

Group 4: The Makefile

This group consists of a single file called Makefile—the information in the Makefile makes reusing functions much easier.

As you may remember from an earlier lab (in Winter 2010, this was lab06), when we split up function definitions across multiple files, we have to bring all of those files together when we compile our program with a command such as:

-bash-3.2$ cc isOdd.c tdd.c testIsOddMain.c -o testIsOdd
-bash-3.2$

The Makefile contains lines called rules that automate this process. This allows us to simply type make at the Unix prompt, and the proper compiler commands are automatically run—for example:

-bash-3.2$ make
cc indexOfMax.c tdd.c testIndexOfMaxMain.c -o testIndexOfMax
cc isOdd.c tdd.c testIsOddMain.c -o testIsOdd


cc maxValue.c tdd.c testMaxValueMain.c -o testMaxValue
cc minValue.c tdd.c testMinValueMain.c -o testMinValue

-bash-3.2$ 

The Makefile also contains rules that allow several special commands to be type. Try each of these at the shell prompt:

make Compile all of the programs.
make all

Compile all of the programs.

Because this is the first rule in the file, it is also the default rule—the one that is run when you just type make

make clean Delete all of the executable files—typing this before make all allows you to recompile everything from scratch.
make test Run each of the test programs.
If the programs aren't compiled yet, this rule will do a make all first.

For now, don't worry about the syntax of the rules in the Makefile

  • You won't have to write any of those rules in this assignment
  • You won't need to modify the contents of the Makefile in any way
  • The details of Makefiles are not covered on any exam in this course.
  • For now, it is enough to understand how to use the commands
    listed in the table above (make, make all , make clean, make test)
  • Learning how to write your own Makefile is a topic for later courses
    (CMPSC32, CMPSC48).
Makefile

Summarizing what we've seen here

To summarize:

 

Step 2: Practicing working with the test harness on the isOdd function

Before we move on to the problem solving, let's practice a bit with the test harness.

Working from your ~/cs16/el02 directory, type the commands shown below at the Unix prompt—this will

-bash-3.2$ make clean
/bin/rm -f testIndexOfMax testIsOdd testMaxValue testMinValue 
-bash-3.2$ make testIsOdd
cc isOdd.c tdd.c testIsOddMain.c -o testIsOdd
-bash-3.2$ ./testIsOdd
Test 1: isOdd(1) FAILED: got -42 expected 1
Test 2: isOdd(2) FAILED: got -42 expected 0
Test 3: isOdd(33) FAILED: got -42 expected 1
Test 4: isOdd(44) FAILED: got -42 expected 0
Test 5: isOdd(-7) FAILED: got -42 expected 1
Test 6: isOdd(-8) FAILED: got -42 expected 0
6 tests failed
-bash-3.2$ 

Now, open up isOdd.c in the editor, and locate the stub for the isOdd() function.

Change the stub code (the code that returns -42) to code that:

Once you've done that, repeat the make testIsOdd and ./testIsOdd steps, and the tests should pass:

-bash-3.2$ make testIsOdd
cc isOdd.c tdd.c testIsOddMain.c -o testIsOdd
-bash-3.2$ ./testIsOdd
Test 1: isOdd(1) passed
Test 2: isOdd(2) passed
Test 3: isOdd(33) passed
Test 4: isOdd(44) passed
Test 5: isOdd(-7) passed
Test 6: isOdd(-8) passed
All tests passed!
-bash-3.2$ 
  

Note that is is not necessary to run the make clean step every time:

You'll repeat this process for each of the remaining problems in this assignment:

  1. make the test program and run it, to see that all the tests fail
  2. edit the function to replace it with code that you think will solve the problem
  3. make the test program again, and hopefully the tests pass—if not, repeat 2 and 3 as needed.

Step 3: Finding the maximum value in an array

Next, at the shell prompt, use the commands:

make testMaxValue to compile the test program
./testMaxValue to run the tests for the functions in maxValue.c

In the output, you'll see that this time we are testing two functions:

Make sure you understand the test cases:

After seeing the tests fail, open up maxValue.c in the editor (emacs or vi) and change the stubs to functions that return the correct values.

Some hints:

When all the tests pass, move on to the the next problem—finding the minimum value in an array.

Step 4: Finding the minimum value in an array

Next, at the shell prompt, use the commands:

make testMinValue to compile the test program
./testMinValue to run the tests for the functions in minValue.c

As with testMaxValue, we are testing two functions, not just one—but this time they are:

Make sure you understand the test cases:

Proceed as before—use emacs minValue.c to replace the stubs with correct code.

Finding the smallest value in an array is pretty similar to finding the largest value—so you shouldn't need any additional hints.


Step 5: Finding the index of the maximum value in an array

The next problem requires us to think carefully about the difference between indexes and values.

As a reminder of the difference, consider the following array:

int a[] = {12, 78, 99, 34, 56};

In this array:

To see the test cases, at the shell prompt, run the commands:

make testIndexOfMax to compile the test program
./testIndexOfMax to run the tests for the functions in indexOfMax.c

Make sure you understand the test cases—they are in the testIndexOfMax() function in indexOfMax.c:

Once you understand the test cases, proceed to solve the problem by editing the indexOfMax() function inside indexOfMax.c and get the tests to pass.

If you get to this point, you are finished.

This is an extra lab, only for practice—to help prepare for the final exam—so there is nothing to turn in.


Copyright 2010, Phillip T. Conrad, CS Dept, UC Santa Barbara. Permission to copy for non-commercial, non-profit, educational purposes granted, provided appropriate credit is given; all other rights reserved.