Computer Science 257

Programming Workshops




Publisher's Source Code

Source code from Carrano, Helman, and Veroff can now be reached from this index.


Final Exam!
Friday, 14 Dec 2001, 2 pm


Tables
Tuesday, 11 Dec 2001


Tables
Thursday, 6 Dec 2001


Tree Day! Whoop-Tee-Doo! Show Me Your Trees!
Tuesday, 4 Dec 2001

What a saga! And you thought trees only grew outdoors. Today is Demo Day for trees of the electronic variety.

Here are a few hints to get everyone across the finish line.

Once you get into the swing of things, you come to appreciate the fact that we are mainly involved in an (admitedly rather elaborate) code transformation exercise with certain very definite patterns. Here are a few of those patterns:

Plain Vanilla Version Template Version
ptrType DelPtr treeNode<T>* DelPtr
ptrType& NodePtr treeNode<T>*& NodePtr
treeItemType& TreeItem T& TreeItem

Therefore, the following code snippit

void bstClass::ProcessLeftmost(ptrType& NodePtr, treeItemType& TreeItem)

transforms into

template <class T>
void bstClass<T>::ProcessLeftmost(treeNode<T>*& NodePtr, T& TreeItem)

If you still have quite a way to go in your own particular binary tree project, you might prefer to complete the following example which successfuly incorporates all of the elements of this series of binary search tree exercises. This code by Ms. Clarkson builds a student record-keeping system as a templated binary search tree. Here, the BST class inherits its basic treeness from the BT class, and everything in sight is templated. It remains only to apply transformations such as those indicated in the table to the file bstClass.h. Cheers!

... and here is an even better hint: a working program!!



Tree Workshop
Thursday, 29 Nov 2001

Freeform exercises from the high diving springboards and bungi platforms involving templated binary search trees.


Tree Workshop
Tuesday, 27 Nov 2001

Freeform floor exercises involving templated binary search trees.


Templated Binary Search Trees
Tuesday, 20 Nov 2001

This exercise is the third and final step in our series of three programming projects dealing with binary search trees. This morning's project achieves the final level of abstraction and sophistication by having binary search trees inherit all of their basic functionality from the binary tree parent class, and by templating both classes so that the same code can build trees with nodes taken from any appropriate class.

This is a major consolidating project. Understanding it well will require a firm grasp on almost all of the C++ programming and modeling skills we have been building all semester long. Enjoy!

templateBST, exercise 29, page 511, and exercise 34. page 512


Binary Search Trees
Thursday, 15 Nov 2001

Today's exercise is the second in our series of three programming projects dealing with binary search trees. This morning's project leverages our work on binary trees to implement binary search trees.

searchTreeReplace, exercise 16(a, c, d), page 508


Binary Trees
Tuesday, 13 Nov 2001

Today we will start a series of three programming projects dealing with binary search trees. This morning's project gets the ball rolling by implementing binary trees.

binaryTreeADT, exercise 10(a, b), page 507


Algorithm Efficiency and Sorting
Thursday, 8 Nov 2001

Today we will work on two programming projects: traceSort and zooSort. Both projects provide important oportunities to reuse previously developed software, yet each project extends previously developed functionality in new directions.

Each of the sorting algorithms studied in Chapter 9 has a sort of "personality" all its own. Each generates recognizable patterns in the data movements it generates while carrying out its particular sort. The project traceSort attempts to expose these patterns by asking you to develop a program which generates as input a random list of 10 integers selected from the range 0..99, and then sorts that same list using selection sort, bubble sort, insertion sort, merge sort, and quicksort. Each time an element in the list is moved by any sorting algorithm, the resulting new list is printed out. Thus each sorting algorithm generates a trace of its operations on the data. Your program should create an attractive display of these traces. Can you capture in words some of the patterns you see?

Create a database of ten zoo animals. For each animal in the zoo, the database should contain the animal's name (one word), age, and weight. One entry in such a database might be penguin 3 1.2 indicating that the zoo's penguin is three years old and weighs 1.2 kilos. Keep the original database in a flat text file. Write a program which sorts and displays that same database in three ways: (1) alphabetically, by the animal's names, (2) by age, and (3) by weight. Your program must create a single C++ record for each animal, and then sort on the various fields of the records.

Here is a program which generates the sort of comparisons discussed in Ms. Clarkson's notes for today:


Exam II
Tuesday, 6 Nov 2001

Exam II covers the material in Chapters 6, 7, and 8.


OOP Demo Day!
Thursday, 1 Nov 2001

In-class demonstrations of four programming exercises from Chapter 8:


OOP Workshop -- Chapter 8
Tuesday, 30 Oct 2001

There is much to do in chapter 8. Here are the major topics and what we are to do for each topic:


OOP
Thursday, 25 Oct 2001

Here is the code for the last of our exercises from Chapter 8. See Ms. Clarkson's notes for today for a description of this "Class Project."


Class Relationships
Tuesday, 23 Oct 2001

This morning is dedicated to a number of important concepts from Chapter 8:

Let's start with a simple example illustrating public inheritance and static binding of member functions:

In this micro-world, balls are spheres that have names. We model that behaviour by creating a class, sphereClass, which captures some of the meristic characteristics of spheres, and then creating a derived class, ballClass, which inherits the characteristics of spheres and adds member functions which manipulate the names of balls. The inheritance is public.

We now modify that example to illustrate virtual functions and late binding. The Area member function of a sphere calculates the surface area of a sphere, but the Area member function of a ball calculates the cross-sectional area of a ball. One of these numbers is 4 times the other. We have in mind that Area when called on a sphere will return surface area, but when called on a ball will return the cross-sectional area. This first attempt to achieve the desired behaviour is incorrect. It uses static binding, and hence cannot distinguish between balls and spheres at runtime. Since SPtr is defined as a pointer to an element of sphereClass, and since the binding is static, any call to run the Area member function of the object pointed to by SPtr will invoke a sphere's Area member function.

To achieve the correct behaviour, we must signal the compiler that we wish to use dynamic binding, so that the appropriate version of the Area member function is invoked, according to the datatype of the object actually pointed to by SPtr at the time of invocation. Our text indicates how to accomplish this simply by typing the word "virtual" into three places in the above code. Make the three changes indicated on page 358 of our text and verify that the resulting virtual member functions now exhibit late binding. If SPtr happens to point to a sphere, SPtr->Area() will return surface area, but if SPtr points to a ball, SPtr->Area() will return cross-sectional area.

Templates provide a way for classes to accept other classes as parameters. For instance, one can create lists of items to be taken from some as yet unspecified generic data type, and only later on instantiate that datatype to obtain, say, lists of integers or lists of strings or lists of records. All of this is achieved at the cost of only a little baroque notation decorating the specification of the target classes.

Unfortunately, templates are not quite standardized in the programming community, so different compilers may want source code files to be arranged somewhat differently. Here are some hints for three important compilers and platforms:

Finally, let's look at an example involving an overloaded operator. See today's notes by Ms. Clarkson for details.

After working through all of those illustrative examples, we can settle down to today's programming exercise. Complete Exercise 9, on page 387 (stack only). This exercise asks us to overload the assignment operator (=) for the pointer-based implementation of stackClass. The authors hint that we should study copy constructors.


Project Demonstration Day!
Thursday, 18 Oct 2001

This morning is brought to you by Set ADT's!

Tomorrow is Mid-Semester, and mid-semester grades are due in the Registrar's office on Monday morning, so this morning is a great oportunity to demonstrate your Set ADT project and any remaining old work left over from the previous class.

There is much to do in chapter eight. We will close in on the very powerful concepts of public and private inheritence, abstract base classes, virtual functions, and parameterizing classes via templates. All of this material lies at the core of modern object-oriented programming. To get a solid start on these constructions we will begin two exercises this morning:


Homework Demonstration Day!
Thursday, 11 Oct 2001

Yup. Here's a checklist:


Queues -- and a new Programming Project!
Tuesday, 9 Oct 2001

This morning's project is to implement the Queue ADT described in Chapter 7, and then to add to your implementation the enhancements described in Exercises 5 and 7 of Chapter 7, page 337 (QueueDelete and two versions of Display).

This morning we also begin to consider a brand new Programming Project: implement the Set ADT. There is a detailed description and instructions for this project in Ms. Clarkson's web pages. Go to her syllabus page, and click on October 18th, "Pledged Program I is Due." The project is due at the beginning of class, 8 am, on October 18, 2001. You will be asked to demonstrate your project during that class. Here are some helpful files:


An Application of Stacks: Implementing a Calculator
Thursday, 4 Oct 2001

This morning's project is to modify the calculator program from chapter 6 so that it handles the exponentiation operator. Use the symbol ^ for exponentiation. Also, complete the function named correct() in the calculator program. It appears in today's code only as a stub. Links to the bulk of the necessary code appear below. See Ms. Clarkson's web pages for additional details.


Stacks
Tuesday, 2 Oct 2001

Stacks are lists with a distinctive protocol. Implement DisplayStack from Chapter 6, Exercise 3, page 294, and ~Stack from Chapter 6, Exercise 13, page 296.


Exam 1
Thursday, 27 Sep 2001

We'll have an exam in class today, covering chapters 1, 2, 3, and 4.


Pointer-based Sorted Lists
Tuesday, 25 Sep 2001

Consolidate your understanding of pointer-based dynamic lists by writing solutions to the programming projects described in Programming Problems 1a, 1b, and 2, on pages 211 and 212. Your solutions should be accompanied by client programs which thoroughly test all of the functionality of your implementations. Be ready to demonstrate all of your linked list programs to the instructor in class today. Here is a checklist:


Manipulating Linked Lists
Thursday, 20 Sep 2001

Write a function which solves exercise 4 on page 209, DeleteLargest. Then write a program which generates appropriate tests of your function.


Linked Lists
Tuesday, 18 Sep 2001

Implement a pointer-based implementation of the List ADT. Write a client program which thorougly tests your implementation. Add the operations SaveList and RestoreList to the pointer-based implementation of the List ADT, as described in Exercise 15 on page 211. This adds new functionality to our List ADT: one can now save a dynamic list to a file and regenerate it from a file. Of course, the pointers are not saved to a file, only the data. Appropriate pointers are generated anew when the data comes off the file on restoring the list.


Homework Demonstration Day!
Thursday, 13 Sep 2001

Yup. Here's a checklist:


Data Abstraction: The Walls
Tuesday, 11 Sep 2001

Our textbook's subtitle is "Walls and Mirrors." This morning we will work with the walls: encapsulation.

As a warmup exercise, study, compile and run the program about spheres on page 133. There is a header file on page 129, an implementation file on page 132, and a client ("using") file on page 133. The electronic versions of the associated source code can be found in the Carrano files "c03p129," "c03p132," and "c03p133." Move them into a directory named "sphere" and cd into that directory. Use the mv command to give these files more meaningful names, such as "sphereClass.h," "sphereClass.cpp," and "useSphere.cpp." Compile them under g++ with a command such as

  g++ -o sphere useSphere.cpp sphereClass.cpp

Run the resulting executable file sphere with

  ./sphere

The "./" means "in the current directory." You won't have to specify that if your bash PATH variable ends with a period, since in the jargon of command shells a period indicates the current directory. This variable is defined in the file ".bash_profile" in your home directory. You can edit that file to customize your working environment to some extent.

Now create a new directory named listA and use it to compile and run the array-based list program on pages 136-139. The text will make frequent reference to this key program.

Now we are ready for today's programming exercises: (1) Exercise 1 on page 142 (integerListSum), and (2) Programming Problem 5 on page 145 (sortedListADT). In both cases, use a typedef statement to define listItemType to be int. You will want to include a well-designed client file which you can use to demonstrate your solutions in class. As always, clarity, elegance, and precision are keys to success. Enjoy!


Programming with g++
Thursday, 6 Sep 2001

Field trip! Our first excursion -- to the new Linux Lab in WL131, where we will learn to program with g++ and emacs. See the web page getting started with linux for a list of some of the most frequently used commands and software for programming in a Linux environment. This lab contains Linux, PC, and Macintosh computers, and is open 24 hours a day, 7 days a week, so you can program to your heart's content.

Our textbook's subtitle is "Walls and Mirrors." This morning we will work with the mirrors: recursion. As a warmup exercise, write a program which uses the factorial function and both recursive and iterative versions of a program which writes strings backwards, all from chapter two. You may find it convenient to download electronic versions of all of the text's programs from the publisher's web site. As today's programming project and homework assignment, write solutions to exercises 3, 4, and 5 on page 99 (sumOfIntegers, writeBackward, and integersUptoN).


Modelling in C++: bridgehand
Tuesday, 4 Sep 2001

How did you do on the programming assignment? What language did you program it in? Well, you're going to tell me C++ because the word "cout" appears somewhere in your code. But did you use the word "Class" anywhere? If not, you were programming in C. One of our goals this semester is to raise our computer science skills to the next level. We want to go from programming to modelling, from C to C++. As a step in that direction, reconstruct your solution as an object-oriented program. Just to impose some level of coherence on this morning's discussions, write the supporting files necessary to accompany this main program: bridgehand.cpp

To complete our review of C++ programming, write solutions to programming exercises 2, 3, and 11 on pages A62 and A63 of Appendix A (qualityPoints and merge). See the explanatory notes on the course web pages for today. These solutions and your final solution to the bridgehand problem are due on Thursday. You may be asked to demonstrate one or more of your solutions in class on Thursday.


Programming in C++: bridgehand
Thursday, 30 Aug 2001

Welcome to Data Structures!

This morning we will address two main tasks: (1) familiarize ourselves with these new computers and with the Visual C++ programming environment, and (2) refresh all those C++ memories which may have faded into the background over the Summer. We will accomplish both of these tasks at once by attacking a programming project: design and code a C++ program which calculates the value of a bridge hand. There is a detailed specification of this program in our text (Programming Problem 2, page 47). Your program should read its data from a file, and should produce as its output a display similar to the one shown in the statement of the problem.


cparrish@sewanee.edu