Duke APCS Workshop, AB Course

Day 1, June 22

To get an idea of how classes can be used, we'll look at two programs that count the unique words in a text file and how many times each word occurs:

• words.p (Pascal version)
• words.cpp (C++ version, vector,nonclass)
• words2.cpp (C++ vector, classes)
• words4.cpp (C++, linked list, classes)

The program words.cpp uses a vector of structs (Pascal array of records) to track words. The program words2.cpp is a version that uses a class rather than the more Pascal-like version from words.cpp. As part of our discussion of AB topics, we'll be making changes to the words2.cpp program to make it use different data structures to store the words.

Several utility classes and functions are used in the words programs too, in particular, free (non-class) functions specified in the header files below:

• prompt.h
• strutils.h

A sample run of words2.cpp is shown below, user entered data is in italics (only the last part of the run is shown, the output is lengthy).

  prompt> enter name of file: y:\apcs\data\poe.txt
   ...

   1       would
   1       wringing
   2       wrong
   1       yells
   6       yes
   2       yet
   25      you
   8       your

   # of words = 809
   total words (non-unique): 2324
   total time for update = 0.83

In addition to these programs, two programs from the A workshop may be useful in comparing Pascal and C++: cheese.pas and cheese.cpp. These show how the languages are related, how control structures (e.g., while, if, switch) work in C++, and how using classes helps in designing programs.

As group exercises, work on the following problems:

1. In words4.cpp (and the other wordsX.cpp programs), the struct WordStat does not have a constructor or other member functions. Based on the code in cheese.cpp design appropriate constructor(s) for WordStat, and show where they would be used in words4.cpp.

2. show-me Rewrite the member function Update in words4.cpp so that new words are added to the front of the linked list, rather than added in alphabetical order. Do you think this will speed up or slow down the running time of the program?

3. What code needs to be changed in words4.cpp so that a (dummy) header node is used for the linked list pointed to by myList?

4. Using the struct function print from cheese.cpp as a model, write a function print for the struct WordStat. If there's an overloaded insertion operator << also (as in  cheese.cpp) where could it be used in words4.cpp?

Day 1, Morning Lab

Using the apgeneric project (with the ap library already linked to the project), load words2.cpp into the environment, and make it the program that will be run when the project is run. Run the program and time how long it takes on both poe.txt, shakespeare\romeo.txt, and melville.txt (all these files are in y:\apcs\data).

1. Much of the time in the WordList::Update function is spent shifting elements. Each shift requires a string and an integer to be copied from one array cell to another. You'll make shifting faster by using pointers to WordStat objects rather than the objects themselves.

   Use the save as option to make a copy of words2.cpp, call it words3.cpp. You'll then change the program to use pointers to structs rather than structs: Change the declaration of myList in the class WordList to

   apvector<WordStat *> myList; You should initialize all values in myList to NULL. You can do this with a a loop in the body of the constructor or (at least on some compilers) by using the definition myList(size,NULL) in the initializer list.

   Now you'll need to search for uses of myList[...] and change them as appropriate. For example, in the original version of word2.cpp you'll find (in WordList::Search)

   if (myList[mid].info == key) // found key, exit

   You'll need to change this to:

   if (myList[mid]->info == key) to dereference the pointer in myList[mid] and get to the object it points to. You'll make similar changes elsewhere, but do not change the assignment in the loop of WordList::Update myList[loc+1] = myList[loc]; this stays the same to copy pointers rather than objects. When your program works time it again on the same data files you used originally.

2. Load the program words4.cpp and save it as words4a.cpp. Time the program on a few data files, then make the change done in the group earlier so that new nodes are added to the front of the list rather than in sorted order. Retime the program.

3. Continue working on words4a.cpp, you may want to rename the program (save as) words4b.cpp. Modify the program so that each time a word is found (e.g., in WordList::Update), the found node is moved to the front of the list. The idea here is that frequently accessed words will be moved to the front of the list. You'll need to think about the best way to unlink a node i.e., you could alter WordList::Search to return a pointer to the node before the node being searched for, or you could find the node before with a loop if the search is successful.

Day 1, Afternoon Session

1. show-me We'll go over the 1998 and 1997 exam questions, and then you'll work on a solution to question 3 from the the 1996 exam in C++. You should write a solution to parts A and B of the question, and also find a big-Oh expression for the running time of your solution to the function IsBST from part B. Do the code as a show-me exercise. We'll use the big-Oh problem to motivate a brief study of recurrence relations as a good way of analyzing recursive functions.

2. Think about how to modify words4.cpp to use a binary search tree rather than a linked list. In particular, concentrate on the destructor and the member function Update --- to implement these you'll need to use private, helper member functions. This will be typical of using trees to implement other classes. You should try to write the destructor, and think about writing Update.

Day 1, Afternoon Lab

You should time your words5.cpp program and compare it to words6.cpp, a version of the program that uses a binary search tree.

Day 2, June 23

Day 2, Morning

For example, to turn stone into money, one possible ladder is (replace 't' by 'h', replace 'o' by 'i', etc.):

We'll explain the logic of the program in class, but it finds the shortest possible word ladder for any pair of words given a dictionary of words. Using a queue ensures that the ladder found is the shortest. A stack is used to print the ladder since the ladder is found "backwards".

We'll use the program to discuss different parts of C++ and the templated classes apstack and apqueue. In particular, we'll talk about how templated classes are compiled and how to design a templated class. Although we're using the wordladder program to help foster a discussion, this is the complete program of an assignment we typically give in our data structures course, although we provide the code to read the dictionary so that students can concentrate on the algorithm of finding the ladder.

You should work in groups on the following problems.

1. show-me Rewrite the Ladder member function print so that it is recursive rather than using a stack.

2. What changes are needed in member function findLadder so that a stack is used rather than a queue. What will this do to the ladder found? What do you think it will do to the running time?

3. show-me Sketch the design of a class Set (provide part of a header file set.h) for implementing sets, e.g., collections without duplicates. Make the class templated, and provide a few important member function names (with parameters as appropriate). How will you store items in the set? What are your options?

We'll discuss the possible implementations of the Set class, and how to overload operators. We'll leave groups to think more about the design and implementation of the class after we've talked about initial group designs. This will most likely mean that we won't have a morning lab activity today. if there is time, you should begin to implement the class Set.

Day 2, Afternoon, Lab

1. The first problem involves working with postfix expressions, the apstack class and the class BigInt from the C++ case study. The BigInt class is declared in the header file bigint.h.

   A run of postfixi.cpp is shown below, the program computes the value of integer postfix expressions. (when running, the end-of-input is signalled by end-of-file, which is control-Z on Windows machines, followed by a return. You may need to type the control-Z as the first character on a line, immediately followed by return.)

   
       prompt>  postfixi 
        12 8 * 22 + 
       result = 118
       99999 99999 * 
       result = 1409865409
   

   (why can't the last calculation be correct?)

   Load postfixi.cpp into the programming environment, add it to the apgeneric project, and run it a few times with good and bad (poorly formed postfix) expressions. Then use save-as to create a file file postfixb.cpp, modify it to use BigInt values rather than int values. For almost all applications, BigInt variables and values can be treated like integer values.

   When you have the program working for BigInt values, add an exponentiation operator ^ and use it to evaluate both 2 3 ^ (which should have the value 8) and to evaluate 2 200 ^ which is a large value. You'll need to implement a function to raise a number to a power to do this. Don't worry about efficiency, to calculate a^b just use a * a * a ... * a where a is multiplied by itself b times.

2. Implement a templated class apset. Initially, implement only the member functions below:
   • print (all elements, one per line)
   • contains (boolean, whether an item is in the set)
   • size (# elements in the set)
   • add (an element, no duplicates allowed)
   • makeEmpty (make the set contain no elements)

   You can use a vector of elements for the storage, or you can cut-and-paste code from words5.cpp or from words6.cpp. Use the code in the class apstack as a guide. You'll want to look at the apstack implementation too. As a start, we are providing apset.h.

   A run of a program that uses a set is shown below. This does the same thing as the wordX.cpp set of programs.

   int main() { apstring filename = PromptString("enter name of file: "); apstring word; // word read from file ifstream input; apset<apstring> wset; input.open(filename.c_str()); if (input.fail()) { cout << "could not open file " << filename << endl; exit(0); } while (input >> word) // reading word succeeded { wset.add(word); } wset.print(cout); cout << "total words (non-unique): " << wset.size() << endl; return 0; }

3. Re-implement the BigInt class but use linked-lists instead of an apvector. Time a simple program that raises numbers to a power, or some other calcuation, using both the apvector implementation and the linked list implementation. Which is faster? Why?

You can also check the lab activities for the A Workshop.

Wrap-up