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

C4-R3: ALGORITHM ANALYSIS AND DESIGN
NOTE:
Time: three Hours Total Marks: 100
1.
a) An algorithm runs a provided input of size n. If n is 4096, the run time is 512 Milliseconds. If
n is 16384, the run time is 2048 millisecond. What is the complexity of the algorithm?
Write it in terms of big O notation.
b) On what type of input does the Quick sort algorithm exhibit its worst-case behavior?
Why?
c) Draw a complete graph on 4 nodes. Also draw all of its spanning trees.
d) What is the longest prefix of the string “cgtacgttcgtacg” that is also a suffix of this
string.
e) Let G be a complete bipartite graph such that |X| = |Y| = n and for every pair of vertices x
of X and y of Y, there is an edge ranging from x and y. obtain out number of distinct maximum
matchings in G.
f) Let G be a graph whose vertices are the integers one through eight and let the adjacent
vertices of every vertex provided by the table below:
Vertex Adjacent vertices
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3,6
5 6,7,8
6 4,5,7
7 5,6,8
8 5,7
i) Draw G.
ii) Order the vertices as they are visited in BFS traversal starting from vertex 1.
g) State Bellman’s principle of optimality. Also show that how it is valid for shortest path
issue with non-negative weights on the edges.
(7x4)
2.
a) State Tower of Hanoi issue with n rings. Write the recursive relation for its complexity.
Prove that Tower of Hanoi issue cannot be solved fewer than 2n –1 movements of
rings.
b) Show that traveling salesman issue is NP complete.
(6+12)
C4-R3 Page one of three January, 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.
2,10 eight , eight 4, 14
8, 8
6, 10
3.
a) Write mathematical formulation of 0-1 knapsack issue. Use dynamic programming
approach to solve the subsequent instance of the issue
Maximum capacity = 11 units
No of items = 5
Weights = 1,2,5,6,7
Profits = 1,6,18,22,28
b) Prove that the lower bound of sorting a sequence of n elements using comparisons
based sorting algorithm is nlogn.
c) What is red black tree? discuss its properties and its applications.
(10+4+4)
4.
a) Write any algorithm for finding minimum spanning tree of a connected weighted graph.
Show that the algorithm you have written indeed determines the optimal spanning tree.
On what approach this algorithm is based on?
b) Critically differentiate greedy strategy and dynamic programming approach with the help
of 2 points.
(12+6)
5.
a) State and prove Ford Fulkerson’a theorem. obtain out the maximum flow and minimum cut
for the subsequent network at a state, where 1st entry represents flow along that arc and
second entry represents the capacity of that arc.
b) Consider a task of a sequence of n operations push, pop, multipop on a stack of
maximum size n. obtain worst case time complexity for this task. Also obtain amortized cost
of every operation of the task.
(10+8)
C4-R3 Page two of three January, 2006
3
8
5
2
4
7
1 6
8,14
18, 18
12, one 6
0,18
0,18
10, 10
6, 6
12,20
6.
a) How Dijkstra’s algorithm is based on greedy approach? elaborate the assumptions made in
it? provide an example where Dijkstra’s algorithm fails? discuss the cause.
b) discuss Strassen’s matrix multiplication. Derive its time complexity. Why this is better than
ordinary matrix multiplication?
(9+9)
7.
a) How the efficiency of a parallel algorithm is measured? By giving an example of a parallel
algorithm obtain its efficiency.
b) State convex hull issue. Write an algorithm to solve it. obtain its time complexity.
c) Write the Knuth Morris Pratt algorithm for string matching. explain its best and worst cases.
(6+6+6)
C4-R3 Page three of three January, 2006

Earning:   Approval pending.