## Pokhara University | Old Question Paper

Bachelor of Engineering (BE)

Analysis and Design of Algorithms | Level: Bachelor

Year: 2010 | Semester : Spring

**Download Question Paper File**

[ 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 Θ. [7]

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. [8]

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. [7]

3. a) Briefly explain the Dynamic Programming method for problem solving. What is the basic difference between Dynamic Programming and Greedy method? [7]

**b) Consider five items along with their respective weights and profit values [8]**

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. [8]

b) What do you mean by biconnected components and articulation points in a graph? Explain with an example. [7]

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. [8]

6. a) Write an algorithm to find the transpose of a matrix and compute its complexity. [7]

b) Write a recursive algorithm to find the nth Fibonacci number, and compute its complexity. [8]

**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