LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

XZ 29

M.Sc. DEGREE EXAMINATION – MATHEMATICS

FIRST SEMESTER – APRIL 2008

    MT 1808 – COMPUTER ALGORITHMS

 

 

 

Date : 06/05/2008            Dept. No.                                        Max. : 100 Marks

Time : 1:00 – 4:00

Answer ALL questions. Each question carries 20 marks

 

1    a.   Define a queue. Give an algorithm to delete an element from a circular queue.

OR

1. Give algorithm INSERT used to form a heap on n elements. (5)

 

1. (i) Discuss in detail how to analyze algorithms.

(ii)  Define a binary tree. Give the parent, left child and the right child of a node of a binary                     tree labeled j.                                                                                  (9+6)

OR

1. State algorithm HEAPSORT. Simulate it on a(1:5) = ( 67,23,12,78,90).         (15)

 

2    a.   Draw the tree of calls of MERGESORT when n =13.

OR

1. State algorithm PARTITION to partition the array a[m:p-1] about a[m].        (5)

 

89. State algorithm BINSRCH. Simulate it on a(1:10) = (12, 23, 34, 45, 56, 67, 78, 89, 90, 98 ) to search for (i) x = 34 (ii) x = 80 (iii) x = 89. Draw the binary decision tree when n = 10.

OR

1. State algorithm MERGESORT. Show that the computing time for MERGESORT is O(n log n ) where n is the number of inputs.                                                                                (15)

 

3    a.   Give the control abstraction for greedy method.

OR

1. Explain the ‘optimal storage on tapes’ problem with an example.        (5)

 

1. Explain the problem ‘job sequencing with deadlines’. Describe a greedy method to solve it and prove that the method always obtains an optimal solution to the job sequencing problem.

OR

1. State algorithm GREEDY KNAPSACK  and prove that it generates an optimal solution to the given instance of the knapsack problem.                                                                         (15)

 

4    a.   Explain two different formulations of ‘sum of subsets’ problem.

OR

1. Define inorder traversal of a tree with an example.        (5)

 

1. Explain how backtracking works on 4-queens problem. State algorithm NQUEENS.

OR

1. State an algorithm for breadth first graph traversal. Draw a graph on 8 vertices and explain the concept. Also explain depth first graph traversal showing how it differs from breadth first graph traversal.                                                                                     (15)

5    a.   Write note on ‘Nondetermininistic Algorithms’.

OR

1. What is a formula in propositional calculus? When is it said to be in                           (i) conjunctive normal form and (ii) disjunctive normal form.                       (5)

 

1. Explain the clique decision problem Prove that CNF-satisfiability α clique decision problem

OR

1. Define a node cover for a graph with an example. Prove that the clique decision problem α the node cover decision problem.                         (15)

 

Go To Main page

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