Back to CS211 home

Lab Sheet 9

Sit back, and enjoy the movie..."The Towers of Hanoi"

What did you think of that? Interesting? Boring? Too complicated? Try to get your head around the recursion... It's the same principle as searching a tree recursively. First of all decide what terminates your recursion (usually something trivial such as a NULL value, or zero, or 1). Then walk through one or two of the simplest examples with some real data values, and try to come up with a general scheme. Chances are if it works in the trivial case and it works for one other nontrival case then it is correct.

Implement the Towers of Hanoi program (99% of the code is in the slideshow). Plot a graph of inputs 1 to 13 against number of seconds to complete writing the solution to the screen. (If you don't know how to plot a graph, ask someone who has done high school physics, they'll show you!) Find out how long it will take to run for an input of 20, 25, and 30.

One credit will be awarded for a neat graph of data points 1 to 13.

For the second half of this lab you will learn about hash tables. You were already given a flavour of them at the beginning of the course. Read the hash table handout and implement the simple program described below.

Problem 9.1 Design and write a simple hash table class to store 10 ISBN numbers. For the purposes of this assignment assume that ISBN numbers are strings of 10 characters. You will need a class to describe each node of the hash table (containing a string or character array ISBN number as the key) and a class to maintain an array of such nodes. Methods in this latter class should include adding to the hash table, printing the hash table, and checking if the hash table if full. Define a hash function of your own (it can be anything you like!).

To help you along, here is a possibility for the first class:
const int ISBNSize = 10;
const int TitleSize = 50;

class HTableNode {
 public:
  char isbn[ISBNSize]; // the key
  char title[TitleSize]; // name of the book
};

One credit will be awarded for pencil & paper algorithms for Problem 9.1.

End of Lab Sheet