LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

AB 30

M.Sc. DEGREE EXAMINATION – MATHEMATICS

FIRST SEMESTER – November 2008

    MT 1808 – COMPUTER ALGORITHMS

 

 

 

Date : 13-11-08                 Dept. No.                                        Max. : 100 Marks

Time : 1:00 – 4:00

Answer ALL questions

1. a) Ifthen prove that

OR

1. b) Explain sequential labeling of the nodes of a binary tree. Give an example of a complete binary tree which is not full.                                                                   (5)
2. c) Give an algorithm to form a heap of n elements inserting one element at a time. Simulate it on A(1:8) = (34, 67, 12, 55, 80, 71, 99, 10).

OR

1. d) Give an algorithm to form a heap of n elements using algorithm ADJUST. Simulate it on A(1:7) = (66, 83, 14, 90, 45, 33, 81).                                                                        (15)
2. a) Give the control abstraction for divide and conquer strategy.

OR

1. b) Explain the problem ‘Optimal Merge Pattern’.                                                             (5)

 

1. c) State algorithm BinSearch.

       Simulate it on A(1:12) = (12, 23, 33, 45, 56, 61, 66, 70, 78, 89, 90, 95) when (i) x=23,      (ii) x=57 and (iii) x=95. Draw the binary decision tree when n = 12.

OR

1. d) State algorithm QUICKSORT.

       Simulate it on (1:9) = (33, 67, 78, 31, 90, 51, 29, 66, 84).                                               (15)

3. a) Give the control abstraction for greedy method.

OR

1. b) Explain clearly the job sequencing problem with deadlines.                                          (5)

 

1. c) Give algorithm GREEDYKNAPSACK. If p₁/w₁ ≥ p₂/w₂  ≥ … p_n/w_n then prove that GREEDYKNAPSACK generates an optimal solution to the given instance of the knapsack problem.

OR

1. d) Explain the optimal storage on tapes problem with an example. With usual notations prove that if  then the ordering  minimizes over all possible values of the                                                                                      (15)

 

 

4. a) Explain the inorder and the preorder tree traversals with examples.

OR

1. b) Explain the breadth first search traversal with an example.                                          (5)
2. c) Explain two different formulations of the sum of subsets problem. Give a recursive backtracking algorithm for sum of subsets problem.

OR

1. d) Explain in detail the 4-queens problem. Give a backtracking algorithm to solve the n-queens problem.                                                                                                                 (15)
2. a) What is Satisfiability problem? State Cook’s Theorem.

OR

1. b) Define a nondeterministic algorithm with an example.                                                 (5)
2. c) Explain maximum clique problem with an example. Prove that CNF-satisfiability α clique decision problem.

OR

1. d) Explain the node cover decision problem with an example. Prove that the problem is NP-complete.                                                                                                                    (15)

 

Go To Main page

 

 

 

 

 

 

Latest Govt Job & Exam Updates:

View Full List ...