## Nice Exercises

1. ** 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. Hint

2. * 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)?

3. ** 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 :
• (ii) Report sum(i,j) = sum of the entries in the array from indices i to j for any 0 < i < j <= n.
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. 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). Hint

4. ### Problems on Amortized Analysis

1. ** 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). Hint

2. * 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).

5. 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

6. ### Shortest Path Problems

1. * From a subset of vertices to another subset of vertices

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.

7. ### Paths in Directed Acyclic Graph

1. * 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 to v.

2. ** 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".

8. * 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.

9. 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 .

10. * 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.

11. * 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?

12. * 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.

13. ** 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. Hint 14. ** 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.

15. *** 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.

# Solutions

## Exploring a Binary Heap

Hint : 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

Hint : 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 A[i]. 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

Hint : 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

Hint : 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

Hint : Some simple observations from the definition of scorpion graph are :
1. The only vertex of degree n-2 is body.
2. There is no edge between any foot and the sting.
3. There is no edge between any foot and the tail.
We shall use above observations to give the O(n) time algorithm for verifying whether given graph is a scorpion graph or not.
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.
Observations :
• The body must belong to set A.
• The sting must belong to set B.
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.
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 body.
• else
pick one node say z from 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 .
So by a constant number of lookups of the adjacency matrix we are able to eliminate atleast one foot from set A or B.