- ** 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)?
- ** Complete binary tree as an efficient
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 :
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
Your objective is to perform these operations efficiently.
Give a data-structure which will guarantee O(log n)
time per operation. (The title of the problem is a hint).
- (i) Add(i,x) which adds x to the entry
- (ii) Report sum(i,j) = sum of the entries in the
array from indices i to j for any 0 < i < j <= n.
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
- Computing a spanning tree having smallest value of largest edge weight
Describe an efficient algorithm that, given an undirected graph G,
determines a spanning tree of G whose largest edge weight is minimum
over all spanning trees of G.Hint
Shortest Path Problems
- * From a subset of vertices to another subset
Given a directed graph G(V,E), where edges have nonnegative
weights. S and D are two disjoint subsets of the set of
vertices. Give an O(|V| log |V| + |E|) time algorithm to find
the shortest path among the set of paths possible from any node in S
to any node in D.
Paths in Directed Acyclic Graph
- * Counting the number of paths
Given two nodes u,v in a directed acyclic graph G(V,E).
Give an O(|E|) time algorithm to count all the paths from u
- ** Path passing through a subset of nodes
Given two nodes u,v and a set of vertices
w1, w2,...,wk in a directed acyclic
graph G(V,E). Give an O(|E|) time algorithm to output
a path(if exists) from u to v which passes through each
of the nodes w1,...,wk. If there is no such path
then your algorithm must report that "no such path exists".
- * 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
traveled 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.
- *** Nearest Common Ancestor
Given a rooted tree of size n . You receive a series of online
queries : "Give nearest common ancestor of u,v " . Your
objective is to preprocess the tree in O(n) time to get a data
structure of size O(n) so that you can answer any such query in
O(log n) time.
Exploring a Binary Heap
I think you are trying to find the kth largest element in the heap in
O(k) time in order to solve this problem. But actually, you
need not find the kth
largest element in the heap to solve this problem. You will be able to
solve the problem if you are able to find whether the number of elements in
the heap which are greater than x are more/less/equal to k .
Now exploit the definition of the heap, to do this task in O(k) time.
Note that you have extra O(k) storage space to use.
Complete Binary Tree as an efficient data-structure
Consider a complete binary tree with its leaves
as the entries of the array A, i.e. the i th leaf of the tree is
Every internal node of the tree can be used to store some number .
The skeleton of the data-structure is shown in the following figure :
Fill in the details of the data-structure and give O(log n) time
algorithms for both the operations.
Delete-min in constant amortized time
This is a very nice exercise to understand the technique of Amortized Analysis.
You know that actual cost of Delete-min is O(log n). So you have
to choose a potential function such that during the Delete-min
operation, change in the potential function is - O(log n) (to balance
the actual cost).
Now concentrate on the tree structure of the binary heap to realize what
happens when the minimum element is deleted. Look on the following diagram
to see what is happening during Delete-min :
Compare the two tree structures above. What is missing in the tree after
Delete-min. Two structures are the same except a node is missing
and that too from leaf level. Can you now guess the potential function? If not,
then scroll down to see the solution.
It is sum of the depths of all the nodes in the heap. Now verify it.
Computing a spanning tree having smallest value of largest edge weight
First prove that largest edge weight of the minimum spanning tree is minimum
over all spanning trees of G(use the fact that the an edge belongs to
the minimum spanning tree if it is of the least weight in the cut-set defined
by the tree and the edge).
Now give any efficient algorithm for computing minimum spanning tree.
Checking the Scorpion
Some simple observations from the definition of scorpion graph are :
We shall use above observations to give the O(n) time algorithm
for verifying whether given graph is a scorpion graph or not.
- The only vertex of degree n-2 is body.
- There is no edge between any foot and the sting.
- There is no edge between any foot and the tail.
Let M be the adjacency matrix of the graph.
Pick a vertex v arbitrarily. Let d be the degree of v(can
be found out from the adjacency matrix in time O(n)).
From the definition of scorpion it is clear that if d is 1,2 or n-2,
we can easily check whether the graph is scorpion or not(convince yourself).
Let us consider the case when $2 < d < n-2$. Clearly v must be a foot.
Now Let A be the set of vertices which are adjacent to v,
and B be the set of vertices which are not adjacent to v.
Now we shall successively eliminate the verticess of set A and
B which are feet. Finally we shall
be left with A or B containing single vertex. At this point
you can easily verify in O(n) time whether the given graph is scorpion.
Now we shall describe a way to successively eliminate the vertices of set
A and B until one of them becomes a singleton set.
- The body must belong to set A.
- The sting must belong to set B.
Pick two nodes x,y from set A.
If M[x,y] =0, then throw both of them away since none of them can be a
pick one node say z from B.
So by a constant number of lookups of the adjacency matrix we are able to
eliminate atleast one foot from set A or B.
If M[x,z] = 1 and M[y,z]= 1, throw z away since
z can't be sting.
If M[x,z] = 1 and M[y,z]= 0, throw y away since
y can not be body.
If M[x,z] = 0 and M[y,z]= 1, throw x away since
x can not be body.
If M[x,z]=M[y,z]=0, then pick one more vertex say w from set B.
Try to eleiminate x or y if possible as in case of z.
If we are still stuck i.e. M[x,w]=M[y,w]=0, then through both
x,y since none of them can be a body .