Deemed University 2009 M.Tech Computer Science & Engineering University: Lingayas University Term: I Title of the : Analysis and Design of Algorithms - Question Paper

Roll No. ..

 

Lingayas University, Faridabad

M.Tech (Comp. Sc. & Engg.) (Term I)

End Term Examination October, 2009

Course: Analysis and Design of Algorithms

Course Code: CS -502

[Time: 3 Hours] [Max. Marks: 100]

 

Before answering the questions, candidate should ensure that they have been supplied the correct and complete question paper. No complaint in this regard, will be entertained after examination.

 

Note: Question No. 1 is compulsory. Attempt any two questions from Part B and two questions from Part C. In all attempt five questions.

 

Part A

Q-1

(a) Define mathematically the statement:

f (n) = o (g(n)). (4)

(b) Prove either mathematically or graphically that

3n + 2 = O (n²). (4)

(c) Write a recursive algorithm for finding factorial of n (4)

(d) Why Breadth-first search is so named? Show by a diagram how the search proceeds. (4)

(e) Find the Hamiltonian circuit in the following graph using backtracking. (4)

Part B

Q-2. (a) What is the Minimum-Spanning Tree problem? (5)

(b) Write Kruskals algorithm to solve the Minimum-Spanning Tree problem. (10)

(c) Hence show that Kruskals algorithm is a greedy algorithm. (5)

Q-3. Explain All Pairs Shortest Path algorithm with suitable examples. Can this be considered as an example of dynamic programming? (10)

(b) Show that vertex cover problem is NP complete. (10)

Q-4. Write short notes on the following :

(a) Divide and conquer algorithm. (5)

(b) Dynamic programming algorithm. (5)

(c) Binary search tree. (5)

(d) Circuit satisfiability problem. (5)

Part C

Q-5. (a) Consider the following pseudo codes (a module of an algorithm):

For i 1 to n

For j 1 to n

do s₁

do s₂

End For

End For

If line 3 has the running time O (n.log₂n) and Line 4 has the running time O(log₂n), then compute the running time (complexity) of the above module of the algorithm. (10)

(b) Write the values of :

(i) (ii) (iii) (iv) (4)

(c) Explain topological sorting with an example. How is it different from conventional sorting? (6)

Q-6. Show how to sort n integers x_i, i=1,2,3 ,n in O (n) time, where o ≤ x_i <n² is true"i = 1,2,3, ., n. (20)

Q-7. Let A and B be two matrices of order mxn and nxp respectively. If we want to compute the matrix C = A.B, then

(i) How many real multiplications and real additions are to be performed? (5+5)

(ii) Suppose that on a given machine one real multiplication can be executed in ns time and one real addition can be executed in ns time. What will then be the time required to compute the matrix C (ignoring the other amount of time). Calculate it using asymptotic notations. (10)

Q-8. (a) Draw an undirected graph G having 6 vertices and 10 edges. (6)

(b) Hence draw any non-trivial clique with maximum possible number of vertices of G (8)

(c) Hence draw a Vertex Cover of the graph G. (6)

Roll No. ..

 

Lingayas University, Faridabad

M.Tech (Comp. Sc. & Engg.) (Term I)

End Term Examination October, 2009

Course: Analysis and Design of Algorithms

Course Code: CS -502

[Time: 3 Hours] [Max. Marks: 100]

 

Before answering the questions, candidate should ensure that they have been supplied the correct and complete question paper. No complaint in this regard, will be entertained after examination.

 

Note: Question No. 1 is compulsory. Attempt any two questions from Part B and two questions from Part C. In all attempt five questions.

 

Part A

Q-1

(a) Define mathematically the statement:

f (n) = o (g(n)). (4)

(b) Prove either mathematically or graphically that

3n + 2 = O (n²). (4)

(c) Write a recursive algorithm for finding factorial of n (4)

(d) Why Breadth-first search is so named? Show by a diagram how the search proceeds. (4)

(e) Find the Hamiltonian circuit in the following graph using backtracking. (4)

Part B

Q-2. (a) What is the Minimum-Spanning Tree problem? (5)

(b) Write Kruskals algorithm to solve the Minimum-Spanning Tree problem. (10)

(c) Hence show that Kruskals algorithm is a greedy algorithm. (5)

Q-3. Explain All Pairs Shortest Path algorithm with suitable examples. Can this be considered as an example of dynamic programming? (10)

(b) Show that vertex cover problem is NP complete. (10)

Q-4. Write short notes on the following :

(a) Divide and conquer algorithm. (5)

(b) Dynamic programming algorithm. (5)

(c) Binary search tree. (5)

(d) Circuit satisfiability problem. (5)

Part C

Q-5. (a) Consider the following pseudo codes (a module of an algorithm):

For i 1 to n

For j 1 to n

do s₁

do s₂

End For

End For

If line 3 has the running time O (n.log₂n) and Line 4 has the running time O(log₂n), then compute the running time (complexity) of the above module of the algorithm. (10)

(b) Write the values of :

(i) (ii) (iii) (iv) (4)

(c) Explain topological sorting with an example. How is it different from conventional sorting? (6)

Q-6. Show how to sort n integers x_i, i=1,2,3 ,n in O (n) time, where o ≤ x_i <n² is true"i = 1,2,3, ., n. (20)

Q-7. Let A and B be two matrices of order mxn and nxp respectively. If we want to compute the matrix C = A.B, then

(i) How many real multiplications and real additions are to be performed? (5+5)

(ii) Suppose that on a given machine one real multiplication can be executed in ns time and one real addition can be executed in ns time. What will then be the time required to compute the matrix C (ignoring the other amount of time). Calculate it using asymptotic notations. (10)

Q-8. (a) Draw an undirected graph G having 6 vertices and 10 edges. (6)

(b) Hence draw any non-trivial clique with maximum possible number of vertices of G (8)

(c) Hence draw a Vertex Cover of the graph G. (6)