# Analysis and Design of Algorithms – BE (PU) Question Paper 2010 | SEM: Spring

## Pokhara University | Old Question Paper Bachelor of Engineering (BE) Analysis and Design of Algorithms | Level: Bachelor Year: 2010 | Semester : Spring

[ File Type: PDF | File Size: 231 KB | Download ]

Full Marks: 100 | Pass Marks: 45 | Time: 3 Hrs
Candidates are required to give their answers in their own words as far as practicable. The figures in the margin indicate full marks.

Attempt all the questions.

1. a) What do you understand by Complexity of an algorithm? Explain the asymptotic notations Big Ο, Big Ω, and Big Θ. 
b) Briefly explain a Circular Queue data structure. Write algorithm to add and remove an element from the circular queue and compute the complexity of your algorithm. [2 + 4 + 2]

2. a) Explain the basic principle of Divide an Conquer strategy for algorithm design. Give and example of Divide and Conquer Algorithm, and compute its complexity. 
b) For a recursive algorithm, if the value of T(1)=2 and T(n) given by T(n/2) + c for n>1, then compute the complexity of the algorithm. 

3. a) Briefly explain the Dynamic Programming method for problem solving. What is the basic difference between Dynamic Programming and Greedy method? 
b) Consider five items along with their respective weights and profit values 

Items I = < I1, I2, I3, I4, I5 >
Weights w=< 5, 10, 20, 30, 40 >
profit value v= <30, 20, 100, 90, 160 >
The Knapsack has capacity W=60. Find an optimal solution to the Knapsack Problem

4. a) Devise an algorithm using the idea of Breadth First Search to find the shortest (directed) cycle containing a given vertex v. 
b) What do you mean by biconnected components and articulation points in a graph? Explain with an example. 

5. a) Briefly explain the Backtracking method for problem solving? [3 + 4]
b) How do you solve 0/1 Knapsack problem using Backtracking method? Explain. 

6. a) Write an algorithm to find the transpose of a matrix and compute its complexity. 
b) Write a recursive algorithm to find the nth Fibonacci number, and compute its complexity. 

7. Write short notes on any two: [2 X 5]

a) Strassen’s Matrix Multiplication
b) Tree Vertex Splitting Problem
c) 8-queen’s problem

Posted By : | Comment RSS |