Ahmedabad Institute of Technology
CE & IT Department
Analysis and Design of Algorithms (3150703)
Question- Answer Assignment
Assignment -1 (Write any 20 Questions out of 30) -20 Marks
1 What is an algorithm? Explain various properties of an algorithm.Discuss 7
key characteristics of algorithm.
2 (i)Explain why analysis of algorithms is important? Explain: Worst Case, 7
Best Case & Average Case Complexity. (ii) Define: Optimal Solution,
Feasible solution, Principle of Optimality.
3 Write an algorithm of Selection Sort Method. Give its best case, worst 7
case and average case complexity.
4 Explain Asymptotic notation. Arrange the growth rate of 2 n , n 2 ,1, log 7
n, n logn, 3 n and n in increasing order of growth.
5 Write the Master theorem. Solve following recurrence using it. 7
(i) T(n)=9T(n/3) + n (ii) T(n)=3T(n/4) + nlgn
6 What is an amortized analysis? Explain aggregate method of amortized 7
analysis using suitable example.
7 Analyze quick sort algorithm for best case, average case and worst case 7
with example. In which case it performs similar to selection sort?
8 Explain the use of Divide and Conquer Technique for Binary Search 7
Method.What is the complexity of Binary Search Method? Explain it with
example.
9 What are the differences between greedy approach and dynamic 7
programming?
10 Solve Making change problem using dynamic technique. d1 = 1, d2=2, 7
d3=4, d4=6, Calculate for making change of Rs. 10.
11 Explain Chained Matrix Multiplication with example. 7
12 Explain Depth First Traversal Method for Graph with algorithm with 7
example.
13 Explain Backtracking Method. What is N-Queens Problem? Give solution 7
of 4-Queens Problem using Backtracking Method.
14 Find all pair of shortest path using Floyd’s Algorithm for given graph 7
15 Explain in Breif: 7
P Problem, NP Problem, NP Hard Problem, NP Complete Problem
16 What is recurrence? Explain recursion-tree method with suitable example. 7
17 Solve following recurrence relation using suitable method and express 7
your answer using Big-oh (O) notation.
T(n) = T(n/3) + T(2n/3) + Ө(n)
18 Solve following recurrence relation using suitable method and express 7
your answer using Big-oh (O) notation.
T(n) = 2 T(n/2) + n2
19 Write sequential search algorithm and analyze it for worst case time 7
complexity. Represent its time complexity using Big-oh (O) notation
20 Write greedy algorithm for activity selection problem. Give its time 7
complexity. For following intervals, select the activities according to
your algorithm. I1 (1-3), I2 (0-2), I3 (3-6), I4 (2-5), I5 (5-8), I6 (3-10), I7(7-9)
21 Find the optimal way of multiplying following matrices using dynamic 7
programming. Also indicate optimal number of multiplications required.
A:3 x 2, B: 2 x 5, C:5 x 4, D: 4 x 3, E: 3 x 3
22 What is a minimum spanning tree? Draw the minimum spanning tree 7
correspond to following graph using Prim’s
algorithm.
23 Find the longest common subsequence for the following two sequences using 7
dynamic programming. Show the complete process.
X = 100101001
Y = 101001
24 Write and explain Dijkastra algorithm with example. 7
25 Explain naïve string matching algorithm with example. 7
26 Explain Rabin – Karp algorithm with example. What is expected 7
running time of this algorithm?
27 State whether Hamiltonian problem is a NP-Complete problem? 7
Justify your answer
28 Solve the following instance of knapsack problem using Backtracking 7
Technique. The Capacity of the Knapsack W = 8 and w = (2,3,4,5) and value v =
(3,5,6,10)
29 Generate minimum spanning tree using Kruskal's algorithm for the followin 7
graph.
30 Find an optimal Huffman code for the following set of frequency. a : 50, b: 20, c: 7
15, d: 30.
Prof. Heena Panjwani & Prof. Neha Prajapati Dr. Ajay N. Upadhayaya
Assistant Professor, CE Dept., AIT HOD CE & IT Dept., AIT
Ahmedabad Institute of Technology
CE & IT Department
Analysis and Design of Algorithms (3150703)
Innovative Assignment (20 Marks)
Kindly Choose Any Online Course from the Following:
Sr. Name of Course Platform Total No. of Weeks
No
1 Algorithmic Toolbox by University of california Coursera 6 Weeks
san Diego
2 Greedy Algorithms, Minimum Spanning Trees, and Coursera 4 Weeks
Dynamic Programming by Stanford
Prof. Heena Panjwani & Prof. Neha Prajapati Dr. Ajay N. Upadhayaya
Assistant Professor, CE Dept., AIT HOD CE & IT Dept., AIT
