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

 

Latest Govt Job & Exam Updates:

View Full List ...