Analysis Of Algorithms - Dec 17 | MU | Sem 4

Analysis Of Algorithms - Dec 17

Computer Engineering (Semester 4)

Total marks: 80
Total time: 3 HoursINSTRUCTIONS
(1) Question 1 is compulsory.
(2) Attempt any three from the remaining questions.
(3) Draw neat diagrams wherever necessary.

1.a. What is backtracking approach. Explain how it is used in graph coloring.

(5 marks)

1.b. Explain Randomized algorithm with example.

(5 marks)

1.c. What is Knuth Morris Pratt Method of Pattern Matching ? Give Examples

(5 marks)

1.d. Explain in brief the concept of Multistage Graphs ?

(5 marks)

1.e. Merge sort and its complexity

(5 marks)

2.a. Derive and comment on the complexity of Quick Sort algorithm.

(10 marks)

2.b. Solve the following Knapsack problem using dynamic approach
N = 4 items , Capacity of knapsack M = 9
|Item i |Value vi| Weight wi| |-|-|-| |1|18|2| |2|25|4| |3|27|5| |4|10|3|

(10 marks)

3.a. What is sum of subset problem? Write the Algorithm and solve the following.
Array A = [2,3,5,6,7,8,9] and K = 15

(10 marks)

3.b. Write the algorithm for finding strassens matrix multiplication and show how the complexity is being affected ?

(10 marks)

4.a. What is longest common subsequence Problem ? Find LCS for the following
String x = ACBAED
String y = ABCABE

(10 marks)

4.b. Explain binary search Tree? How to generate an optimal binary search tree.
                                                                                                                (10 m

arks)   

5.a. What is all pairs shortest path algorithm ? Apply the same on following graph

(10 marks)

5.b. Find MST of following graph using Prims and Krusicals Algorithm.

(10 marks)

6.a. Write short note on Optimal Storages on Tapes

(7 marks)

6.b. Write short note on 15 puzzle problem.

(7 marks)

6.c. Write short note on binary search and its complexity.

(7 marks)

6.d. Write short note on Problem of Multiplying Long Integers.

(7 marks)