Assignment # 2 A binary search tree

Assignment # 2 

• The PDF file that you submit must be clearly legible. To this end, we encourage you to learn
and use the LaTex typesetting system, which is designed to produce high-quality documents
that contain mathematical notation. You can find a latex template in Piazza under resources.
You can use other typesetting systems if you prefer. Handwritten documents are acceptable
but not recommended. The submitted documents with low quality that are not clearly legible,
will not be marked.
• You may not include extra descriptions in your provided solution. The maximum space limit
for each question is 2 pages. (using a reasonable font size and page margin)
• For any question, you may use data structures and algorithms previously described in class,
or in prerequisites of this course, without describing them. You may also use any result that
we covered in class, or is in the assigned sections of the official course textbook, by referring
to it.
• Unless we explicitly state otherwise, you should justify your answers. Your paper will be
marked based on the correctness and completeness of your answers, and the clarity, precision,
and conciseness of your presentation.
• For describing algorithms, you may not use a specific programming language. Describe your
algorithms clearly and precisely in plain English or write pseudo-code.

1. A binary search tree is weight balanced if for each node in the tree, the number of nodes in its two
subtrees differ by at most 1. Recall that for an AVL tree, it is the height of the two subtrees that
must differ by at most one.
(a) (10 Mark) Give an algorithm to build a weight balanced BST given a sorted array of n elements.
Your algorithm should run in O(n) time. Analyze the time complexity of your algorithm.
(b) (10 Mark) Prove that the height of a weight balanced BST is O(logn).
(c) (5 Mark) Does the same rebalance operation for AVL tree insert work for inserting to weight
balanced BST? Justify your answer by a proof or a counter example.
2. Bob has m dollars and wants to buy two items with an exact total cost of m. Assume that you are
given a binary search tree that stores the price of n available items and no two items have the same
price.
(a) (15 Mark) Write an O(n) algorithm to find two items with total price of m.
(b) (5 Mark) Analyze the time complexity of your algorithm.
3. Consider the following opertation in a binary tree that stores integer keys:
• Closest-Pair(r): returns the minimum difference of the keys among all pairs in the subtree
rooted at r. In other words, Closest-pair(r) returns the minimum value of |x.key −y.key| among
all elements x,y rooted at r.
We want to is augment AVL tree to support this operation in O(1) time such that the time complexity
of Insert and Delete remains O(logn).
(a) (6 Mark) What extra information do we need to store at each node?
(b) (8 Mark) Explain how to perform Closest-Pair in O(1)?
(c) (16 Mark) Explain why Insert and Delete can still be performed in O(logn) time?
4. A cryptographic hash function is a particular class of hash functions that have special properties which
make them suitable for use in cryptography. The ideal cryptographic hash function has five main
properties:
1) It is deterministic so the same message always results in the same hash.
2) It is quick to compute the hash value for any given message.
3) It is infeasible to generate a message from its hash value except by trying all possible messages.
4) A small change to a message should change the hash value so extensively that the new hash
value appears. uncorrelated with the old hash value
5) It is infeasible to find two different messages with the same hash value
In this question, you will see the algorithms for two simple string hash functions. For both
algorithms, the input is a string of ASCII characters and the output is a hash code.

• Algorithm 1
This algorithm is not the best possible algorithm, but it has the merit of extreme simplicity.
1: function Hash(S)
2: hash = 0
3: for each characters c in S do
4: hash + = ASCII(c)
5: end for
6: return hash
7: end function
• Algorithm 2
This algorithm is one of the best algorithms known for string hash.
1: function Hash(S)
2: hash = 5381
3: for each characters c in S do
4: hash = hash ∗ 33+ASCII(c)
5: end for
6: return hash
7: end function
(a) (7 Mark) What is the hash code of the string “abcd” using Algorithm 1 and Algorithm 2?
(b) (5 Mark) For each 5 properties of cryptographic hash functions mentioned above, discuss if
Algorithm 1 has the property. Briefly justify your answer for each or give a counter example.
(c) (5 Mark) Why do you think Algorithm 2 is a better algorithm? (Specify at least one property
in which you think algorithm 2 performs better than Algorithm 1. Justify your answer.)
(d) (8 Mark) Name two well-known cryptographic hash functions and specify the hash code of
the string “abcd” using each of them. (You do not need to describe the algorithms and the
computation process. You might need a quick Google search or running a command line
program.)