Programming Problems 7

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 fi nds 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.


About Avi Dullu
Jaako rakhe saiyan, maar sake na koi!

One Response to Programming Problems 7

  1. Divya says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: