1. Explain Asymptotic notations in detail with example. (12 Marks) (Dec.2019/Jan.2020 | 17 Scheme)

2. Outline an algorithm to find maximum of n elements and obtain its time complexity. (08 Marks) (Dec.2019/Jan.2020 | 17 Scheme)

3. Design algorithm for tower of Hanoi problem and obtain time complexity. (10 Marks) (Dec.2019/Jan.2020 | 17 Scheme)

4. Prove the theorem

if f1(n) Є 0 (g, (n)) and f2(n) Є 0 (g2 (n)) Then f1(n) + f2(n) Є 0 (max {g1(n), g2(n)}) (10 Marks) (Dec.2019/Jan.2020 | 17 Scheme)

5. Design an algorithm to search an element in a array using sequential search. Discuss the worst case, best case and average case efficiency of this algorithm. (08 Marks) (June/July 2019 | 17 Scheme)

6. Discuss adjacency matrix and adjacency list representation of a graph with suitable example. (06 Marks) (June/July 2019 | 17 Scheme)

7. Give the recursive algorithm to solve towers of Hanoi problem. Show that the efficiency of this algorithm is exponential. (06 Marks) (June/July 2019 | 17 Scheme)

8. Give the general plan for analysing time efficiency of non-recursive algorithms. Derive the worst case analysis for the algorithm to check whether all the elements in a given array are distinct. (08 Marks) (June/July 2019 | 17 Scheme)

9. List and define any three asymptotic notations. What are the various basic asymptotic efficiency classes? (06 Marks) (June/July 2019 | 17 Scheme)

10. Explain the following types of problems: (i) Combinatorial problems (ii) Graph problems. (06 Marks}(June/July 2019 | 17 Scheme)

11. What is an algorithm? Summarize the properties of an algorithm. (04 Marks) (June/July 2019 | 15 Scheme)

12. Solve the following recurrence relation:

X(n) = x(n/2) + n for n>1, x(1) =2

Assume n= 2^k (06 Marks) (June/July 2019 | 15 Scheme)

13. Algorithm Test(n)

// Input: A non-negative integer 'n'

S ← 0

for I ← 1 to n do

for j ← 1 to n do

s ← s + i * j

return s

(i) What does this algorithm compute?

(ii) What is the basic operation?

(iii) How many times the basic operation executed?

(iv) What is the efficiency class of this algorithm? (06 Marks) (June/July 2019 | 15 Scheme)

14. With neat diagram summarize the steps used to solve a given problem using computer. (06 Marks) (June/July 2019 | 15 Scheme)

15. Consider the following algorithm:

Algorithm s(n)

{

If (n= 1) return 1,

Else return (s(n - 1) + n.n.n)

}

What does this algorithm? What is the basic operation? How many times the basic operation executed? (04 Marks) (June/July 2019 | 15 Scheme)

16. Design a recursive algorithm for computing factorial of a number n. Set up a recurrence relation and find its efficiency. (06 Marks) (June/July 2019 | 15 Scheme)

17. What is an algorithm? What are the properties of an algorithm? Explain with an example. (04 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

18. Explain the general plan for analysing the efficiency of a recursive algorithm, Suggest a recursive algorithm to find factorial of a number. Derive its efficiency. (08 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

19. If t₁(n) Є O(g₁ (n)) and t₂(n) Є O(g₂ (n)) prove that t₁(n) + t₂(n) Є O(max{ g₁(n), g₂(n)}). (04 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

20. Explain the asymptotic notations with examples. (06 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

21. Distinguish between the two common ways to represent a graph. (04 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

22. Discuss about the important problem types and fundamental data structures. (06 Marks) (Dec.2018/Jan.2019 | 15 Scheme)

23. Write an algorithm to find the maximum element in an array of n element. Give the mathematical analysis of this non-recursive algorithm. (06 Marks) (June/July 2018 | 15 Scheme)

24. Explain the asymptotic notations Big O, Big Ω and big theta used to compare orders of growth of an algorithm. (06 Marks) (June/July 2018 | 15 Scheme)

25. Explain with an example how a new variable count introduced in a program can be used to find the number of steps needed by a program to solve a particular problem instance. (04 Marks) (June/July 2018 | 15 Scheme)

26. Write a recursive function to find and print all possible permutations of a given set of n elements. (05 Marks) (June/July 2018 | 15 Scheme)

27. Solve the recurrence relation: M(n) = 2M(n - 1) + 1. Take M(1) = 1, M(n) is given for n > i (05 Marks) (June/July 2018 | 15 Scheme)

28. Define algorithm. What are the criteria that an algorithm must satisfy? (06 Marks) (June/July 2018 | 15 Scheme)

29. Define an algorithm. Discuss the criteria of an algorithm with an example. (06 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

30. Prove that: If t₁(n) Є O(g₁(n)) and t₂(n) Є O(g₂(n)) then t₁(n) + t ₂(n) Є 0 (max{g₁(n), g₂(n)}) (06 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

31. Explain the two common ways to represent a graph with an example (04 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

32. Consider the following algorithm

Algorithm GUESS(A[ ] [ ])

for i←0 to n -1

for j←0 to i

A [i][j] ← 0

i) What does the algorithm compute?

ii) What is basic operation?

iii) What is the efficiency of this algorithm? (03 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

33. List and explain important problem types that are solved by computer. (07 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

34. Design an algorithm for checking whether all elements in a given array are distinct or not. (Dec.2017/Jan.2018 | 15 Scheme)

35. Derive its worst complexity. (06 Marks) (Dec.2017/Jan.2018 | 15 Scheme)

36. Define algorithm. Explain asymptotic notations, Big O, big Omega, big theta notations. (08 Marks) (June/July 2017 | 15 Scheme)

37. Explain general plan of mathematical analysis of non-recursive algorithms with example. (08 Marks) (June/July 2017 | 15 Scheme)

38. Define time and space complexity. Explain important problem types. (08 Marks) (June/July 2017 | 15 Scheme)

39. Illustrate mathematical analysis of recursive algorithm for towers of hanoii. (08 Marks) (June/July 2017 | 15 Scheme)