Scribd
Upload
25 views

Question Bank IA1

This document is a question bank for the course 'Design & Analysis of Algorithms' (CSE23402) at the Global Academy of Technology. It includes a variety of questions covering topics such as algorithms, time complexity, asymptotic notations, and sorting techniques. The questions require explanations, pseudocode, and examples to demonstrate understanding of algorithm design and analysis.

Uploaded by

pbcshetty.library
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
25 views

Question Bank IA1

This document is a question bank for the course 'Design & Analysis of Algorithms' (CSE23402) at the Global Academy of Technology. It includes a variety of questions covering topics such as algorithms, time complexity, asymptotic notations, and sorting techniques. The questions require explanations, pseudocode, and examples to demonstrate understanding of algorithm design and analysis.

Uploaded by

pbcshetty.library
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Department of Computer Science and Engineering

Global academy of Technology


IA 1Question Bank

Course Title with code: Design & analysis of


Algorithms(CSE23402)

1. Define Algorithm? Explain the notion of an algorithm and list out its important
properties.
2. Discuss various algorithms to calculate GCD of 2 numbers.
3. With a pseudocode, Explain Sieve of Eratosthenes algorithm. Trace the same for
n=50.
4. With an example, discuss how to find the time complexity of an algorithm.
5. Find the time complexity of the following codes.
i)

ii)

6. Write a note on various efficiency classes of an algorithm.


7. With a neat flowchart, discuss the process of designing and analysing process of an
algorithm.
8. What are asymptotic notations? Discuss the various types of asymptotic notations.
9. Discuss the general plan to find the time complexity of non-recursive algorithm with
an example.
10. Discuss the general plan to find the time complexity of recursive algorithm with an
example.
11. Setup the recurrence for solving tower of Hanoi problem and solve it using
substitution method.
12. Discuss the Master’s theorem used to find the time complexity of an algorithm. (All
three cases with an example)
13. Apply master’s theorem for the following recurrence
i) c(n) = 2c(n/2) + n-1
ii) T(n) = 8T(n/3) + n4
14. If t1(n) € O (g1(n)) and t2(n) € O (g2(n)) then prove that t1(n) + t2(n) € O(max(g1(n),
g2(n)).
15. For each of the following algorithms, indicate (i) a natural size metric for its inputs;
(ii) its basic operation; (iii) whether the basic operation count can be different for
inputs of the same size:
a. Computing the sum of n numbers
b. Computing n!
c. Finding the largest element in a list of n numbers
d. Euclid’s algorithm
e. Sieve of Eratosthenes
17. Use the informal definitions of O, Θ, and Ω to determine whether the following

a. n(n + 1)/2 ∈ O(n3) b. n(n + 1)/2 ∈ O(n2)


assertions are true or false.

c. n(n + 1)/2 ∈ Θ(n ) 3


d. n(n + 1)/2 ∈ Ω(n)
18. Order the following functions according to their order of growth (from the lowest to the
highest):

19. Consider the following algorithm.


Algorithm Mystery( n)
//Input: A nonnegative integer n
S←0

S←S+i∗i
for i ← 1 to n do

return S
a. What does this algorithm compute?
b. What is its basic operation?
c. How many times is the basic operation executed?
20. Consider the following recursive algorithm.
Algorithm Q(n)
//Input: A positive integer n

else return Q(n − 1) + 2 ∗ n − 1


if n = 1 return 1

a. Set up a recurrence relation for this function’s values and solve it to


determine what this algorithm computes.
b. Set up a recurrence relation for the number of multiplications made by this
algorithm and solve it.
c. Set up a recurrence relation for the number of additions/subtractions made
by this algorithm and solve it.
21. Sort the list E, X, A, M, P, L, E in alphabetical order by bubble sort and find the
number of comparison and swaps done.
22. Sort the list E, X, A, M, P, L, E in alphabetical order by Selection sort and find the
number of comparison and swaps done.
23. With a pseudocode, discuss the time complexity of Selection Sort.
24. With a pseudocode, discuss the time complexity of Bubble Sort.
25. Discuss the general plan of solving the problem using divide and conquer.
26. Write algorithm or program of Merge sort.Discuss the time complexity of Merge sort
27. Sort the list E, X, A, M, P, L, E in alphabetical order by Merge sort and find the
number of comparison done.
28. Write algorithm or program of Quick sort. Discuss the time complexity of Quick sort
for all three cases.
29. Sort the list E, X, A, M, P, L, E in alphabetical order by Merge sort and find the
number of comparison done.

You might also like