SRM University 2007 B.Tech Computer Science and Engineering Bank : Design and Analysis of Algorithms - exam paper

S .R.M Institute of Science and Technology (Deemed University)
Department of computer Science and Engineering

Subject: Design and Analysis of Algorithms Subject Code: CS207
Year: II Semester: III
ques. Bank

Unit – I

PART A

1. What is an algorithm?
2. What are computational procedures?
3. What is a program?
4. Define Algorithm Validation.
5. Define program proving and program verification.
6. Define pseudocode.
7. What are the control structures in pseudocode?
8. Define Recursion. provide an example.
9. Define Time and space complexity.
10. Distinguish performance analysis and performance measurement.
11. What are the components of fixed and variable part in space complexity?
12. Define program step.
13. What are the methods to determine step count?
14. Define input data size.
15. Describe frequency table method.
16. Define best, avg. and worst case step count.
17. Define break-even point.
18. Define asymptotic notation.
19. Define Big Oh notation.
20. Define Theta notation.
21. Define Omega notation
22. Define little Oh and Little Omega notation.
23. What does O(1) mean?
24. How do you time a very short event?
25. What are the design techniques that are used to devise algorithms?
26. Define recursion. elaborate its types?
27. Write an algorithm to obtain if the provided no is Armstrong no? obtain its time complexity?
28. Differentiate algorithm and program.
29. Find the order of 20n3+100n2+2.


PART B
1. Explain Towers of Hanoi issue and solve it using recursion.
2. Find the time complexity and space complexity of the subsequent issues.
1) Factorial using Recursion.
2) Compute nth Fibonacci Number.
3) Compute xn or exponentiate (x,n).
4) mxn matrix multiplication
5) nxn matrix multiplication
6) mxn matrix addition.
7) Sequential/linear search.
3. Describe best, worst and avg. case analysis with an example.

UNIT II

PART A

1. What is divide and conquer technique?
2. Give the control abstraction for divide and conquer technique.
3. Write the recurrence relation for DandC.
4. Timecomplexity of Binary search is O(logn). Justify.
5. Write a straight forward max min algorithm.
6. Explain the greedy method.
7. Define feasible and optimal solution.
8. Write the control abstraction for greedy method.
9. What are the constraints of knapsack problem?
10. What is a minimum cost spanning tree?
11. Specify the algorithms used for constructing Minimum cost spanning tree.
12. State single source shortest path algorithm (Dijkstra’s algorithm).
13. Calculate the T(n) for the provided recurrence form
T(n) = T(1) if n=1
T(n) = aT(n/b)+f(n) if n>1
where a=2,b=2, T(1)=2, f(n)=n;

Earning:   Approval pending.