**Note: **In this homework set, log denotes the natural logarithm, i.e. the logarithm in base *e*. Following the notation used in the textbook, we write *A*[1*..n*] to mean an array *A *indexed from 1 to *n*. This means the first entry of *A *is *A*[1].

**Question 1 **(Heap)**. **Illustrate all intermediate steps (as a sequence of binary trees) for the operation Insert(*A,*20) applied to the max heap *A *= [18*,*13*,*9*,*5*,*12*,*8*,*7*,*4*,*0*,*6].

**Question 2 **(Heap)**. **The function Increase key(*A,i,k*) has the following pseudocode.

**function **Increase key(*A,i,k*)

**Require: ***A*[1*..n*] is a max heap.

**Require: **1 ≤ *i *≤ *A.*heap size is an index of *A*.

**Require: ***k *≥ *A*[*i*] is a real number.

## 1: A[i] ← k

2: **while ***i > *1 and *A*[parent(*i*)] *< A*[*i*]:

3: **swap ***A*[*i*] and *A*[parent(*i*)]

## 4: i ← parent(i)

Note that each swap operation on line 3 typically requires three assignments.

*temp *← *A*[*i*]

*A*[*i*] ← *A*[parent(*i*)] *A*[parent(*i*)] ← *temp*

Show how the idea of the inner loop of Insertion Sort can be used to reduce these three assignments down to just one assignment, for this function Increase key(*A,i,k*).

**Question 3 **(Binary trees)**. **The binary-search-tree property and the min-heap property are two properties that can describe binary trees.

- Can a binary tree with at least 3 nodes with distinct key values satisfy both properties?

Justify your answer.

- Let
*A*be a min heap with*n*Is it possible to print out the keys of all*n*elements of*A*in sorted order in*O*(*n*) time? If this is possible, please show how. If this is not possible, explain why not. [4 points] - Explain in detail why if a node in a binary search tree has two childern, then its successor has no left child and its predecessor has no right child. [4 points]

**Question 4 **(Binary search tree)**. **(i) We can sort a given set of *n *numbers by first building a binary search tree containing these numbers (using tree-insert repeatedly to insert the numbers one by one) and then printing the numbers by an inorder tree walk. What are the worst-case and best-case running times for this sorting algorithm?

(ii) Describe a binary search tree with *n *nodes, such that the **average **depth of a node in the tree is Θ(log*n*) but the height of the tree is Ω(log*n*). Given an asymptotic upper bound on the height of a binary search tree with *n *nodes, in which the average depth of a node is Θ(log*n*).

**Question 5 **(AVL Tree)**. **Suppose that *a,b,c,d,e,f,g,h *are eight elements with the key values 38*,*22*,*33*,*25*,*47*,*30*,*28*,*31 respectively. Starting with an empty AVL tree (i.e. with no nodes), insert the elements *a,b,c,d,e,f,g,h *in this given order (where *a *is the first element to be inserted) into the AVL tree, and let *T *be the final AVL tree obtained after the insertion of all eight elements. Assume that for every insertion, the AVL tree remains as an AVL tree.

- Please draw
*T*, and please also draw all seven intermediate AVL trees obtained in this sequence of insertions. [4 points] - Let
*T*_{1 }be the AVL tree obtained by deleting element*g*(which has key value 28) from*T*.

Please draw *T*_{1}, and please show all intermediate steps by drawing. (iii) Let *T*_{2 }be the AVL tree obtained by deleting element *e *(which has key value 47) from *T*. (Note that *T *still has element *f*.) Please draw *T*_{2}, and please show all intermediate steps by drawing.

**Question 6 **(BSTs and AVL trees)**. **(i) The binary tree shown in Fig. 1 is a BST, but not an AVL tree. Explain why this BST is not an AVL tree, and perform the necessary rotations, so that it becomes an AVL tree. Please indicate clearly **all rotation steps**, including the node used for each rotation step. Please also draw all intermediate trees obtained in your sequence of rotations, as well as the final AVL tree. (Note that a rotation step is either Left Rotate(*node*) or Right Rotate(*node*). For simplicity, assume that the elements of this BST are labeled by their key values, e.g. node 22 has key 22, node

49 has key 49, etc.)

Figure 1: AVL Tree for Question 6(i)

(ii) Design an algorithm Tree Merge(*T,T*^{0}), where the two inputs *T,T*^{0 }are binary search trees, and where the output is a “merged” binary search tree consisting of all elements in *T *and *T*^{0}, possibly with repeated key values. You may write your algorithm in pseudocode. Explain in as much detail as possible why the binary-search-tree property is still maintained after running your algorithm. What is the complexity of your algorithm? Justify your answer. **Question 7 **(Analysis of d-ary heaps)**. **As mentioned in Lecture L0301 Slide 23, we define a *d*-ary heap (for *d *≥ 2) analogously like a binary heap, but instead, in the *d*-ary tree visualization of a *d*-ary heap, we allow every node to have at most *d *children. In this question, you will extend several binary heap operations to the case of *d*-ary heaps. When asked to design an algorithm, you may write your algorithm in pseudocode.

- For a
*d*-ary heap*A*, given to us in its array representation, describe and explain how its*d*-ary tree visualization can be obtained. Please give an example involving a 3-ary heap with 15 elements. [5 points] - What is the height of a
*d*-ary heap with*n*elements? Find an exact expression for this height in terms of*n*and*d*, and justify your answer with details. [5 points]

In Week 3, we introduced several heap operations, including Extract Max(*A*), Insert(*A,x*), and Increase Key(*A,i,k*), where *A *was assumed to be a binary max heap.

- Design an efficient algorithm that extends Extract Max(
*A*) to*d*-ary max heaps*A*[1*..n*]. Your algorithm should return an element with the largest key and remove it from the input array*A*. (If there are multiple elements with the same largest key value, then returning any of these elements would be okay.) Analyze the running time of your algorithm in terms of*d*and*n*. [5 points] - Design an efficient algorithm that extends Insert(
*A,x*) to*d*-ary max heaps*A*[1*..n*], where*x*is an element to be inserted into*A*while still maintaining the*d*-ary max heap data structure. (Assume that*x*has a valid numerical key value key.) Analyze the running time of your algorithm in terms of*d*and*n*. [5 points] - Design an efficient algorithm that extends Increase Key(
*A,i,k*) to*d*-ary max heaps*A*[1*..n*]. Here,*A*is assumed to be a*d*-ary max heap,*i*is an index of*A*, and*k*is a value. Your algorithm should flag an error if*k < A*[*i*], but would otherwise set*A*[*i*] =*k*and then update the*d*-ary max heap data structure appropriately. Analyze the running time of your algorithm in terms of*d*and*n*. [5 points]

## Reviews

There are no reviews yet.