CIS 114                                                     Summer 2005


                            Homework 5
			    ----------

- General Instructions (GI) for all Homeworks:

SEE HOMEWORK ONE.  ALL INSTRUCTIONS WILL BE ENFORCED.

THIS HOMEWORK IS DUE MONDAY JUNE 27th AT 5:00 PM.


Q1 (lecture 25)

Show in the same format as page 12 how you would merge the following
two arrays:

12 18 39 44 and 14 15 20 40 

Make sure you place the arrow marks correctly.


Q2 (lecture 26)

Quicksort is extremely important.  Make sure you study it well.

Show step by step how you find the S1/S2 division on this array:

12 18 6 19 4 17


Q3 (lecture 27)

What is the complexity of sorting an array with Quicksort when that
array is already sorted?

Q4 (lecture 28)

Look at page 14.
We are adding the following nodes:

A LEFT child under 7.
A LEFT child under 12.

Only integer numbers are allowed.

What are the two numbers that we added?


Q5 (lecture 29)

What would be the result of POSTORDER traversal of the tree
from Q4 above (before adding the two new nodes).


Q6 (lecture 30)

Explain: When is the binary tree implementation of a table efficient,
and when is it not efficient?