ALGORITHMS AND DATA STRUCTURES II ASSIGNMENT 1 - WRITTEN

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 �(�) ∈ (�(�)) if and only if �(�) ∈ O(�(�)) and �(�) ∈
(�(�)).
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
� = [�0, �1, �2], 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 �).