LOYOLA  COLLEGE (AUTONOMOUS), CHENNAI-600 034.

M.Sc. DEGREE  EXAMINATION  – mathematics

FourTh SEMESTER  – APRIL 2003

MT  4952/ M  1057    computer Algorithms

26.04.2003

1.00 – 4.00                                                                                            Max: 100 Mark

 

Answer ALL questions. Each question carries 25 marks

 

I  a)   (i)   Give procedure SEARCH to search for an element x in an array A(1:n)

and to return k if a(k) = x and zero otherwise.

(ii)   Give a recursive produce to find GCD of 2 accepted numbers.        (OR)

1. b) Give a procedure to create a leap of n elements, inserting one item, at a time.    (8)
2. c) (i)   Discuss: Analyzing  algorithms in general

(ii)   Explain the conditional statements and loop structures in SPARKS. (OR)

1. d) Give HEAPSORT to sort numbers in an array. Simulate it on

A(1:6)  = (14,17,25,12,13,7)                                                                       (17)

 

II a)  Give procedure BINSRCH and simulate it on

A(1:7) = (45,  70,  82,  90,  95, 100, 110)when x = 46.(OR)

1. b) Give procedure MAXMIN and find its  best, worst and average lese number

of comparisons when n is a power of 2.                                                              (8)

1. c) Give procedure MERGESORT

If the time for merging operation is proportional to n, then find the computing

time ד (n) for MERGESORT.  When n = 2^k, prove that ד(n) =O(n log n)  (OR)

1. Give procedure SELECT to find the k^th  smallest element in an array simulate it on

A(1:8) = (14, 12, 61, 60, 17, 20, 6, 10 )  to find the 3^rd  smallest element.  (17)

 

III a)  Explain the problem of optimal storage on rapes. With usual notation.

if l₁ £ l₂ £ .-.£ l_n then prove that  the ordering i_j = j_i £ n minimizes

outing over all possible permutations of the i_j .                                          (OR)

1. State a greedy algorithm to generate shortest paths from a given vertex to

all other  vertices in a graph.                                                                                 (8)

1. Give line procedure due to krushkal to find a minimum sparring tree of a graph.

Prove also that Kruskal’s algorithm generates a minimum cost sparring

tree for every corrected undirected graph G.                                            (OR)

1. State procedure GREEDY- With used notation, if

p₁|w₁³ p₂|w₂ ³ …³ p_n|w_n , then prove that  GREEDY- KNAPSACK generates

an optimal solution to the given instance of the knapsack problem.                  (17)

 

IV  a)   Explain sum of subsets problem and give 2 different formulations for the same.

(OR)

1. b) Explain in detail low backtracking works on the 4 -queen problem.                 (8)
2. c) (i)  Give recursive backtracking algorithm for sum of subsets problem

(ii)  State procedure MCOLO RING to find all m-colorings in a graph.

(OR)

1. d)   Define a hamiltonian cycle.Give an example of (i)  a hamiltonian graph.

(ii) Give algorithm HAMITONIANJ to generate all hamiltonian cycles in a graph   (17)

 

Go To Main page

 

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