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)
- b) Give a procedure to create a leap of n elements, inserting one item, at a time. (8)
- c) (i) Discuss: Analyzing algorithms in general
(ii) Explain the conditional statements and loop structures in SPARKS. (OR)
- 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)
- b) Give procedure MAXMIN and find its best, worst and average lese number
of comparisons when n is a power of 2. (8)
- c) Give procedure MERGESORT
If the time for merging operation is proportional to n, then find the computing
time ד (n) for MERGESORT. When n = 2k, prove that ד(n) =O(n log n) (OR)
- Give procedure SELECT to find the kth smallest element in an array simulate it on
A(1:8) = (14, 12, 61, 60, 17, 20, 6, 10 ) to find the 3rd smallest element. (17)
III a) Explain the problem of optimal storage on rapes. With usual notation.
if l1 £ l2 £ .-.£ ln then prove that the ordering ij = ji £ n minimizes
outing over all possible permutations of the ij . (OR)
- State a greedy algorithm to generate shortest paths from a given vertex to
all other vertices in a graph. (8)
- 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)
- State procedure GREEDY- With used notation, if
p1|w1³ p2|w2 ³ …³ pn|wn , 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)
- b) Explain in detail low backtracking works on the 4 -queen problem. (8)
- 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)
- 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)
Latest Govt Job & Exam Updates: