EECS 211
Array, Vector and Pointer Exercises

Below are exercises suitable for submission to the Code Critic after reading Chapters 1 through 7, and Chapter 19, of the textbook. Don't forget the rules of the queue.

The exercises are:


Exercise: Seat Assignment

Exercise 7.20 describes a simple seat assignment problem. As described, it's not set up for test-driven development, and is vague about things such as

So, here's an API (application program interface) designed for testing. Define a class ReservationManager with these public member functions:

If assign() is called for a customer already assigned a seat, the previously assigned seat should be returned.

For example, tests for the example in the exercise might look like this:

ReservationManager mgr(5, 5);
CPPUNIT_ASSERT_EQUAL(1, mgr.assign(1, 100));
CPPUNIT_ASSERT_EQUAL(6, mgr.assign(2, 101));
CPPUNIT_ASSERT_EQUAL(7, mgr.assign(2, 102));
CPPUNIT_ASSERT_EQUAL(2, mgr.assign(1, 103));

There should also be calls to assignment() to verify the assignments have been saved.

Start simple! Develop tests for a small plane with no first class seats, and no calls to assign() with the same customer ID twice. Write the tests, run them to show failure, then develop code to pass those tests.

After those tests are passed, add some tests for the repeated customer case. Run the tests. Make sure you see the failures you expect. Then write the code to handle this case.

After those tests are passed, write more tests for a plane with some first class seats. Run the tests. Make sure you see the failures you expect. Then write the code to handle first class seating.

Create a separate test function for each plane configuration and request sequence, e.g., you might have one function for the case where first class is filled (and over-requested) first, before coach, another function where the opposite happens, and a third where the requests are interleaved.

Think about ways you can use for loops to short the length of the test code.

Instead of storing 0 and 1 in the seating chart, as described in the book, store the customer ID. You can assume the ID is never 0.

Submit to Code Critic:

Remember to put a header comment at the start of the files that identifies what file they are.

Wrap Up

When the above has been approved via the Code Critic, run make handin.

Email the Zip archive produced by your Makefile with the Subject EECS 211: Seat Assignment.


Exercise: GradeBook Grades

Use TDD to implement storing grades in your GradeBook.

Recommended Reading: Sections 7.6 (arrays in GradeBook) and 7.11 (vectors).

Background

The textbook uses arrays to store grades (Section 7.6). While OK as a demonstration of arrays, this is actually a terrible way to do grades. Notice that the number of grades is fixed as 10 for all courses (Fig. 7.16). How useless is that?

The solution in C++ for storing data whose number you don't know in advance is to use vectors. The book talks about them in Section 7.11, but treats them exactly like arrays, which misses the key point of vectors: vectors are dynamic -- they grow automatically as data is added.

To do this, you call the vector member function push_back()

vector<int> grades;
grades.push_back( 85 );
grades.push_back( 92 );
grades.push_back( 78 );
cout << "There are " << grades.size() << " grades." << endl;
for ( int i = 0; i < grades.size(); ++i ) {
  cout << (i + 1) << ": " << grades[i] << endl;
}

Tasks

Create a new project directory called grades. Extract your Zip archive for your previous GradeBook exercise into this directory, to get a clean copy of the old code. If you're using an IDE like Code::Blocks or XCode, create a new grades project.

Add to GradeBookTests.cpp tests for the following function:

You should have tests for getting grades when there no grades, and when GradeBook::addGrade() has been called.

Test your tests with your current GradeBook. Make sure the old tests pass but the new ones fail.

Then, update the relevant parts of GradeBook.h and GradeBook.cpp to use a vector of integers to store the grades.

Run your tests. If any fail, fix the code or the tests as appropriate.

If you haven't already, remove redundant code:

Submit to Code Critic:

Clearly label each section of code.

Wrap Up

When the above has been approved via the Code Critic, run make handin.

Email the Zip archive produced by your Makefile with the Subject EECS 211: GradeBook Grades.


Exercise: Blob Counter

The Electro-Magic-Microscope company has hired you to develop a program that takes a B&W microscopic image and returns the number of "blobs" in the image, e.g., they might be bacteria or blood cells or whatever. A blob is a set of black pixels that border each other, horizontally, vertically or diagonally. A blob can be as small as one pixel or as large as the entire image.

Here's the kind of output they would like to see for two images, printed on a console, using x's for black pixels and periods for white, with a blob count. (The image data at the top will be explained later.)

picture of 3 blobs picture of twisty blob

As you can see, blobs can get pretty long.

Your job is to use TDD to implement a blob counter.

Background

Representing images

Images on a computer are two-dimensional arrays of pixels, where each pixel is a set of bits, representing color information. For black and white images, just one bit is needed for each pixel -- black by convention is 1, white is 0.

Internally, a 2-dimensional array of boolean values makes the most sense for representing a small image. Externally however, such arrays are not easy to write down for testing. For 8 x 8 black and white images, a more compact external notation is hexadecimal numbers. Hexadecimal uses base 16, with the digits 0 through 9, followed by A (10), B (11), C (12), D (13), E (14), and F (15). If you've ever worked with HTML color codes, like #CC6633 (one form of brown), you've worked with hexadecimal numbers. Each hexadecimal digit maps to exactly 4 bits. Decimal digits don't do that. So for example, C (12) in binary is 1100, 6 is 0110, and 3 is 0011. So the color code #CC6633 is the 24 bit binary number 1100 1100 0110 0110 0011 0011.

In C++, you write numbers in hexadecimal notation by starting them with a "0x", e.g., 0xCC6633.

An 8 x 8 image has 64 bits, or 16 hexadecimal digits. The image on the left above, with 3 blobs, could be represented in binary and hexadecimal thus:

Image rowBinary formHexadecimal form
........0000 000000
xx......1100 0000C0
....xxx.0000 11100E
x..x....1001 000090
xx..x...1100 1000C8
........0000 000000
........0000 000000
........0000 000000

On many C++ compilers, including Cygwin, 64 bits is too big for one unsigned long, so we'll use two, one for the upper half of the image and one for the lower half. Therefore, the image would be represented in C++, using the 0x numeric prefix for hexadecimal literals, as 0x00C00E90 and 0xC8000000.

Counting blobs

At first it might seem that counting blobs could be very tricky, especially considering the image above on the right. Blobs can twist and turn so no simple left to right, top to bottom scan will work. But, if you have an array you can erase (and reset later!), then there's a clever solution that works quite nicely:

Erasing the blob is the key to this. It has to erase a blob, no matter how convoluted. A simple recursive algorithm will do it. You should work out the details but here's the essence:

Erase blob(pixel): If the pixel is black, set it to white, and for each neighboring pixel, call erase blob.

Watch out for infinite loops! Watch out for the edges of the image!

Task

Use TDD, define the class Image with this API:

You won't be able to test the display function with CppUnit, but it will be useful to call when a test of getBlobCount() fails. So define display() early, when you hit your first bug.

Hint: See Figure 15.8 for a simple way to print numbers in hexadecimal.

Start simple! What's the simplest possible case? An image with no blobs! So write a test for that, make sure it fails (or doesn't even compile), then do the simplest thing that could possibly work (DTSTTCPW). That's pretty easy for this case. Don't do anything more. This is a good chance to get all the files and prototypes right without worry about any algorithms. The main algorithms you'll need are:

Hint: you can use division and remainder to "peel" off the bits in the unsigned long data. No matter how you write a number, it's all binary inside the computer. But this will give you the bits from right to left, so be careful how you write your loops to fill up the internal array.

Since the image is blank (all zeros) no code is needed to count blobs yet.

Test to make sure the above parts are working.

What's the next simplest? How about 1 pixel blobs, somewhere in the image. Create test cases for that (some hexadecimal practice), make sure the tests fail, then add code to your constructor to set the blob counter. Something very simple should work when only single pixel blobs are involved. You'll need some loops to search the array for pixels.

Now what? One multi-pixel blob? Or multiple single pixel blobs? Your call. Both need to be done, but you decide which to tackle first.

When the above all work, you're finally ready tackle the general case of multiple multi-pixel blobs.

Submit to Code Critic:

Clearly label the start of each file.

Wrap Up

When the above has been approved via the Code Critic, run make handin.

Email the Zip archive produced by your Makefile with the Subject EECS 211: Blob Counter.


Comments? comment icon Contact the Prof!

Valid HTML 4.01 Transitional