Scribd
Upload
45 views2 pages

Unit - 1 Assignment

Uploaded by

Mithun
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
45 views2 pages

Unit - 1 Assignment

Uploaded by

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

Course: BCA, Year: 2nd, Semester: IV (IBM & B)

Subject Name: Design & Analysis of Algorithms


Subject Code: CAUCBC403T
UNIT – 1
ASSIGNMENT
SHORT ANSWER TYPE QUESTIONS
1. What is an Algorithm?
2. What is algorithm Design Technique?
3. Differentiate Time and Space efficiency?
4. Design an algorithm to compute the area and Circumference of a circle.
5. How will you measure input size of an algorithms.
6. Define best, worst and average case efficiency?
7. Define big oh (O), Big omega (Ω) and big theta (Ө) notations.
8. List the basic efficiency classes.
9. Define recurrence relation.
10. What is non recursion relation?
11. Define non-recursive algorithm.
12. Consider the following algorithm:
a. S=0
b. for i=1 to n do
c. S=S+i
d. return i
What does this algorithm compute? How many times is the basic operation executed?
13. Write an algorithm using recursive function to find the sum of n numbers.
14. What is algorithm optimality?
15. List the factors which affects the running time of the algorithm.
16. What is meant by substitute methods?
17. Write the general plan for analyzing Time efficiency of recursive algorithm.

LONG ANSWER TYPE QUESTIONS


1. Discuss in detail about fundamentals of algorithmic problem solving.
2. Explain the necessary steps for analyzing the efficiency of recursive algorithms.
3. Explain the general framework for analyzing the efficiency of an algorithm.
4. Write the asymptotic notations used for best-case, average-case and worst-case analysis of
algorithms. Also write an algorithm for finding maximum element of an array and perform
best, worst and average case complexity with appropriate order notations.
5. Explain the method of solving recurrence equations with suitable example.
6. Explain the method of solving non-recursive equations with suitable examples.
7. Answer the following:
(i) Describe the basic efficiency classes in detail.
(ii) Write an algorithm for Fibonacci numbers generation and compute the following:
a) How many times is the basic operation executed?
b) What is the efficiency class of this algorithm?
8. Solve the following recurrence relations:
a) x(n)=x(n -1) + 5 for n > 1 x(1)=0
b) x(n)=3x(n-1) for n > 1 x(1)=4
c) x(n)=x(n-1)+n for n > 0 x(0)=0
d) x(n)=x(n/2)+n for n > 1 x(1)=1 ( solve for n=2k)
e) x(n)=x(n/3)+1 for n >1 x(1)=1 (solve for n=3k)
9. Consider the following recursion algorithm:
• Min1(A[0 --- n-1])
• If n=1 return A[0]
• Else temp = Min1(A[0… n-2])
• If temp <= A[n-1] return temp
• Else
• Return A[n-1]
a) What does this algorithm compute?
b) Setup a recurrence relation for the algorithms basic operation count and solve it.
10. Proof that worst-case time complexity of Merge Sort is O(nlogn). Mention all the steps
clearly.
11. Proof that worst-case time complexity of Quick Sort is O(n2). Mention all the steps clearly.
12. Proof that best- case time complexity of Merge Sort is O(nlogn). Mention all the steps
clearly.
13. Bubble sort time complexity in best case is O(n) but in worst case complexity is O(n2).
Why? Proof with an example.
14. If the given array A is [2, 6, 9, 12, 23, 44, 55, 67, 87, 99]. If quick sort is performed and
pivot element is last element of the array. What will be the time complexity of program.
15. Heap sort algorithm time complexity is O(nlogn). Why? Explain clearly.

You might also like