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

Latest Govt Job & Exam Updates:

View Full List ...