STUPIDSID
1 (a)
Define terms:
1. Polynomial time algorithm
2. Greedy Algorithm
3. Minimum Spanning Tree (MST)
4. NP-Complete.
1. Polynomial time algorithm
2. Greedy Algorithm
3. Minimum Spanning Tree (MST)
4. NP-Complete.
7 M
1 (b)
Prove that travelling salesman problem is NP-complete.
7 M
2 (a)
Given a set of n items with each item I having bi→ a positive benefit and wi→a
positive weight. Choose items with maximum total benefits but with at most
W=10ml.
| Weight | 4 ml | 8 ml | 2 ml | 6 ml | 1 ml |
| Benefit per ml | 3 | 4 | 20 | 5 | 50 |
7 M
2 (b)
Explain the accounting method of amortized analysis using stack operations.
7 M
2 (c)
Explain potential method of amortized analysis.
7 M
3 (a)
Use master method to give tight asymptotic bounds for the following
recurrence.
T(n)=2nT(n/2)+n2
T(n)=3T(n/2)+n2
T(n)=16T(n/4)+n.
T(n)=2nT(n/2)+n2
T(n)=3T(n/2)+n2
T(n)=16T(n/4)+n.
7 M
3 (b)
Write Prim's algorithm and apply it on following graph. And find running time of the algorithm.
7 M
3 (c)
1. Let f(n)=4n+3 and g(n)=n Is f(n)=Ω(g(n))?
2. Let f(n)=n2 and g(n)=4n2+2 Is f(n)=Ω(g(n))?
If yes, find n0 and c.
2. Let f(n)=n2 and g(n)=4n2+2 Is f(n)=Ω(g(n))?
If yes, find n0 and c.
7 M
3 (d)
What kind of problems is solved by Bellman Ford algorithm? Run the bellman Ford algorithm on following graph. Find the running time.
7 M
4 (a)
Working modulo q=13, how many spurious hits does the Rabin Karp matcher encounter in text T=2359023141526739921 when looking for pattern P=31415
7 M
4 (b)
Determine a Longest Common subsequence (LCS) of {1,0,0,1,0,1,01} and {0,1,0,1,1,0,1,1,0} with proper diagram.
7 M
4 (c)
Write the case in which worst case behavior for quicksort occurs. Find out
the worst case running time of quicksort. Write and explain randomized
partition for QUICKSORT.
7 M
4 (d)
Describe Dijkstra's algorithm for single source shortest path problem.
Give a simple example of a directed graph with negative-weight edges for
which Dijkstra's algorithm produces incorrect answers.
7 M
5 (a)
Find the running time of breadth first search algorithm.
7 M
5 (b)
How MERGE-SORT can be done with Divide and Conquer strategy?
Explain with example.
7 M
5 (c)
Explain recursive algorithm of depth first search (DFS) for directed graph.
7 M
5 (d)
Explain assembly line scheduling and how it can be done by dynamic
programming? Write the procedure for computing the fastest times to get the
assembly out of factory.
7 M
More question papers from Design And Analysis Of Algorithm