Using the MBCS

to Teach AP Computer Science

Copyright Chris Nevison, Computer Science Department, Colgate University, Hamilton, NY, 13346, July, 2000.  This material may be reproduced with permission for face-to-face teaching purposes only.   This material may not be reproduced or used for any commercial purpose. This copyright notice must appear on any copies made.

Don't Teach the Marine Biology Case Study, Use the Case Study to Teach Computer Science!

This summarizes our philosophy about teaching the Marine Biology Case Study.  Don't think in terms of teaching it, think in terms of using it as a tool to teach the topics of introductory Computer Science throughout the introductory courses.  Teach topics like these:
Elementary Programming Constructs: declaring variables of different types; assignment; output; apstrings; conditional statements (if...else); loops (for, while); using and defining functions; one-dimensional fixed length arrays (apvector) as counters; one-dimensional dynamic arrays (apvector) to record sequences.
Classes: use of an abstraction given as a class; modification of simple classes by adding data members and modifying member functions; understanding the design of a complex program; understanding the interaction of several classes in one program; program testing; modifying the behavior of a program by modifying the interaction of classes, including adding new member functions; implementing a simple class.
Data Structures and Algorithms: a set stored as a two-dimensional array (apmatrix); a set stored as a one-dimensional array; sorting; special purpose algorithms based on the characteristics of a particular structure; binary search; informal comparison of algorithms.

More advanced topics from the APCS AB curriculum that can be taught using the MBCS include these:  queues; linked lists used to implement sparse arrays; a map (directory) implemented as a binary search tree; a map (directory) implemented as a hash table; efficient traversals of data structures; quicksort; formal asymptotic analysis of algorithms (big-O analysis); defining new classes; object-oriented design.

Here is an outline of how you might use parts of the MBCS to teach topics in your course.  The order may vary, depending on your syllabus and text.

A topics

  1. Declaring variables of different types;  Abstraction; Assignment.  Use a single class, Position, which is used in MBCS, part 2, as an example of a class that can be used with the operations defined for that class, as well as assignment. The Position ToString function produces an apstring that can be used for output.
  2. If statements.  Use random numbers, as generated by the the class RandGen, to do any one of several tasks involving a random selection: flipping a coin, rolling a die, spinning a spinner as in a game.  Develop the simple random walk program from MBCS part 1, then try modifications.  Generate a two dimensional random walk, using the Position class from MBCS, part 2.
  3. Loops.  For loops can be introduced as a way of doing a random experiment (using RandGen) a specified number of times and getting averages, or extreme values: What is the furthest distance reached from the start in a one-dimensional random walk of N steps?  What is the furthest distance reached in a two-dimensional random walk (using the Position class) of N steps.  While loops can also be taught using these ideas:  Flip a coin until five heads appear; roll a pair of dice until the first sum of seven comes up; wander in a one or two dimensional random walk until you are a given distance from the start.
  4. Functions.  Define a function to give the distance between two positions in a two-dimensional grid; this should take two Position parameters and return a real number (double) (for Euclidean distance) or an integer (int) for "city-block" distance.  Define a function that given a Position, randomly returns one of the four neighboring positions with equal probabilities.
  5. Working with a class.  Introduce the MBCS, part 1, AquaFish class.  Modify this class so that an AquaFish has data members representing the direction of movement (to the right or to the left) and a probability of moving forward and the Swim function uses these so that the fish moves forward with the given probability, other wise moves backwards.
  6. One-dimensional arrays.  Introduce an array as a set of counters, by adding an array data member to Aquafish to record the number of times at each positions and write a program to print a histogram.  Introduce an array as a means to record a sequence of things by recording the sequence of positions the Aquafish moves to.
  7. Introduce file output by having the information on the Aquafish movements written to a file.  Then pop that file into a spreadsheet to produce a histogram chart or a line chart of the random walk.
  8. Use the MBCS to introduce the idea of "black-box" testing.  Testing a program by simply running it on data sets meeting specifications to determine if the behavior is as expected, or to discover the behavior of an incompletely specified program.  After reviewing the structure of the MBCS part 2 program, introduce "white-box" testing using the DebugPrint statements used throughout the program.  Whenever making modifications or additions to the program, include appropriate calls to DebugPrint to aid in debugging.
  9. Use the MBCS part 2 program to introduce the interaction of many objects, defined by several classes, to implement a program.  The class diagrams available on the College Board web page are extremely useful.  Having used the RandGen and Position functions earlier will make this easier, since these will be tools the students already understand.  The Neighborhood class could also be previewed like the Position class, by using it independent of the MBCS part 2 before you get there.
  10. Teach the introduction of a new data member into a class used in a larger context by adding age to the fish simulation (represent younger fish with lower case letters and older fish with upper case in the display, modify the fish data file to have ages that are read in by the Environment, etc.)  Teach the modification of multiple interacting classes by introducing the possibilities of dying or breeding to the fish simulation.
  11. Review the use of one-dimensional arrays with the use of apvector as the return type of the Encironment AllFish function that is then used in the Simulation Step functions and the Display Show function.
  12. Teach the use of two-dimensional arrays by studying the way that fish are represented in the MBCS part 2 program.  Another potential use of two-dimensional arrays is to introduce the possibility of islands or beaches to the case study by storing positions where the fish cannot move in the Environment.
  13. Teach alternate representations of a simple abstract structure, a set of fish, by comparing the representation used to store fish in the environment (the apmatrix) with the alternative of an apvector sorted by position (In the A course give the overloaded operator < for class Position, in the AB course have the students write the code for it.).  The possibility of a really huge grid. possibly too big for memory, with relatively few fish can be used to justify the apvector approach.
  14. Study sequential and binary search by using the apvector to store fish and comparing performance of an unsorted array using sequential search and a sorted array using binary search for the many lookups needed for the Environment EmptyFish function calls.  A recursive binary search can be used to teach recursion here as well.
  15. Informal study of algorithms or, for the AB course, formal big-O analysis, can be used to discuss the Update function for fish for the vector approach to storing the fish -- insert and delete or a special purpose algorithm taking advantage of the knowledge of the model.

AB topics

  1. Introduce the ideas of object-oriented design by analyzing the MBCS part 2 program from an o-o approach.
  2. Introduce queues as an alternative data structure for passing around the sequences of fish for processing, the AllFish Environment member function used in the SimulationStep function and the Display Show function.
  3. Teach about the design and implementation of a class by adding new classes to the case study.  Here are some possibilities for new classes:  A Direction class to facilitate changes in the movement of fish where probabilities are direction dependent; A Boat class for fishing; A Species class, so that each fish has a species and different species have different characteristics (like different probabilities of breeding and dying, or one species that preys on a another).
  4. Introduce linked lists in order to implement a sparse matrix of Fish as the Environment storage structure.  The need for this alternative can be based on the huge grid mentioned above, but in the context of a dynamic fish population with breeding and dying.  The sparse matrix can be represented as an apvector of linked lists.  Again, the formal asymptotic analysis of the algorithms should be developed here.
  5. Introduce the binary search tree as another alternative for storing the fish if we make another assumption -- the fish swim in an unbounded area (the Pacific ocean or even Water World), so that any bounded matrix representation can not work.  Analyze the complexity of the algorithms, ultimately of the Simulation Step function.
  6. Introduce a hash table as an alternative to the binary search tree for storing the fish.  Use the analysis of the algorithms to compare the relative efficiencies of the two approaches.  A sort, and quicksort is the natural one to use, will be needed to generate the list for the AllFish function.

We hope that this outline will convince you to use the case study not as another topic to teach, but as a tool to teach many, in fact most, of the topics of both the APCS A and AB courses.  The materials provided here should give you some good ideas on how you can do that, as well as teaching you about the details of the MBCS.