MORE IN Analysis of Algorithms
MU Computer Engineering (Semester 4)
Analysis of Algorithms
May 2016
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1(a) Explain the asymptotic notations.
10 M
1(b) Write an algorithm to find minimum and maximum value using divide and conquer and also derive its complexity.
10 M

2(a) Explain the concept of multiplying long integers using divide and conquer.
10 M
2(b) Sort the following numbers using Quick Sort. Also derive the time complexity of Quick Sort.
50, 31,71,81,12,33
10 M

3(a) Solve the following Job sequescing with deadlines problem
n=7,   Profits (p1, p2, ......, p7)     = {3, 5, 20, 18, 1, 6, 30}
Deadlines(d1,d2,......,d7)     = {1, 3, 4, 3, 2, 1, 2}
10 M
3(b) Explain Different string matching algorithm.
10 M

4(a) Find the Minimum Spanning Tree of the following graph using Kruskal's algorithm 10 M
4(b) Explain flow shop scheduling with example.
10 M

5(a) Write an algorithm for sum of subsets. Solve the following problem.
M=30       W={5, 10, 12,13,15,18}
10 M
5(b) Find the shortest path from source vertex A using Dijkstra's algorithm 10 M

Write note on (any two)
6(a) Strasen;s matrix multiplication
10 M
6(b) 8- Queen problem.
10 M
6(c) Graph coloring
10 M
6(d) 15-puzzle problem
10 M

More question papers from Analysis of Algorithms