54109-mt----algorithm Analysis & Design

NR

Code No: 54109/MT M.Tech. – I Semester Supplementary Examinations, September, 2008 ALGORITHM ANALYSIS & DESIGN (Embedded Systems) Time: 3hours

Max. Marks:60 Answer any FIVE questions All questions carry equal marks ---

1.

What is time and space complexity? Give and explain asymptotic notations with suitable examples.

2.a) b)

What is P and NP-complete problem? Prove that the color ability problem is NP-complete even if K is restricted to 3 and the maximum degree of any vertex is 4.

3.

Write an algorithm to find residues of a polynomial modulo a collection of polynomial moduli.

4.

Write the fast Fourier transform algorithm with an example.

5.

What do you mean by forward and backward approach of problem solving in dynamic programming and explain the algorithms.

6.

Write an algorithm to search an element in a list using binary search technique and derive time complexites.

7.

Write and explain a procedure for in order traversal of a tree with example and analyze the time and space complexity.

8.

Explain set representation using trees and develop algorithms for UNION and FIND using weighting and collapsing rules. ^*^*^