Cluster 5 * Summer 2004
Computer Science Through Games and Scheme Programming
David G. Kay, Dan Frost, Kevin Papke

Scheme Lab Activities: Seventh Set

1. By this point, all of you should have games projects. You will naturally want to spend most of your lab time working on those projects. Still, you should devote Tuesday and Thursday mornings to these Scheme labs (at least until you finish them all--this one is the last).


2. Go ahead and finish up the non-optional parts of Labs 5 and 6.


3. In class on Monday we discussed binary search trees (BSTs). A BST lets us organize data hierarchically; that in turn lets us access the data--add items, find items, and so on--more quickly. Not just a little more quickly, but in a whole new category of quickness, as we saw on that comparison graph in class.


1. Do this part on pencil and paper. Starting with an empty binary search tree, add each of the following to the tree, in the order given: 314, 159, 265, 358, 979, 323, 846, 264, 338, 327, 950, 288. Remember the basic algorithm: If the value you're inserting is less than the root, insert the value into the left subtree; if the value you're inserting is greater than the root, insert the value into the right subtree. (If you want to see this in code, check out the file bst.ss.) Use a full sheet of paper and spread the first few nodes far apart so you have room for all the rest.


2. Now try it again, inserting the same numbers in this (different) order: 323, 265, 358, 159, 264, 288, 314, 950, 846, 979, 327, 338. Notice how the tree has a more balanced shape?


3. Try it one more time, with the numbers in sorted order: 159, 264, 265, 288, 314, 323, 327, 338, 358, 846, 950, 979. Are we always guaranteed, no matter what shape our BST is, to get the expected increase in performance?


4. To traverse a data structure (a list, a tree, whatever) means to visit every node. We need to traverse a structure if we want to print out every element, or apply any other kind of processing to every element. There's nothing interesting about traversing linear data structures like lists: We just start at the beginning hand handle every item in turn. (Or, we could start at the end and work backwards; in either case, we'd just be going in a straight line.) But traversing a hierarchical structure like a tree isn't quite so straightforward. In fact, there are at least four different ways to traverse a binary tree, each of which is useful in certain circumstances. We'll use the tree shown below as an example; note that it's a binary tree but not a binary search tree (because it doesn't maintain the BST property that everything to the left is less than everything to the right in each subtree).


1. Breadth-first traversal: Visit the root first, then everything on the next level, then everything on the third level, and so on. For our example tree, a breadth-first traversal visits the nodes in this order: H I E G F D A C B


2. Pre-order traversal: Visit the root first, then traverse its left subtree (using pre-order traversal), then its right subtree (using pre-order traversal). A pre-order traversal of the example would produce H I G F E D C B A.


3. Post-order traversal: Traverse the left subtree (using post-order traversal), then the right subtree (using post-order traversal), then visit the root. A post-order traversal of the example would produce G F I C B D A E H.


4. In-order traversal: Traverse the left subtree (using in-order traversal), then visit the root, then traverse the right subtree (using in-order traversal). An in-order traversal of the example would produce G I F H C D B E A. With a binary search tree, this produces an ordered list of the elements in the tree: Try it on the three trees you created above.


5. This part is optional for those of you who would like to explore binary search trees further


1. The file bst.ss contains Scheme code that implements binary search trees (with numbers as the values being stored).


2. Open the file in DrScheme and play around with it.


3. How would you change it to use strings as the value being stored? How could you refactor the number version and the string version to capture the common aspects of both tasks?


4. How could you use the bst.ss code with the restaurants program so that the restaurant collections would be implemented in a binary search tree instead of a plain list? Can you localize those changes so that they only occur in the part of the program that handles the collection?


4. You can create a stand-alone, double-clickable application from your restaurants code by choosing the "Create Executable" item from the Scheme menu in DrScheme. You'll need to have a call to (Restaurants) at the end of your code; this will start it up. (If you want to run this application on another machine, that machine will need to have DrScheme installed.) Try this with the Restaurants program or with one of your games.

COSMOS Cluster 5 Home * COSMOS UCI Home

Tuesday, July 27, 2004 -- 10:38 AM