CS 252 _ ALGORITHMS AND DATA STRUCTURES
B.E./B.Tech.DEGREE EXAMINATION, NOVEMBER/DECEMBER 2007. Third Semester
Instrumentation and Control Engineering
CS 252 _ ALGORITHMS AND DATA STRUCTURES
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PARTA-(10 x2=2Dmarks)
1. State any two properties of a goodalgorithm.
2. Write down the asymptotic notations used for best case, average case and worst caseanalysis of algorithms.
3. Give an example for NP problem.
4. Differentiate between data and control structures of a program.
5. Why linear data structures are named so?
6. DefrneADT.
7. Give the post order traversal for the following tree.
' melon
/\
/\
grape pear
/\\
/\\
apple lemon Langerine
8. What is a heap? Give an example tree.
9. Distinguish between internal and external sorting techniques.
10. State why graph is termed as nonlinear data structure.
11. (a) (i)
PARTB-(Sx16=80marks)
Differentiate between deterministic and algorithms.
non deterministic
(8)
(ii) construct the binary search tree for the following input.
107L5 9 5L2 18
Delete the following nodes one by one
Node 15 followed bv node 12.
(8)
(b) (i)
(ii)
Or
Name and explain in brief any two mathematical proof techniques used for proving the correctnessof algorithms with an example. (10)
List down the benefits and drawbacks of recursive algorithms. (6)
12. (a)
(i)
write down the algorithm for finding the sum of 2 matrices of order
n x n each. Analyse the algorithm for best and worst case time
complexity.
(8)
(ii) Define the working backward method of solving problems with an
example.
(8)
Or
(b) (i) Define NP completeproblem with an example. (g)
(ii) What is heuristic algorithm? Explain the heuristic approach for reaching the goal with a sample problem. (g)
13' (a) (i) Explain an LIFO data structure and write down the proceduresfor insertion and deletion of elements using non sequential
implementation.
(ii) Explain an application for queue.
(12)
(4)
Or
(b) (i) Give the insertion and deletion algorithms for linked representation
ofa queuedata structure.
(ii) Explain how stack cErn be procedures.
(L2)
used for implementing recursive
G)
Instrumentation and Control Engineering
CS 252 _ ALGORITHMS AND DATA STRUCTURES
Time : Three hours Maximum : 100 marks
Answer ALL questions.
PARTA-(10 x2=2Dmarks)
1. State any two properties of a goodalgorithm.
2. Write down the asymptotic notations used for best case, average case and worst caseanalysis of algorithms.
3. Give an example for NP problem.
4. Differentiate between data and control structures of a program.
5. Why linear data structures are named so?
6. DefrneADT.
7. Give the post order traversal for the following tree.
' melon
/\
/\
grape pear
/\\
/\\
apple lemon Langerine
8. What is a heap? Give an example tree.
9. Distinguish between internal and external sorting techniques.
10. State why graph is termed as nonlinear data structure.
11. (a) (i)
PARTB-(Sx16=80marks)
Differentiate between deterministic and algorithms.
non deterministic
(8)
(ii) construct the binary search tree for the following input.
107L5 9 5L2 18
Delete the following nodes one by one
Node 15 followed bv node 12.
(8)
(b) (i)
(ii)
Or
Name and explain in brief any two mathematical proof techniques used for proving the correctnessof algorithms with an example. (10)
List down the benefits and drawbacks of recursive algorithms. (6)
12. (a)
(i)
write down the algorithm for finding the sum of 2 matrices of order
n x n each. Analyse the algorithm for best and worst case time
complexity.
(8)
(ii) Define the working backward method of solving problems with an
example.
(8)
Or
(b) (i) Define NP completeproblem with an example. (g)
(ii) What is heuristic algorithm? Explain the heuristic approach for reaching the goal with a sample problem. (g)
13' (a) (i) Explain an LIFO data structure and write down the proceduresfor insertion and deletion of elements using non sequential
implementation.
(ii) Explain an application for queue.
(12)
(4)
Or
(b) (i) Give the insertion and deletion algorithms for linked representation
ofa queuedata structure.
(ii) Explain how stack cErn be procedures.
(L2)
used for implementing recursive
G)
Comments
Post a Comment