Exercises related to the classes held till now
- ** Exploring the 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.
- * 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)?
- ** Complete binary tree as an efficient
data-structure
You are given an array of size n(n being a power of two).
All the entries of the array are initialized to zero.
You have to perform a sequence of the following online operations :
(i) Add(i,x) which adds x to the entry
A[i].
(ii) Report sum(i,j) = sum of the entries in the
array from indices i to j for any 0 < i < j <= n.
The objective is to perform these operations efficiently. It can be seen easily
that we can perform the first operation in O(1) time whereas the
second operation may cost O(n) in worst case.
Here is an outline of a data-structure which will guarantee O(log n)
time for both the operations : Consider a complete binary tree
with n leaves, the i th leaf pointing to A[i]. Every
internal node of the tree can store some number . Fill in the details of
the data-structure and give algorithms which will take O(log n) time
to perform each operation. The skeleton of the data-structure in the following
figure :
-
Problems on Amortized Analysis
- ** Delete-min in constant time !!!
Consider a binary heap of size n , the root storing the
smallest element. We know that the cost of insertion of an
element in the heap is O( log n) and the cost of deleting the
smallest element is also O( log n). Suggest a valid potential
function so that the amortized cost of insertion is O( log n)
whereas amortized cost of deleting the smallest element is O( 1).
- * Implementing a queue by two stack
Show how to implement a queue with two ordinary stacks so that the amortized
cost of each Enqueue and each Dequeue operation is
O(1).
Miscellaneous Exercises
- * Searching for a friend
You are standing at a crossing from where
there emerge four roads extending to infinity. Your friend is somewhere on
one of the four roads. You do not know on which road he is and how far he
is from you. You have to walk to your friend and the total distance
travelled by you must be at most a constant times the actual distance of your
friend from you. In terminology of algorithms, you should traverse
O(d) distance, where d is the distance of your
friend from you.
- A simple problem on sorted array
Design an O(n)-time algorithm that, given a real number
x and a sorted array S of n numbers, determines whether
or not there exist two elements in S whose sum is exactly x .
- * Finding the decimal dominant in linear time
You are given n real numbers in an array. A number in the array is
called a decimal dominant if it occurs more than n/10 times in
the array. Give an O(n) time algorithm to determine if the given array
has a decimal dominant.
- * Finding the first one
You are given an array of infinite length
containing zeros followed by ones. How fast can you locate the the first one
in the array?
- * Searching for the Celebrity
Celebrity is a person whom everybody
knows but he knows nobody. You have gone to a party. There are total n
persons in the party. Your job is to find the celebrity in the party. You can
ask questions of the form Does Mr. X know Mr. Y ?.
You will get a binary answer for each such question asked. Find the celebrity
by asking only O(n) questions.
- ** Checking the Scorpion
An n-vertex graph is a scorpion
if it has a vertex of degree 1(the sting) connected to a vertex of degree two
(the tail) connected a vertex of degree n-2 (the body) connected to the
other n-3 (the feet). Some of the feet may be connected to other feet.
Design an algorithm that decides whether a given adjacency matrix represents
a scorpion by examining only O(n) entries.
- ** Endless list
You are having a pointer to the head of singly
linked list. The list either terminates at null pointer or it loops back to
some previous location(not necessarily to the head of the list). You have to
determine whether the list loops back or ends at a null location in time
proportional to the length of the list. You can use at most a constant
amount of extra storage.