| Contents [0/2] |
| Homework [1/2] |
| HW Answers [2/2] |
(Click here for one slide per page)
| Homework [1/2] |
Read Algorithms 3.1, 3.5 and 3.2
Recursion Supplement (Optional, but suggested): Tracing Recursion. You do not need to hand in anything for this.
Do the following problems from the text. (Hand in.)
3.1.10
Give a trace of the process of inserting the keys
E A S Y Q U E S T I O N
into an initially empty table using SequentialSearchST. How many
compares (of keys) are involved?
3.1.11
Give a trace of the process of inserting the keys
E A S Y Q U E S T I O N
into an initially empty table using BinarySearchST. How many
compares (of keys) are involved?
3.2.1
Draw the BST that results when you insert the keys
E A S Y Q U E S T I O N
in that order (associating the value i with the ith key, as per
the convention in the text) into an initially empty tree. How many
compares are needed to build the tree?
3.2.2
Inserting the keys in the order A X C S E R H into an
initially empty BST gives a worst-case tree where every node has one
null link, except one at the bottom, which has two null links. Give
five other orderings of these keys that produce worst-case trees.
You can also describe the constraints that produce this outcome
--- Things like "insert A first, insert B before C, etc."
3.2.3
Give five orderings of the keys A X C S E R H that, when
inserted into an initially empty BST, produce the best-case tree.
You can also describe the constraints that produce this outcome
--- Things like "insert A first, insert B before C, etc."
3.2.4
Suppose that a certain BST has keys that are integers between
1 and 10, and we search for 5. Which sequence below cannot be the
sequence of keys examined?
a. 10, 9, 8, 7, 6, 5
b. 4, 10, 8, 6, 5
c. 1, 10, 2, 9, 3, 8, 4, 7, 6, 5
d. 2, 7, 3, 8, 4, 5
e. 1, 2, 10, 4, 8, 5
| HW Answers [2/2] |
3.1.10
k v # list representation (key|value)
E 0 0 E|0
A 1 1 A|1 -> E|0
S 2 2 S|2 -> A|1 -> E|0
Y 3 3 Y|3 -> S|2 -> A|1 -> E|0
Q 4 4 Q|4 -> Y|3 -> S|2 -> A|1 -> E|0
U 5 5 U|5 -> Q|4 -> Y|3 -> S|2 -> A|1 -> E|0
E 6 6 U|5 -> Q|4 -> Y|3 -> S|2 -> A|1 -> E|6
S 7 4 U|5 -> Q|4 -> Y|3 -> S|7 -> A|1 -> E|6
T 8 6 T|8 -> U|5 -> Q|4 -> Y|3 -> S|7 -> A|1 -> E|6
I 9 7 I|9 -> T|8 -> U|5 -> Q|4 -> Y|3 -> S|7 -> A|1 -> E|6
O 10 8 O|10 -> I|9 -> T|8 -> U|5 -> Q|4 -> Y|3 -> S|7 -> A|1 -> E|6
N 11 9 N|11 -> O|10 -> I|9 -> T|8 -> U|5 -> Q|4 -> Y|3 -> S|7 -> A|1 -> E|6
------------------------------------------------------------------------------
Total = 55 compares
If N is the number of put operations, then the maximum is N*N/2
(= 12*12/2 = 72 in this case).
The worst case occurs in the case that all keys are unique.
3.1.11
Binary search does the comparison to key[mid], where
mid = lo + (hi - lo) / 2;
if hi-lo is odd, pick the middle.
if hi-lo is even, pick the lower of the middle two
In the table below, I show the comparisons in order in the key
array. So, for example, when inserting S, the algorithm first
compares to A, then E.
k v # KEY ARRAY VALUE ARRAY
E 0 0 E1 0
A 1 1 A1 E2 1 0
S 2 2 A E1 S2 1 0 2
Y 3 2 A E1 S2 Y3 1 0 2 3
Q 4 3 A E Q1 S2 Y3 1 0 4 2 3
U 5 3 A2 E3 Q1 S U Y 1 0 4 2 5 3
E 6 3 A E Q1 S3 U2 Y 1 6 4 2 5 3
S 7 3 A E Q1 S3 U2 Y 1 0 4 7 5 3
T 8 3 A E2 Q3 S1 T U Y 1 0 4 7 8 5 3
I 9 3 A E2 I3 Q1 S T U Y 1 0 9 4 7 8 5 3
O 10 3 A E2 I3 O4 Q1 S T U Y 1 0 9 10 4 7 8 5 3
N 11 4 A E I N O Q S T U Y 1 0 9 11 10 4 7 8 5 3
--------------------------------------------------------------------------
Total = 30 compares
Binary search allows N keys to be put() about 2N compares (= 24 in
this case). The number is low, since about half the time, we have
one more comparison, making it really closer to 2.5N (= 30 in this case).
3.2.2
In general: repeatedly insert either the max or min remaining key.
Here are some examples:
A,C,E,H,R,S,X // sort
A,C,E,H,R,X,S
A,C,E,H,X,S,R
A,C,E,X,S,R,H
A,C,X,S,R,H,E
A,X,S,R,H,E,C
X,S,R,H,E,C,A // reverse sort
A,X,C,S,E,R,H // alternate
X,A,S,C,R,E,H
Are the following correct?
A,S,C,X,E,R,H
X,R,S,H,E,C,A
X,E,R,C,S,H,A
3.2.3
In general:
keep a set of sets, initially just one subset containing all keys
choose a subset and remove it from the set of sets
in the BST, insert the middle key from the subset
to the set of sets, add the two subsets containing the smaller and larger keys
Another way to view that:
Draw the perfectly balanced tree that you want.
Always insert parent before child.
In this case the tree we want is:
H
/ \
C S
/ \ / \
A E R X
Here are some examples:
H,C,A,E,S,R,X // pre-order
H,C,S,A,E,R,X // level-order
H,C,E,A,S,X,R
H,S,X,R,C,E,A
H,S,R,X,C,A,E
H,S,R,X,C,E,A
3.2.4
d