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 :
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).
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
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.
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.
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".
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.
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 .
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.
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.