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[X²] ? What is E²[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 =(x₁, x₂…….x_m) and Y =( y₁, y₂…….y_n) 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 S₀ objects and

finishes with .S_n 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(V²) 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.