Lecture 21 - November 5, 2007

If you didn't finish any of the three programs I was expecting, please do so ASAP and submit electronically BEFORE 5pm on Wednesday

• Redo of Linked List Queue Implementation
• ( with all functions from original specification and user defined exceptions
• Josephus
• redo of Sort program
• (with modifications specified)

I will not be in class on Wednesday.

Instead of class you will have an assignment that needs a computer

The assignment must be done in pairs (two people - one submission)

The assignment will become available at 5pm on Wednesday

It must be submitted by 7pm

Today we wrote a recursive function to multiply two numbers together.

Here is the function we came up with

with ada.text_io;

with ada.integer_text_io;

procedure testMultiply is

result : integer;

function mTimesn(m, n : natural) return natural is

begin

if (n = 0) or else (m = 0)then

return 0;

elsif (n = 1) then

return m;

elsif( m = 1) then

return n;

else

return m + mTimesn(m, n-1);

end if;

end mTimesn;

begin

result := mTimesn (5,0);

ada.integer_text_io.put (result);

ada.text_io.new_line;

result := mTimesn (0, 23);

ada.integer_text_io.put (result);

ada.text_io.new_line;

result := mTimesn (5,4);

ada.integer_text_io.put (result);

ada.text_io.new_line;

result := mTimesn (5,1);

ada.integer_text_io.put (result);

ada.text_io.new_line;

result := mTimesn (1,17);

ada.integer_text_io.put (result);

ada.text_io.new_line;

end testMultiply;

Here are some questions you should be able to answer about the function:

· Why did we declare the parameters and the return value natural?

· What is the behavior of the or else in the test for 0?

· Why couldn't we use an or else in the test for 1?

· How could we re-write this code so that it would work if the parameters and the return value were of type integer?

We talked about how we could write a recursive function to print out the elements in a linked list in reverse order.

• You should be able to write one

We talked about binary trees which are trees in which every node has at most two children.

We talked about traversing binary trees in three different ways using a

• pre-order traversal
• in-order traversal
• post-order traversal

We represented an expression using a binary tree and we saw how we would write it using

• prefix notation
• infix notation
• postfix notation

We noted that the order of the operands doesn't change only the placement of the operators does.

We noted that infix notation requires parentheses to indicate evaluation order

We indicated that if we used recursion, the traversals were simple

Pre-order

• "process the root"
• visit the left subtree
• visit the right subtree

In-order

• visit the left subtree
• process the root
• visit the right subtree

Post-order

• visit the left subtree
• visit the right subtree
• process the root -- by printing it

We pointed out that processing the root might be printing it.

We then remembered that the key to doing a binary search was our ability to repeatedly divide the list in half.

We then defined a special binary tree called a binary search tree which is a binary tree in which all of the values in the left sub-tree are less than the value in the root and all of the values in the right sub-tree are greater than the values in the root. We noted that the left sub-tree and the right sub-tree are themselves, binary search trees.

We then built a binary search tree by going around the room and collecting integers to place in the tree from each student.

We then walked through a search of the tree.

We than determined that an in-order traversal of the tree would enable us to print out the values in the tree in ascending order.