Consider the insertion of items with the following keys WRITTEN Solution

Description

1. Consider the insertion of items with the following keys (in the given order) into an initially empty AVL tree: 30, 40, 24, 58, 48, 26, 11, 13, 17. Draw the resulting AVL trees after each insertion (nine of them).

2. What is the minimum number of internal nodes in an AVL tree of height 5? Draw such a tree.

3. Given functions ,  : ℕ → ℝ, prove that  (  ) ∈ Q( ( )) if and only if  (  ) ∈ O( ( )) and  (  ) ∈ W( ( )).

4. Consider the version of selection sort I gave you in lecture 2, shown below:

Algorithm selectionSort(A,n): Input: Array A of size n Output: Array A sorted for k ¬ 0 to n–2 do

min ¬ k

for j ¬ k+1 to n–1 do

if A[j] < A[min] then

min ¬ j

end

end

swap(A[k], A[min])

end

end

Draw the decision tree associated with running this algorithm on a sequence of 3 distinct values, say = [ ₀, ₁, ₂], where each ∈ {1,2,3}. Label each internal node with the comparison done at that node in terms of (for example, < ) and label each external node with the actual sequence that leads the algorithm towards that external node. Note, your results should be consistent, meaning each path can correspond to at most one permutation of the original data.

5. Suppose you would like to sort music files, but you only have an old, unreliable computer, which you have nicknamed “Rustbucket”. Every time Rustbucket compares two music files, and , there is an independent 50-50 chance that it has an internal disk fault and returns the value -1, instead of the correct result of 1 for true or 0 for false, to the question, “ ≤ ?” Otherwise, Rustbucket correctly performs every other kind of operation (including comparisons not involving music files.) Describe an efficient algorithm that can use Rustbucket to sort music files correctly and show that your algorithm has expected running time that is (   log   ).