Assume you are given a list of n = 2k + 1 integers as (k + 1; 1; : : : ; k; k + 2; : : : ; 2k + 1).

Draw a binary search tree resulted from inserting these integers in the order of the list.

What is the best, worst and average time for the searching operation.

1. Present an O(k log k) time algorithm to return the kth minimum element in a binary

min-heap H of size n, where 1 k n.

1. Read Chapter 6.2 in the book of Mehlhorn and Sanders. Brie

y explain the advan-

tages conferred by using Fibonacci heaps over the simpler binary heap implemen-

tation of priority queues (75-150 words).

1

Exercise 2 Algorithm design (15 points)

Exercise 3 Binary Search and Priority Queues (10 points for 3.1 + 10 points for 3.2)

2. Assume you are given a binary heap containing n = 2k elements in an array of size

n. You are asked to repeatedly extract the minimum element, n times. Assume

that insertions are never performed. To make the heap space ecient, you move

the heap over to an array of size 2j whenever an extraction decreases the number of

elements to 2j for any integer j. Suppose that the cost of each such move is (2j).

What is the total movement cost caused by the n extracting operations starting

from the heap of n elements? (Ignore the costs of any other binary heap related

operations.)

Exercise 4 Binary Search and AVL Trees (15 points for 4.1 + 15 points for 4.2 + 15

points for 4.3 + 5 points for 4.4)

1. Given n distinct input values derive an expression for the number of dierent degen-

erate trees that can be generated from dierent insertion orders of those n values.

In your discussion, call this number deg(n). If you are stuck you may want to con-

sider how to generate all the degenerate trees for the elements 1; 2; 3; 4 to help you

get started. Note: to get full marks your derivation has to be in precise language

and apply to all integers n 0. Hint: the answer to this question does not have

to be long but it should address the nature of the insertion sequences that generate

degenerate trees.

2018-03-05
Database