DEPARTMENT OF
B.Tech (5th Sem) – II
ASSIGNMENT-1 COMPUTER SCIENCE
Design and Analysis of
AND ENGINEERING
Algorithms
AGCS-21501
Question Sets
Set 1: Question Number 1, 3, 12, 13, 21, 22, 32, 38, 43
Set 2: Question Number 5, 6, 14, 16, 24, 27, 33, 39, 45
Set 3: Question Number 8, 9, 18,20, 28, 29, 36, 41, 48
Allocation of Question Sets to students
Set Uni. Roll No.
2333336, 2333337, 2333341, 2333344,2333345, 2333346, 2333347, 2333348,2333353, 2333355,
1 2333357,2333364, 2333367, 2333368, 2333369,2333373, 2333380, 2333382, 2333385,2333392,
2333393, 2333394,2333395,2333396, 2333401, 2333402
2233592,2333335, 2333338, 2333340, 2333342,2333350, 2333354, 2333358, 2333360,2333362,
2 2333366, 2333371,2333375,2333378, 2333381, 2333384, 2333386, 2333387,2333388, 2333390,
2333391, 2333398,2333399 2333400
2333334, 2333339, 2333343, 2333349,2333351, 2333352, 2333359,23333363, 2333365,2333370,
3 2333372, 2333374,2333376, 2333379, 2333397, 2333403
Q. No Section A (2 marks each) CO
1. Define time and space complexity. Explain with examples.
2. Explain the process of designing an algorithm. Give characteristics of an
algorithm.
3. Give the two major phases of performance evaluation
4. Write down the properties of asymptotic notations. CO-1
5. Write short note on Fundamentals of Algorithmic Problem Solving.
6. Explain iterative Algorithm Design Issues?
7. Contrast and compare between iterative and recursive process with an example?
8. Prove that f(n)= O(g(n)) and g(n)=O(f(g(n)) then f(n)=(g(n))
9. Compare the order of growth n(n-1)/2 and n2.
10. Explain how many algorithms can you write for solving find the prime
numbers. Compare which is the simplest and the most efficient.
11. Define Optimal Substructure.
12. Give the general procedure of divide and conquer method
13. Show the recurrence relation of divide-and-conquer?
14. For T(n)=7T(n/2)+18n2 Solve the recurrence relation and find the time
complexity.
15. Where the max element does reside in the max heap?
16. Write a recursive algorithm for Quick sorting using Partition Algorithm CO-2
17. Sort the list of numbers using merge sort: 78, 32, 42, 62, 98, 12, 34, 83
18. What do you mean by worst case analysis of randomized quick sort?
19. Solve the following using Master’s Method
a. T(n)=3T(n/2)+2n2
b. T(n)=4T(n/2)+n2
20. Solve the following using Recurrence Tree Method
T(n)=3T(n/4)+c.n2
21. State dynamic programming. Explain with one application. 3
22. Write the difference between 0/1 knapsack and fractional knapsack.
23. Find the LCS between A = shortest and B=longest
24. Give the definition for 0/1 knapsack problem.
25. Show the general procedure of dynamic programming
26. Find the LCS between A=hindustan and B=indian
27. Solve the solution for 0/1 knapsack problem using dynamic programming N=3 , CO-3
m=6 profits (p1,p2,p3) = (1,2,5) weights (w1,w2,w3) = (2,3,4)
28. Solve the following using Knapsack Problem n=3,m=20
(P1,P2,P3)=(24,25,15),(W1,W2,W3)=(18,15,10) using fractional Knapsack
29. Find the LCS between A = 1,0,0,1,0,1,0,1 and B= 0,1,0,1,1,0,1,1,0
30. How many multiplications are required to multiply where the dimensions are
d0=4, d1=8,d2=2,d3=6,d4=7.
Section B (4 marks each)
31. Describe performance analysis, space complexity and time complexity.
32. Explain in detail about asymptotic notations.
33. Define time complexity and space complexity. Write an algorithm for adding n
natural numbers and find the space required by that algorithm.
34. If f(n)=5n2 + 6n + 4, then prove that f(n) is O(n2 ) CO-1
35. Find theta notation for:
a) F(n)= 3n4+5n+76
b) F(n)= 2n3+n2+2n
c) F(n)= 27n2+16n+25
d) F(n)= 5n3+n2+3n+2
36. What is the order of the computation for the following loop.
for(i=1,i<n,i+1)
for(j=1,j<n,j+1)
37. Write an algorithm for linear search and analyze the algorithm for its time
complexity.
38. Write an algorithm for Binary search and discuss its complexity.
39. Simulate Quick sort algorithm for the following example
25,36,12,4,5,16,58,54,24,16,9,65,78
40. Illustrate Merge sort algorithm and discuss its time complexity
41. Discuss the General plan for analyzing efficiency of Non recursive & Recursive
CO-2
algorithms Understand and Insertion Sort with example?
42. Derive the time complexity of Heap sort using Recurrence and Back
Substitution.
43. Explain matrix chain multiplication with suitable example.
44. What is meant by dynamic programming? Give the recurrence relation for
dynamic programming. CO-3
45. Find the cost of the route using travelling Salesman problem.
46. Give the algorithm for matrix multiplication and find the time complexity of the
algorithm using step count method
47. Consider the chain matrix A1,A2 & A3 with dimensions given below. Give the
optimal parentheses to get the product. Matrix Dimensions A1 5 X 10 A2 10 X
20 A3 20 X 25
48. Write the algorithm to compute 0/1 Knapsack problem using dynamic
programming and explain it.
