# Programming Problems 7

November 5, 2009 1 Comment

**Answering dynamic kth smallest queries**

Given a set of n numbers, the kth smallest element can be found in O(n) time using the algorithm we

learned in class. Suppose we have a dynamic set S of numbers that changes over time, and we want to

be able to efficiently support the operations of

(a) inserting a new number into set S, and

(b) Finding the kth smallest element of S, for any k, at any time.

We could support both operations by representing S as an unsorted array A. Inserting a new element

would take just O(1) time. Finding the kth smallest element would take O(n) time. If there are many

kth smallest operations executed on set S, performing all of them will take a large amount of total

time. We might like to speed up the time to find the kth smallest, at a slight increase in the time

to insert an element. Design an algorithm that

(a) supports inserting an element into S in O(log n) time,

(b) supports Finding the kth smallest element of S in O(log n) time as well.

**Room Scheduling**

Suppose you have n classes that you want to schedule in rooms. Each class has a fixed time interval at which it is offered, and classes whose times overlap cannot be scheduled in the same room. There are enough rooms to schedule all the classes.

Design an algorithm to find an assignment of classes to rooms that minimizes the total number of rooms used, in O(n log n) time.

**Minimizing average completion-time**

Suppose you are given a collection of n tasks that need to be scheduled. With each task, you are given its duration. Specifically, task i takes ti units of time to execute. Suppose with each task we also have a release time ri, and that a task may not be started before its release time. Furthermore, tasks may be preempted, in that a scheduled task can be interrupted and later resumed, and this can happen repeatedly. Design an algorithm that finds a schedule that minimizes the average completion-time in this new situation.

**Close Numbers**

For a set S of n real numbers, a pair of elements x, y belong to S, where x < y, are said to be close if

y – x <= ( max(S) – min(S) ) / (n-1)

Suppose you are given an unsorted array A[1 : n] of distinct real numbers. Design an algorithm that finds a pair of close numbers in A in O(n) time.

**Exploring a Binary Heap**

Consider a binary heap containing n numbers (the root stores the greatest number). You are given a positive integer k < n and a number x . You have to determine whether the kth largest element of the heap is greater than x or not. Your algorithm must take O(k) time. You may use O(k) extra storage.

**Merging two search trees**

You are given two height balanced binary search trees T and T’, storing m and n elements respectively. Every element of tree T is smaller than every element of tree T’. Every node u also stores height of the subtree rooted at it. Using this extra information how can you merge the two trees in time O(log m + log n) (preserving both the height balance and the order)?

**In place Ordering**

Suppose we are given a sequence S of n elements, each of which is colored red or blue.

Assuming S is represented as an array, give an in-place method for ordering S so that all the blue

elements are listed before all the red elements. Now extend your approach to three colors.

In-place means that only swap operations are allowed.

MERGING TWO SEARCH TREES

Find the node in T which is the maximum(which is either the root or the rightmost in the right subtree).

After finding this node, just make the right child of this node point to the root of T’. then perform rotations until the height balances.