CS/ECE 234  		Topics and Sample Test 3	4 Dec.

Ch. 8  Trees
Define a binary tree.
Explain the ADT named Binary Tree Node.
Explain the ADT named Binary Tree.
Distinguish between a binary tree node and a binary tree.
List the components of a toolkit for binary tree nodes.

Convert an infix expression to a binary tree as a human.
Convert an infix expression to a binary tree using stacks.
Simulate a stack based algorithm to construct an expression tree for an infix 
    expression.

Explain a tree traversal in your own words.
Identify 4 kinds of tree traversals.
Simulate a particular traversal of a binary tree.

Explain the ADT named Binary Search Tree.
Explain the ADT named Heap.
Explain the ADT named PriorityQueue.

Describe the application to build an index for a text file.

Ch. 10  Sorting
Describe the sorting method of Java.
Identify several common quadratic sorting algorithms.
Identify several common log-linear sorting algorithms.
Explain the partition algorithm.
Simulate the partition algorithm.
Explain the quicksort algorithm.
Simulate the quicksort algorithm.
Explain the mergesort algorithm.
Simulate the mergesort algorithm.
Explain the heapsort algorithm.
Simulate the heapsort algorithm.
Distinguish between a quadratic and log-linear time.
Explain the shell sort algorithm.
Explain the connection between insertion sort and shell sort.
Simulate the shell sort algorithm.
State the order of each sort algorithm.

Explain the divide and conquer heuristic in your own words.
Design an algorithm for a particular problem using the divide and conquer 
    heuristic.

Ch. 12 Self balancing search trees
Describe the impact balance has on the performance of a binary search tree.
Define the ADT red black tree in your own words.
Explain the insertion algorithm for a red black tree.
Explain the deletion algorithm for a red black tree.
Define the ADT 2 3 4 Tree in your own words.
Explain the insertion algorithm for a 2 3 4 tree.
Explain the deletion algorithm for a 2 3 4 tree.
Describe the connection between a 2 3 4 tree and a red black tree.
Define the ADT B Tree in your own words.
Describe the connection between a 2 3 4 tree and B tree.
Explain the insertion algorithm for a B tree.
Explain the deletion algorithm for a B tree.
List the performance characteristics for a B tree.
Count the maximum number of keys in a B tree of depth d and order N.
Count the minimum number of keys in a B tree of depth d and order N.

Labs
Describe a grammar for an arithmetic expression.
Document the role of recursion in the grammar for an arithmetic expression.
Describe the square list ADT.  
Design the insert method for a square list ADT.

CS/ECE 234	Sample Test 4
Answer all problems.  Show all work.

0a. Describe the shell sort algorithm in technical detail.
 b. State the order of the shell sort algorithm.

1a. Describe the partition algorithm used in the quick sort algorithm.
 b. Use a table to simulate the partition algorithm with the letters of 
	   JOHNBAPTISTE.  
    Briefly explain your work.

2a. Describe the ADT 2 3 4 tree.
 b. Simulate the add() method for a 2 3 4 tree for
                15 16 1 17 13 32 14 21 22 31 25 51 33
    Draw at least one picture for each add() operation.
    Briefly explain your work.

3a. Describe a grammar for an arithmetic expression.
 b. Document the role of recursion in the grammar for an arithmetic expression.
 c. Modify the grammar to include functions such as sin(), cos(), tan(),
    e^() and ln().  Explain your changes.  Explain why your changes are correct.
 d. Describe impact part c has on your code for lab 5.  Include technical 
    details.