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.
How to use this UTU paper
This UTU Design and Analysis of Algorithms Paper resource is useful for understanding Uttarakhand Technical University question patterns for CSE branch, previous year exam. Review the repeated units, important numerical questions, definitions and long-answer topics before making your revision plan. Compare this paper with nearby semester papers to identify common subjects and frequently asked concepts.
For more related downloads, browse 1st Year Papers, 3rd Year Papers, and 4th Year Papers.