DOEACC Society 2006 DOEACC C Level C4 Algorithm Analysis & Design ( ) - Question Paper

C4-R3: ALGORITHM ANALYSIS AND DESIGN
NOTE:
Time: three Hours Total Marks: 100
1.
a) describe P, NP, NP-Hard SNP-Complete class of issues.
b) Use mathematical induction to show that when n is an exact power of 2, the solution of
the recurrence
T(n) = two if n = 2
2T (n/2) + n if n = 2k for k>1}
is T(n)= n lg n.
c) Show that in any sub-tree of a max-heap, the root of the sub-tree contains the largest
value occurring anywhere in the sub-tree.
d) What is the use of prefix function in Knuth-Morris-Pratt String Matching Algorithm?
e) A sequence of n operation is performed on a data structure. The i th operation cost i if i
is an exact power of 3, and one otherwise. Use aggregate analysis to determine the
amortized cost per operation.
f) provide an algorithm that determines whether or not a provided undirected graph G = (V, E)
contains a cycle. Your algorithm should run in O (V) time, independent of |E|.
g) Show that if a node in a binary search tree has 2 children, then its successor has no
left child and its predecessor has no right child.
(7x4)
2.
a) Let R (i, j) be the number of times that table entry m[i, j] is referenced while computing
other table entries in a call of MATRIX-CHAIN_ORDER. Show that the total number of
references for the entire table is
å å
= =
=
n
i
n
j i
R i J
1
( , ) ( n3-n)/3 .
b) What is the difference ranging from the binary search tree property and the min-heap
property? Can the min-heap property be used to print out the keys of an n-node tree in
sorted order in O (n) time? discuss why?
(10+8)
3.
a) How can we obtain out ith smallest number from an array of n numbers in expected linear
time?
b) Assuming 3-CNF satisfiability issue to be NP-Complete, prove clique issue is also
NP-Complete.
(9+9)
C4-R3 Page one of two July, 2006
1. ans ques. one and any 4 ques. from two to 7.
2. Parts of the identical ques. should be answered together and in the identical
sequence.
4.
a) Show that a depth-first search of an undirected graph G can be used to identify the
connected component of G and that the depth-first forest contains as many trees as G
has connected components. More precisely, show how to replace depth-first search so
that every vertex v is assigned an integer tag cc[v] ranging from one and k, where k is the
number of connected components of G, such that cc[u] = cc[v] if and only u and v are in
the identical connected component.
b) provide an O(V+E) time algorithm to calculate the component graph of a directed graph
G=(V, E). Make sure that there is at most 1 edge ranging from 2 vertices in the
component graph your algorithm produces.
(10+8)
5.
a) explain Dijkastra’s algorithm to solve the single source shortest paths on a weighted,
directed graph with a example.
b) We are provided a directed graph G = (V,E) on which every edge (u,v) Î E has an
associated value r(u,v), which is a real number in the range 0= r(u,v) = one that represents
the reliability of a communication channel from vertex u to vertex v. We interpret r(u,v)
as the probability that the channel from u to v will not fail, and we presume that these
probabilities are independent. provide an efficient algorithm to obtain the most reliable path
ranging from 2 provided vertices.
(8+10)
6.
a) discuss Ford-Fulkerson method to solve maximum flow issue. What is residual
capacity?
b) A professor has 2 children who, unfortunately, dislike every other. The issue is to
serve that not only do they refuse to walk to school together, but in fact every 1 refuses
to walk on any block that the other child has stepped on that day. The children have no
issue with their paths crossing at a corner. Fortunately, both the professor’s house
and the school are on corners, but beyond that he is not sure if it is going to be possible
to send both of his children to the identical school. The Professor has a map of his town.
Show how to formulate the issue of determining if both his children can go to the
identical school as a maximum-flow issue.
(12+6)
7.
a) What is a convex hull? explain a few methods that calculate convex hulls in O(n lg
n)time.
b) Briefly define Graham’s scan algorithm to solve the convex-hull issue.
([4+6]+8)
C4-R3 Page two of two July, 2006

Earning:   Approval pending.