CS400, Fall 2004. Assignment 1. Due in class, Friday, 3 September.

The purpose of this first assignment is simply to provide you with a snapshot of your programming ability now. Later in the course, you will develop or see programs for these same problems using the methodology that will be taught in the course. You will be able to see the difference between your programming ability now and then. Your grade depends only on your turning in the assignment, done to the best of your current ability. Please don't just look for a reference that has a desired program; try developing it yourself.

You may write the algorithms in the language of your choice, although I would rather see Java than C or C++. You need not read or print anything. Just write a sequence of statements to do the job.

1. Table of cubes. Given is an integer n, n >= 0. Write an algorithm that stores in int array b[0..n-1] a table of cubes. Thus, upon termination of the algorithm, the following holds:

for each i, 0 <= i < n, b[i] = i*i*i .

Here's the catch: your algorithm may not use multiplication, division, or exponentiation; only addition and subtraction. The algorithm should be as fast as possible, but we don't tell you what the order of execution time is.

2. Inorder traversal. Write an iterative (non-recursive) algorithm to produce the in-order traversal of a binary tree. We elaborate. Consider a finite binary tree t (say), which for our purposes is best defined recursively by

t = PHI                 or
t = (t.l, t.d, t.r)

where PHI denotes the empty tree, t.d is an integer, called the value of the root of the tree, and t.l and t.r are themselves binary trees. By #t we denote the number of nodes in tree t, which is defined recursively by

#PHI = 0
#(t.l , t.d , t.r) = 1 + #(t.l) + #(t.r)

We shall also be dealing with sequences of elements. The empty sequence is denoted by epsilon. Catenation of sequences and elements is denoted by juxtaposition. For a sequence S, #S denotes the number of elements in S. The inorder traversal in.t of binary tree t is a sequence of integers defined by

in. PHI = epsilon
in. (t.l , t.d , t.r) = in.(t.l)   t.d   in.(t.r)

Write an iterative algorithm for storing the inorder traversal of a given finite binary tree t in a sequence variable Z, thus truthifying R: in.t = Z. In writing the algorithm, you may use the above notation. You do not have to write classes and all that to define the data structure. For example, to store the left subtree of tree t in variable lt, use lt:= t.l (or, in Java, lt= t.l;).