AP Computer Science Workshop, Berkeley, 1998
If you're reading online, either via the internet or from
a local file system, it is possible that clicking on links
for programs (.cpp suffixes) and/or header files (.h suffixes)
will launch your default programming environment, e.g., Visual C++
or Codewarrior. If you prefer to have these files rendered in
the browser as plain text do the following (conversely, change
the instructions if you want to use the IDE rather than the browser):
- If you're using Netscape, select Editor/Preferences then
Navigator/Applications. Find C++ header files and programs, and
change the MIME type to text/plain, then accept this, and
open it again to select Navigator as the application that will process
the files. You have to change the MIME type first (apparently, or at
least that's what I had to do).
- If you're using Internet Explorer, I'm not sure what to change
since it worked for me on my machine as I write this, although I know
that in the past loading a file launched my default programming
environment. Is IE using Netscape preferences? If you know the
answer to how this works, drop me
an email note
Designing Classes/CRC Day, Morning
We'll spend the morning talking about how to design programs using
classes and how to design classes. There are many resources that can
help with OO design. However, my experience is that students new to
programming and computer science have a hard time with design, so it's
usually a good idea to supply lots of good designs to learn from, to
supply designs initially for students to build from and on, and to keep
design heuristics and guidelines to a minimum.
A few good books for reading and learning about design are listed here,
these are probably better as resources once you know about programming
and some C++ rather than for the beginning programmer. Most of the
books assume that you'll be using inheritance since this is basic to OO
Design and Programming, but inheritance is not part of the AP C++
subset. However, the books below are still useful.
- Object-Oriented Design Heuristics, by Arthur Riel,
Addison-Wesley, ISBN 0-201-63385-X.
- Mastering Object-Oriented Design in C++, by Cay Horstmann,
John Wiley, ISBN 0-471-59484-9.
- More to follow
The two most important concepts to keep in mind are:
- Cohesion. In a function this means that the code
in the body of a function is closely related, a function should do one
thing, not several. In OO programming, strong or tight cohesion means
that a class should capture one abstraction or idea. Keep away from
classes that do too much, so called "kitchen sink" classes. The main
idea is simple: keep related data and functions in one place.
- Coupling. Loose coupling means that classes
should have little dependency on each other. It's impossible to have no
dependencies or classes couldn't be used together. The idea is that
modifications to one class should have minimal affect on other classes
with which the first (modified) class communicates. For example,
all the apclasses depend on apvector, so apvector and the other classes
are strongly coupled. However, the other classes only depend on the
public interface of apvector, not on how apvector is implemented.
Playing Hangman
The first program we'll work on is one to play hangman. In designing
the program you want to keep in mind some goals that may conflict:
- The program should be (relatively) simple to implement in a
prototype form.
- The program should be configurable, i.e., allow the number of
misses to be changed simply for different levels of play.
- The program should be (relatively) simple to change to support a
graphical interface for the hanged person if access to a graphics
package is available.
- The program should be straightforward to support different
languages using the English alphabet, and, perhaps, languages that use
other alphabets.
We'll use three steps to arrive at an initial design that we'll then
take to a prototype stage. Your first task is to get into a group with
up to three people; please work together on this. After each of the
three steps below we'll stop and talk about where we are before going to
the next step.
- Brainstorm by listing nouns that are part of playing a game of
hangman using the computer. Initially you'll list lots of nouns, and
then you'll make the list smaller. From the list will come the classes
used in the program and the private data that makes up the classes.
Every noun is not a class. At first write down nouns almost
indiscriminately. Next, eliminate synonyms --- nouns that in the
program probably refer to the same abstraction. Then determine what the
key classes will be in the program, what nouns would be better as data
than as classes, what nouns will be variables in functions, and what
nouns should be eliminated. You can always change your mind.
- With list of nouns in hand, you'll start to think of verbs which
are member functions associated with each class/noun. You'll also begin
to think about how the classes interact with each other. To help here,
you'll use CRC cards. CRC stands for Class,
Responsibility, and Collaboraters. For any one class,
the responsibilities are the member functions associated with the class
and the collaborators are classes that interact with the class. All are
listed on one 3x5 index card.
- Revisit the design, is anything missing? In developing the CRC
cards did you change what the main classes are? Now you should begin to
think about implementation, what's the data associated with each class.
Notice that you don't think about data first, you think about
responsibilities or behavior first. This is key: behavior comes
before data.
After going through these steps, you're probably ready to prototype a
few of the classes to see if you'll need to go back and revisit the
design. Implement each class separately. Develop methods for testing
the classes individually before testing them with each other. Sometimes
this will be tricky when one class is used to implement another.
A version of hangman that reflects a combination of several
group designs is available. The directory for the project/class header
files and implementations is accessible.
Playing Roulette
In roulette you can place bets on which of 38 numbers is chosen when a
ball falls into a numbered-slot. The numbers range from 1--36 with
special 0 and 00 slots. The 0 and 00 slots are colored green; each of
the numbers 1--36 is red or black. The red numbers are 1, 3, 5, 7, 9,
12, 14, 16, 18, 19, 21, 23, 25, 27, 30, 32, 34, and 36. Gamblers can
make several different kinds of bet, each of which pays off at different
odds. Some common bets are:
Bet | Odds |
red or black | 1 to 1 |
odd or even | 1 to t |
single number | 35 to 1 |
two consecutive numbers | 17 to 1 |
three consecutive numbers | 11 to 1 |
A payoff of 1 to 1 means that a $10.00 earns $10.00 (plus the
bet $10.00 back); 17 to 1 means that a $10.00 earns $170.00 (plus
the $10.00 back). If the wheel spins 0 or 00 then all bets lose except
for a bet on the single number 0/00 or on the two consecutive numbers
0/00.
Design a program that allows a player to make bets on roulette until
either all money is lost or the player decides to retire. The player
should be given an initial bankroll and then be prompted repeatedly for
a bet. After each spin of the wheel the player should be appraised of
the money available and asked if the game should be continued or chips
cashed in.
Playing Jotto
The word game Jotto is similar to mastermind, but played with
five-letter words instead of colored pegs. Two players each pick a
secret word that is not revealed. Players than take turns guessing five
letter words. For each guessed word the opponent tells how many letters
are in common with the secret word. For example, if player A picks
 "flops" as the secret word, and player B guesses
 "spore",
then Player A responds that "spore" has 3 letters in common with his
secret word. The player who determines the oponent's secret word with
the fewest guesses wins.
Note that if the secret word is "tooth", the guess "pores" has one
letter in common: 'o', the guess "tease" has one letter in common: 't',
and the guess "spoof" has two letters in common:
'o' and 'o'.
Design a program that allows the user to play with the computer so that
both competitors try to guess each other's word. It's very easy to come
up with a strategy for the computer that does well without much
intelligence: after every guess, eliminate every word that can't be the
secret word. For example, if the guessed word (at random) has two
letters in common, then eliminate every word that doesn't have exactly
two letters in common with the secret word. Your program should make it
straightforward to plug in new computer strategies.
Designing Classes/CRC Day, Lab
For the lab, you'll implement one of the programs you designed earlier.
Most likely you'll discover flaws in the design that you'll fix as you
implement the classes and functions that comprise the program.
I suggest implementing hangman since it's more interesting to play,
although Jotto is also interesting in seeing how well a so-called "dumb"
strategy does.
You should use the environment you'll be using during the year if that's
available. You should specify C++ Console App, or the closest
equivalent, when creating the project. We'll provide information about
where ap classes are located as well as the location of a project that
is used to create a library of useful classes. You should add this
library,  aplib.lib to your project. From my perspective
in thinking about the most important things to get across about using
environments, a library is the single most important concept you should
work on, we'll discuss whether I'm correct, an idiot, or simply
addle-brained.
Designing Classes/CRC Day, More discussion
We'll discuss a class design for what is intended to be the next case
study after BigInt. The study involves a simulation of creatures
roaming in a 2D grid world. This is similar to the WATOR simulation
that appeared in Scientific American several years ago, and is related
to the Game of Life invented by the mathematician John Conway.
For discussion, we'll envision fish living in a 2D grid world. Every
time-step of the simulation, the fish move in a random direction. We'll
assume initially that this is north, south, east, west, i.e., fish move
at right angles, but in designing classes you can assume that at some
point fish will move diagonally too, i.e., there will be eight possible
directions.
The world has edges (it's pre-Columbian) so fish can't move off an edge,
and don't wrap around when moving, although it's possible that this will
change too, so that at some point the world will be toroidal rather than
flat.
For the first design, assume that there's an initial distribution of
fish that might come from a file, or be random, or be hardwired into the
program. Fish move at random, one-at-a-time, i.e., it is
not the case that the fish all move at once, they take
turns. A fish cannot move onto another fish. Fish live forever.
Come up with an initial design of
classes/responsibilities/collaborators. We'll think about this in
groups, then discuss, then go back to groups to think more about the
design.
After the initial design there will be some changes.
Among the changes might be the following, determine how your design will
change as a result of these changes.
- Fish live for a discrete number of time steps, then die. However,
a fish gives birth to a new fish every so often. It might be the case,
for example, that a fish lives for 100 time-steps, and that every 10
time-steps a fish gives birth with a probability of 20%. Giving birth
means a baby fish occupies a space adjacent to the birthing fish, after
the birthing fish moves. The baby fish takes the space the birthing
fish used to have.
- In addition to fish, there is food in the world. Food never dies,
but it is eaten by a fish whenever the fish moves onto the food. A fish
that eats extends its lifespan, say by 10 time-steps. The food is
algae, if it isn't eaten in say 5 time-steps it grows by occupying a
free adjacent square if there is one.
Template Day, Morning
The first thing we'll do is look at a program that uses a
struct and a class for holding a collection of the structs. We'll
use this to move towards a deeper understanding of templates. This
will lead to a discussion of what the appropriate coverage of templated
functions and classes are in the A and AB courses.
The program we're using is  
people.cpp. A run is shown below, user input
in italics (see 98subgroup for the datafile).
Don Allen Highschool M 125
Bill Burden Highschool M 203
Debbie Carter Highschool F 151
Ron Colby Highschool M 771
Theresa Cuprak Highschool F 217
Ann Fleury College F 618
Mark Stehlik College M 543
David Kay College M 345
Laurie White College F 929
Owen Astrachan College M 101
------ 10 total people
search for: (return to quit) C
matches follow
Debbie Carter Highschool F 151
Ron Colby Highschool M 771
Theresa Cuprak Highschool F 217
------ 3 total people
search for: (return to quit) ll
matches follow
Debbie Carter Highschool F 151
Ron Colby Highschool M 771
Theresa Cuprak Highschool F 217
Don Allen Highschool M 125
------ 4 total people
search for: (return to quit) n
matches follow
Debbie Carter Highschool F 151
Ron Colby Highschool M 771
Theresa Cuprak Highschool F 217
Don Allen Highschool M 125
Don Allen Highschool M 125
Bill Burden Highschool M 203
Owen Astrachan College M 101
------ 7 total people
search for: (return to quit) K
matches follow
Debbie Carter Highschool F 151
Ron Colby Highschool M 771
Theresa Cuprak Highschool F 217
Don Allen Highschool M 125
Don Allen Highschool M 125
Bill Burden Highschool M 203
Owen Astrachan College M 101
David Kay College M 345
------ 8 total people
search for: (return to quit)
searching over
Your first task is to get into a group with up to three people; please
work together on this. Look at the code in   people.cpp, if you have
any questions about the code, or whether some part of the code is in the
official AP C++ subset, please ask. You should come up with a list of
comments or questions that you will bring up before the entire group.
Of course you can get answers to questions from each other too. In
addition to your own questions, please try to answer the questions
below.
- The list of matches to the user-entered search string
reflects all queries to date, not just the last query. The
function Collection::Clear can be used to get just
the results of the last query. Where are (at least) two places
the function can be called? Where should it be called?
- The Person struct has a member function
Print, and operator << is overloaded for the
struct too. How are these part of the AP subset?
- In the function Print, the function
tolower and the iomanipulator setw
are used --- are these parts of the APCS subset?
- The private field myList is grown by doubling in size,
is this a good idea? (see Collection::Add)
- Why is the variable Person p defined inside the first
while loop in main rather than before the loop?
- A while(true) loop is used in main ---
what's an alternative and which is the best approach?
Sorting
You're given the templated sort function below (this is the header or
prototype, you're also shown the actual code below).
template
void SelectSort(apvector & a, int size)
// precondition: size = # of elements of a
// postcondition: a is sorted
//
// standard selection sort
You want the list printed by the function
Colletion::Print to be sorted by last name (and first name if
the last names are equal).
- Where should you put the code that calls the sort function and
what does the call look like?
- What changes do you need to make to the code in  
people.cpp so that
calling the templated sort function will work? The code for the sort
is shown here:
template
void SelectSort(apvector & a, int size)
// precondition: size = # of elements of a
// postcondition: a is sorted
//
// standard selection sort
{
int j,k,min;
for(j=0; j< size-1;j++)
{
min = j;
for(k=j+1; k
- Is it best to call the templated sort function or to write a
non-templated, private member function sort that is called at the
appropriate time?
- If you want to sort by name, but allow the user to also sort
by ID number, what can you do? What would you like to be able to do?
Be specific here, decide how to allow the user to choose and how
you'll implement sorting by two different criteria. You don't need
to write the sorts, but you need to sketch where they're
written/called, and how you'll sort by two (or more) criteria.
- What about searching on other criteria (e.g., by first name
instead of last name) --- what issues arise in trying to implement
different searches?
We'll discuss methods for sorting by different criteria using
templates in standard and advanced ways. We'll also discuss issues
in searching and collecting.
Using Templates to Sort
We'll look at how templated functions are used to sort.
The functions whose prototypes are in
sortall.h and which
are implemented in sortall.cpp
are canonical representatives of templated functions --- they use
a templated vector --- the kind of element in the
vector determines the "real code" that is
emitted when one of the templated functions is instantiated. The
function Swap, reproduced below, is also typical of templated
functions:
template
void Swap(apvector & v,int j, int k)
// precondition: v[j] references value A, v[k] references value B
// postcondition: v[k] references value B, v[k] references value A
{
Type temp = v[j];
v[j] = v[k];
v[k] = temp;
}
In the case of Swap, the template parameter Type must
support assignment. It would be illegal, for example, to try to swap
two streams. If you do this in Codewarrior, for example, the error
message below appears indicating that the assignment operator for
streams is not public, hence streams cannot be swapped.
Error : illegal access to protected/private member
sortall.cpp line 24 v[j] = v[k];
Error : illegal access to protected/private member
sortall.cpp line 25 v[k] = temp;
In general, it can be difficult to ascertain only from error messages
why a template instantiation fails since the error appears in the
templated function, NOT in the instantiation which actually causes
the error.
As documented in the header file for
 sortall.h, elements being sorted must be comparable
using the less-than operator <, but for merge and quick sorts the
operator <= is used. We'll discuss alternatives to overloading
operators using classes that work like function objects. These
are shown in  dosort.cpp.
We'll discuss how function objects work --- then you should do the
following group problems by writing code or struct/class declarations.
Put solutions to all the problems on transparencies.
- Sort words by length of word so that shorter words come
first. Do this by writing a struct called LengthSorter and
show where/how it's called.
- Sort words so that all words that begin with vowels come before
words that begin with consonants, but within the vowel/consonant groups
words are sorted alphabetically. Assume the function isvowel
whose header is below exists:
bool isvowel(char ch)
// postcondition: returns true iff ch is a vowel (upper or lower case)
- Modify the class Collection
in  people.cpp by adding
a member function Collection::Sort. Calling this funtion
should result in the names stored in the collection being sorted in
alphabetical order. How will you do this? What alternatives are there?
How would you give the user the option of sorting by id number or by
name?
Template Day, Afternoon
In the afternoon we'll look at templated classes. We'll use
the Collection class we used in
 people.cpp, but
modified to support access by client code to all the elements in a
collection one-at-a-time. This code is found in
 people3.cpp. These
iterating functions are used in the function
PrintNamesOnly, and in the templated function
Search. Look over the code and ask questions. Answer the
questions below, too.
- Why are iterating functions needed --- why can't client code access
individual elements directly? What alternatives are there to iterating
functions (think about the apstring and apvector classes).
- What is the return type of the member function
Collection::Current, why?
- How could the member function Collection::Print be
rewritten to use the iterating functions. Should it be rewritten? Why?
- Add code/classes/structs so that the user can enter two number, and
everyone whose id number is between the two user-entered numbers is
found and stored in the collection matchGroup. Try to use
the function Search.
-
Implementing a templated class
You'll work on implementing a templated class for storing sets ---
collections with no duplicates. The eventual goal will be to write
code like the two programs illustrated below. The first counts
the unique words in Shakespeare's   Romeo and Juliet, i.e.,
it counts each word that occurs in the play once:
#include
#include
#include "apstring.h"
#include "strutils.h"
#include "apset.h"
int main()
{
apstring filename = "c:\\data\\shakes\\romeo.txt";
apstring word; // word read from file
ifstream input;
apset wset;
input.open(filename.c_str());
while (input >> word) // reading word succeeded
{
ToLower(word);
wset.add(word);
}
cout << "total # unique words: " << wset.size() << endl;
return 0;
}
To more fully use the set functions, you'll implement
a set class that can be used as in
 shakeset.cpp to
count the words in several of Shakespeare's plays including the words
in common to all plays (the intersection) and every word that occurs in
some play (the union). A run of the program is shown below:
reading c:\data\shakes\hamlet.txt
read 31956 words, non-unique = 7234
union size: 10832
intersection size:2297
reading c:\data\shakes\errors.txt
read 16201 words, non-unique = 3721
union size: 12508
intersection size:1186
reading c:\data\shakes\macbeth.txt
read 18232 words, non-unique = 4813
union size: 14747
intersection size:892
reading c:\data\shakes\errors.txt
read 16201 words, non-unique = 3721
union size: 14747
intersection size:892
reading c:\data\shakes\allswell.txt
read 24372 words, non-unique = 5336
union size: 17016
intersection size:781
First, as a group, determine what member functions and operations the
class apset should have. Don't worry about
implementation details, just the member functions (or non-member
functions) that you think should exist to support a good set
abstraction.
Make a list of the functions you think should be included. When you're
done with the list, try to rank the three or four functions you think
will be hardest to implement.
As you move to an actual implementation you'll need to make decisions as
to how to implement the templated class. You'll do this in lab, working
an a class apset that can be used in the program
 shakeset.cpp. Here
are some rules to follow as you move towards an implementation:
- Implement a non-templated class first. It will be much easier
to work out bugs with a non-templated version, and much easier to
convert a working class into a working templated class. Do
not ignore this advice. When implementing the non-templated
version of a class, don't use a built-in type like int or double, use
a class like apstring as the kind of item stored in the
templated class.
- Develop a test plan so that you implement a core of working
functions first. Dont' try to implement the entire class and then
test. Build a robust and complete class slowly, by adding to an
increasingly more complete class with each step. Test using small,
well-thought out cases, not the complete works of Shakespeare, for
example.
- When you've completed the non-templated version of the class,
make it templated: fix the .h file (relatively simple) and the .cpp
file (a little more complex). Test with a few different types of
element so that multiple versions of the class are instantiated.
Complete versions of an apset class using unsorted vectors to
store elements are in apset.h and apset.cpp. This implementation is extremely
slow, contrast it with the the binary search tree implementation of the
class in apset3.h and apset3.cpp.
In the current version, the function interHelp uses an inorder
traversal which leads to a degenerate tree (like a linked list) for the
result of the intersection. In the workshop this was shown to
participants, they were asked to reason about why the tree is bad/time
is slow, and to think about which of pre-order and post-order traversals
would be better alternatives to the inorder traversal shown.
A version is also accessible
that uses a sorted vector with binary search, the .h file is the same as
the original implementation, but there is a different .cpp file: apset2.cpp.
BigInt
We'll work on developing some ideas for using the BigInt case study
in both A and AB courses. As a first step, we'll look at some of the
more low-level C++ concepts including constructors, destructors,
assignment operators, promotion, etc, that can be seen when using the
BigInt class as shown below. After looking at these details we'll come
up for air and discuss some higher level concepts.
The run below shows  
bigfact.cpp using a version of the BigInt class
that is augmented to print a message each time a constructor or
destructor is called. This version has a copy constructor and an
assignment operator to illustrate all the things that happen when the
BigInt class is used. The augmented code is accessible in
 bigint.cpp.
Warning: do not ask your students to do this exercise, it isn't
necessary to trace every single call, but it is a worthwhile experience
for indepth knowledge of what's happening with C++. However, in my
experience it isn't worth covering the class in this kind of detail.
I can only hope that the AP test will not test this, and if it does, I'd
suggest skipping the question.
Find the line that calls every printed constructor, destructor,
assignment operator in the two runs below. For example, the first line
of output is caused when the local variable BigInt b in
main is constructed. The last line is caused when this
variable goes out of scope when main exits. The hexadecimal
number preceding each line of output is this, the address of
the object being constructed, destructed, or assigned to.
User-entered input in italics.
0x0012ff58 default constructor called
enter first last numbers for factorial: 3 4
0x0012ff24 int constructor called 1
0x0012fefc copy constructor called with 1
0x0012ff38 copy constructor called with 1
0x0012fefc destructor called for 1
assignment operator called with 1
0x0012ff38 destructor called for 1
0x0012fefc copy constructor called with 1
0x0012ff38 copy constructor called with 2
0x0012fefc destructor called for 2
assignment operator called with 2
0x0012ff38 destructor called for 2
0x0012fefc copy constructor called with 2
0x0012ff38 copy constructor called with 6
0x0012fefc destructor called for 6
assignment operator called with 6
0x0012ff38 destructor called for 6
0x0012ff78 copy constructor called with 6
0x0012ff24 destructor called for 6
assignment operator called with 6
0x0012ff78 destructor called for 6
3! = 6
0x0012ff24 int constructor called 1
0x0012fefc copy constructor called with 1
0x0012ff38 copy constructor called with 1
0x0012fefc destructor called for 1
assignment operator called with 1
0x0012ff38 destructor called for 1
0x0012fefc copy constructor called with 1
0x0012ff38 copy constructor called with 2
0x0012fefc destructor called for 2
assignment operator called with 2
0x0012ff38 destructor called for 2
0x0012fefc copy constructor called with 2
0x0012ff38 copy constructor called with 6
0x0012fefc destructor called for 6
assignment operator called with 6
0x0012ff38 destructor called for 6
0x0012fefc copy constructor called with 6
0x0012ff38 copy constructor called with 24
0x0012fefc destructor called for 24
assignment operator called with 24
0x0012ff38 destructor called for 24
0x0012ff78 copy constructor called with 24
0x0012ff24 destructor called for 24
assignment operator called with 24
0x0012ff78 destructor called for 24
4! = 24
0x0012ff58 destructor called for 24
(program terminates)
Here's another pair of runs, but the line that updates result in the
function fact is replaced by:
result *= k;
Notice how many fewer BigInt operations result. Explain these calls
too, then look at the questions that follow.
0x0012ff58 default constructor called
enter first last numbers for factorial: 3 4
0x0012ff34 int constructor called 1
0x0012ff78 copy constructor called with 6
0x0012ff34 destructor called for 6
assignment operator called with 6
0x0012ff78 destructor called for 6
3! = 6
0x0012ff34 int constructor called 1
0x0012ff78 copy constructor called with 24
0x0012ff34 destructor called for 24
assignment operator called with 24
0x0012ff78 destructor called for 24
4! = 24
0x0012ff58 destructor called for 24
(program terminates)
0x0012ff58 default constructor called
enter first last numbers for factorial: 11 11
0x0012ff34 int constructor called 1
0x0012ff14 int constructor called 11
0x0012fea0 copy constructor called with 3628800
0x0012feb0 int constructor called 0
0x0012fe78 copy constructor called with 3628800
0x0012fecc copy constructor called with 3628800
0x0012fe78 destructor called for 3628800
0x0012fe68 int constructor called 0
0x0012fe68 destructor called for 0
0x0012fecc destructor called for 3628800
0x0012fe78 copy constructor called with 36288000
0x0012fecc copy constructor called with 36288000
0x0012fe78 destructor called for 36288000
0x0012fe68 int constructor called 0
0x0012fe68 destructor called for 0
0x0012fecc destructor called for 36288000
assignment operator called with 39916800
0x0012feb0 destructor called for 39916800
0x0012fea0 destructor called for 362880000
0x0012ff14 destructor called for 11
0x0012ff78 copy constructor called with 39916800
0x0012ff34 destructor called for 39916800
assignment operator called with 39916800
0x0012ff78 destructor called for 39916800
11! = 39916800
0x0012ff58 destructor called for 39916800
(program terminates)
Questions
- Suppose that the local variable BigInt b is not defined,
but the output statement is changed to:
cout << k << "! = \t" << fact(k) << endl;
How will the output change for calculating 3 and 4 factorial using the
result *= k method?
- If the local variable BigInt b definition is moved inside
the for loop in main, how will the output change for 3 and 4
factorial using the result *= k method?
- How will the output change if the loop in fact is replaced
by the loop below (note that k is now a BigInt variable.
BigInt k;
for(k=1; k <= n; k += 1)
{
result = result * k;
}
- In the loop change above, why is k += 1 used instead of
k++?
- In the loop change above, will more or fewer
constructors/destructors be called if the parameter n is
changed to a BigInt variable?
Linked Big Study
For this part of the workshop we'll discuss what happens if a linked
list is used instead of a vector in implementing the class
BigInt. We'll discuss alternatives for the A course too, one
idea is to change the order in which digits are stored in the vector:
instead of storing the number 1,234 as the vector (4 3 2 1), i.e., 4 in
the location with index zero, what changes occur if 1,234 is stored
as the vector (1 2 3 4)? What happens to the running times of the
arithmetic operations? Why? How would you verify your hypotheses?
We'll first engage in a paper-and-pencil debugging exercise. I claim
that using two other people and the code on paper will find the bug here
faster than individuals who use a computer. If anyone would like to try
to prove/disprove this claim we'll make arrangements.
The code in   linkbig.h
and   linkbig.cpp uses a
singly-linked list without a header node to implement a class
LBigInt. The only changes to the code from the original
BigInt class are in the functions listed below:
- all constructors, e.g., default, from int, from string, copy
- destructor, assignment operator
- private helper functions: GetDigit, ChangeDigit AddSigDigit, Normalize
When the program  linkbigfact.cpp is run
as it's given in the listing, the output is correct as shown below:
enter first last numbers for factorial: 1 7
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
However, if the for loop runs down from last to first,
i.e., the commented-out for loop is used instead, the output is incorrect
as shown below:
enter first last numbers for factorial: 1 7
7! = 5040
6! = 5720
5! = 5120
4! = 5124
3! = 5126
2! = 5122
1! = 5121
However, if the same downto for loop is used, but the variable
BigInt b is printed instead of BigInt a, then the
output will be correct.
You are to find the bug that causes this problem. As an aid in finding
the bug, there is a comment in the copy constructor that indicates
that swapping only the lines below in
terms of which is commented out, will yield a correctly
running program.
while (rtemp != NULL)
// for(int k=1; k < rhs.myNumDigits; k++)
As a further aid, if the definitions of local variables
LBigInt a,b are moved inside the for loop in main, the
output will be correct.
When and if you find the problem, you may be able to come up with some
ideas for optimizing the use of nodes. We'll discuss these. We'll also
discuss why arithmetic operations are much slower using linked lists and
how you might speed them up.
BigInt Lab
For the lab, you'll take the BigInt code modified to use linked lists.
Your goal is to minimize the number of times new is called, this will
make the program faster. You'll also try to optimize successive calls
to the helper functions LBigInt::GetDigit and
LBigInt::ChangeDigit so that if they're called
with index values in order, e.g., 0, 1, 2, 3, then each successive call
is O(1) instead of O(index). To do this optimization you'll need to
use static local variables which aren't part of the AP C++ subset, so
you may want to skip it.
To minimize the use of new, you can use a global variable defined in the
file  linkbig.cpp or you
can use a static variable in the BigInt class. You could use a global
stack, for example. Instead of calling delete in the destructor, for
example, you can push a node onto the stack. Instead of calling new,
check the stack to see if it's empty --- if not, pop a node instead of
calling new. You'll want to use a stack of pointers to nodes.
To time the differences in using this method, you'll want
to use the class SysTimer declared in
 systimer.h that's part of
the library you're using. Using this class, calculate some large
factorial values or raise a number to a power. We'll discuss changes
and results when we get together after lab.
Workshops, C++ subset, the future
With College and Highschool educators working together, we'll try to
develop materials that could be used in College Board (and other)
workshops. We'll also discuss potential future directions for the use
of C++ in the AP courses although there is no official imprimatur
associated with this workshop.
First we'll discuss issues of college credit and the similarity of AP
courses to college courses. We'll also discuss how to use classes in an
A course and how classes will be used on the exam (although on this last
item there's no inside information.)
We'll discuss classes and how they're used by looking at the 1998 exam
in C++. This can be found at the web site
http://www.cs.duke.edu/~ola/ap.html
, and is mirrored locally for the purposes
of the workshop: 1998 Exam in
C++.
We'll look at the questions that appear on the A exam. These are/should
be indicative of how classes will be used on the 1999 exam when C++ is
used for the first time. Look over the questions in groups of two/three
and ask if there are questions. Some questions to guide your inquiry
are given below:
- In question 1, the solution to the part A requires using
either myLength directly, or calling the member function
Length(). Which is preferable?
- In question 1, part B, a function intToDigit is provided
for students to call. If this wasn't provided, how would the problem be
solved? Should the function be provided? Why?
- What are the differences in the two coded solutions to Question 2?
Are there reasons to prefer one to the other?
Artifacts
We'll discuss issues and answer questions in a group, but we'll also
work on providing concrete, usable artifacts and resources for teachers
of AP courses and for those giving AP workshops. These resources will
be made available on the web.
In a group of two to three people, hopefully with college people
collaborating with high school people, come up with an artifact/resource
that will be useful to those involved with AP. This must be something
written, preferably in electronic format. It doesn't have to be in HTML
format, it can be in Microsoft Word, plain text, PDF, etc. If you
include code (and in many cases you will), please make sure the code
compiles and runs. This means you should provide driver programs for
any functions and classes you use.
Although it would be great if you finished something during this
workshop, it's not anticipated that you'll have a polished product.
Something more than a germ of an idea, but less than a full blown,
finished document would be great.
Suggestions for resources:
- Sample free response questions for practicing with students and
workshop participants.
- Small program ideas that will lead to discussions on designing
classes. This might involve a problem statement and suggested guidelines
for developing class-based and non-class-based solutions.
- Ideas for working in small groups as part of workshops or for
presenters to use in lecture, question/answer, etc., formats when giving
workshops.
- Core classes that might be useful in building a library of
classes. Header files and/or partial implementations could be provided.
- Anything else you think might be useful. Creativity knows no bounds.
Owen L. Astrachan
Last modified: Mon Aug 10 13:05:52 EDT 1998