AP Computer Science Workshop, Berkeley, 1998

1. 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).

2. 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

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:

1. 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.

2. 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 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.

1. 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.

2. 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.

3. 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.

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

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

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

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

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 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.

1. 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?

2. The Person struct has a member function Print, and operator << is overloaded for the struct too. How are these part of the AP subset?

3. In the function Print, the function tolower and the iomanipulator setw are used --- are these parts of the APCS subset?

4. The private field myList is grown by doubling in size, is this a good idea? (see Collection::Add)

5. Why is the variable Person p defined inside the first while loop in main rather than before the loop?

6. A while(true) loop is used in main --- what's an alternative and which is the best approach?

Sorting

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).

1. Where should you put the code that calls the sort function and what does the call look like?

2. 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 <class Type> void SelectSort(apvector<Type> & 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<size; k++) { if (a[k] < a[min]) { min = k; } } Swap(a,min,j); } }

3. 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?

4. 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.

5. 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

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.

1. 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.

2. 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)

3. 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

1. 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).

2. What is the return type of the member function Collection::Current, why?

3. How could the member function Collection::Print be rewritten to use the iterating functions. Should it be rewritten? Why?

4. 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

     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.

1. 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.

2. 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.

3. 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

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)

     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

1. 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?

2. 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?

3. 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; }

4. In the loop change above, why is k += 1 used instead of k++?

5. 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

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

enter first last numbers for factorial: 1 7
1! =    1
2! =    2
3! =    6
4! =    24
5! =    120
6! =    720
7! =    5040

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

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

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:

1. In question 1, the solution to the part A requires using either myLength directly, or calling the member function Length(). Which is preferable?

2. 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?

3. What are the differences in the two coded solutions to Question 2? Are there reasons to prefer one to the other?

Artifacts

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:

1. Sample free response questions for practicing with students and workshop participants.

2. 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.

3. Ideas for working in small groups as part of workshops or for presenters to use in lecture, question/answer, etc., formats when giving workshops.

4. Core classes that might be useful in building a library of classes. Header files and/or partial implementations could be provided.

5. Anything else you think might be useful. Creativity knows no bounds.