Design & Analysis of alogrithms

Design & Analysis of alogrithms

Note : Attempt all questions:

1.    Attempt any two of the following :

(a) Let f (n) and g(n) be asymptotically positive
Functions Prove or disprove each of the following
Conjectures:
(i) f(n) = o(g(n)) implies g(n) = o(f(n))
(ii) f (n)+g (n)- ᵩ(min(f(n ),g(n))).

(b) Show how to implement a first-in, first out
queue with a priority queue. Show how to
Implement a stack with a priority queue.

(c) Let X be a random variable that is equal to
the number of heads in two flip of a fair coin.
What is E[X2] ? What is E2[x]?

2 Attempt any two of the following:

(a) Give a recursive version of the tree-insert
procedure.

 (b) Argue that after executing RB-Delete-Fix up, the
root of the tree must be black,

(c) Write a recursive procedure OS-KEY-RANK
(T, K) that takes as input on order statistic tree
T and a key k and returns. The rank of k in
the dynamics set represented by T. Assume that
the keys of T are distinct.

3. Attempt any two of the following :

(a) Show how to reconstruct an LCS from the
completed C table and the original sequence
X =(x1, x2…….xm) and Y =( y1, y2…….yn) in
O(m +n) time without using the b table.

(b) Generalize Huffman's algorithm -to ternary
codewords (i.e. codewords using the symbols
0, I and, 2), and prove that it yields optimal
ternary codes.

(c) What is the total cost of executing n of the stack
operations PUSH POP and MUITITOB assuming
that the stack begins with S0 objects and
finishes with .Sn objects ?

4 Attempt any two of the following:                  

 (a) Suppose that the graph G = (V, E) is represented
as an adjacency matrix. Give a simple
implementation of Prim’s algorithms so that it runs
in O(V2) time for this case.

(b) Give an efficient push-rebel algorithm o find a
maximum matching in a bipartite graph. Analyze
your algorithm.

 (c) Suppose we run Johnson's algorithm on a
directed graph G with weight function w . Show
that if G contains a O-weight cycle c, then
w(U,'V')=0 for every edge (U,V) in c.

5 Attempt any two of the following :

 (a) Construct he string-matching automation for the
pattern P = a a b a b and illustrate its operation
on the text string
T = a a a b a b a a b a a b a b a a b.

(b) Show that the subset-sum problem is solvable
in polynomial time if the target value I is
expressed in unary.

(c) .Write an efficient greedy algorithm that finds
an optimal vertex cover for a tree in linear time.