QQ1. Answer all questions.
- (a)) Design and develop an efficient algorithm to find all the prime numbers in the range 2 to 10000. Access the complexity of this algorithm? (100 words)
- (b)) Differentiate between Quadratic-time and Exponential-time algorithms. Give example of one problem each for these two running times. (100 words)
- (c)) A sorted array of size n contains several duplicate values. Design an algorithm to search a value in the array. The algorithm should output all the indexes where the searched value exists. Explain the worst time complexity of this algorithm. (100 words)
- (d)) Explain the Big Theta (Θ) and Big Omega (Ω) notations with the help of a diagram. What is the need of asymptotic bounds? Also, list the shortcomings of the asymptotic bounds. Find the Big O, and Ω bounds for the following function: f(n)= 999n^3+999999n+100 (200 words)
- (e)) Write the Right to Left binary exponentiation algorithm. Demonstrate the use of this algorithm to compute the value of 5^23. Show all steps of the computation. Explain the worst-case complexity of this algorithm. (200 words)
- (f)) Write and explain the Insertion sort algorithm. Discuss its best and worst-case time complexity. (150 words)
- (g)) What is a recurrence relations? When are they used? Solve the following recurrence relations using the Master's method: a. T(n) = 16T(n/4) + n² b. T(n) = 8T(n/2) + n² (150 words)