Solutions to CS 12 Assignment 4, part 1, Fall 2008
Adapted/extended from textbook's solutions package by cmc, 11/11/08

a. 6.3 Review Questions 1 and 2

1. Constant - O(1)
   Logarithmic - O(log n)
   Linear - O(n)
   n log n - O(n log n)
   Quadratic - O(n^2)
   Cubic - O(n^3)
   Exponential - O(c^n), where c > 0 is a finite constant.

2. No, the complexity class tends to give useful comparative information
   only when the input size of the algorithm is comparatively large.

b. 9.2 Review Questions 1, 2, 3 and 4

1. (a) R, T
   (b) X
   (c) X, Y, Z
   (d) T

2. The root node in a tree is the only node having no ancestors.

3. A leaf.

4. There is one and only one path from the root node R in a tree to
   any given node N that is a descendant of R.

c. 9.6 Exercise 1

PreOrder Traversal: R S X Y Z T U V W
InOrder Traversal: X S Y Z R U T W V
PostOrder Traversal: X Z Y S U W V T R
LevelOrder Traversal: R S T X Y U V Z W

d. 11.4 Review Questions 1, 2 and 5

1. Two keys K1 and K2 (where K1 != K2) are said to collide in a hash
   table T if they have identical hash addresses h(K1) = h(K2).

2. A collision resolution policy is a method for finding an empty
   table entry in which to store a key K2 if, after trying to store K2
   in table T, we find that the table location given by the hash
   address h(K2) is already occupied by another previously inserted
   key K1.

5. Primary clustering occurs in hashing by open addressing with
   linear probing when contiguous clusters of keys form in the hash
   table. Each such cluster tends to grow at its low address end at a
   rate proportional to its cluster size, and adjacent clusters tend
   to join to form even larger clusters which grow even faster
   (because they form larger targets for collision with new keys
   being inserted).

e. 11.6 Review Question 1

A hash function h(K) performs well if the hash addresses it
computes for keys K are distributed evenly in a hash table’s
address space. A good hash function disperses clusters of keys in
the key space by mapping them into dispersed hash table
addresses. A hash function performs poorly if it does not
distribute hash addresses evenly in a hash table or if it fails to
disperse clusters of keys.

f. 13.4 Review Questions 1 and 2

1. In divide-and-conquer methods for sorting, an initially unsorted
   array of keys is divided into two or more subarrays that are
   conquered (sorted separately), after which the sorted subarrays
   are combined in some fashion to yield the entire sorted array that
   solves the original sorting problem.

2. In the MergeSort method, an unsorted array is divided into two
   unsorted arrays of (roughly) equal size which are merge sorted to
   yield two sorted subarrays. These sorted subarrays are then
   merged by imagining that they are queues, repeatedly removing
   the larger key from the front of either of the two queues, and
   inserting it on the rear of an initially empty output queue.