Indus Institute of Technology & Engineering

Computer Science & Engineering Department

=====================================================
Design and Analysis of Algorithms
CE0516
=====================================================

Unit 1
Sr. No. Part - 1 : Basics of Algorithms and Mathematics
TOPIC:1 What is an algorithm? Mathematics for Algorithmic Sets
1 Explain the terms with example: Set

2 What is an Algorithm?
OR
Define Algorithm.

3 List types of algorithms.

4 What is an algorithm? Explain characteristics of any algorithm.

OR
Define algorithm. Discuss key characteristics of algorithms.
OR
What is algorithm? Explain with example. Which are the characteristics of
algorithm?

5 Define an algorithm. List various criteria used for analysing an algorithm.

6 Define Algorithm. Discuss factors affecting time complexity of an algorithm.

7 Define Algorithm, Time Complexity and Space Complexity.

TOPIC:2 Function and Relations, Vectors and Matrices

1 Explain the term with example: Relation

2 Explain the term with example: Function

3 What is a vector? Which operations are performed on vectors?

4 What is the relation? Explain equivalence relation.

5 What is a matrix? Explain the various operations which can be performed on

Page no. 1
 the matrix.

Sr. No. Part - 2 : Analysis of Algorithm

TOPIC:1 Average, Best and Worst Case Analysis, Amortized
Analysis, Asymptotic Notations
1 What is the worst case time complexity?

2 Define: Order of Growth.

3 Total Frequency Count for given code is =__________

for ( i=1; i<= n ; i++)

{
printf(“%d” , a[i] )
}

4 Two main measures for the efficiency of an algorithm are

A). Processor and memory

B). Complexity and capacity
C). Time and space
D). Data and space

5 What is an algorithm? Why analysis of algorithm is required?

6 Explain why analysis of algorithms is important? Explain: Worst Case, Best

Case and Average Case Complexity with suitable examples.

7 Discuss best case, average case and worst case asymptotic analysis. When
do best case, average case and worst case occur if you want to find out an
item from an array of n items.

8 Why do we use asymptotic notations in the study of algorithms? Briefly

describe the commonly used asymptotic notations.

9 What is meaning of T (n) =O(1). Explain with suitable example.

10 What are the different parameters to analyze any algorithm?

11 What is the smallest value of n such that an algorithm whose running time is
100n2 runs faster than an algorithm whose running time is 2n on the same
machine?

12 An asymptotically fast algorithm running on Slow computer is better than

asymptotically slow algorithm is running on fast computer for larger input
size. (True/False) Justify your answer with supporting arguments.

13 Prove or disprove that f(n) = 1 + 2 + 3 + … + n ∈Θ(n2).

14 What is an amortized analysis? Explain accounting method and aggregate

analysis with suitable example.

15 Let f(n) and g(n) be asymptotically positive functions. Prove or disprove

following.f(n) + g(n) = Θ(min( f(n), g(n))).
Page no. 2
16 Let f(n) and g(n) be asymptotically non-negative functions. Using the basic
definition of Ɵ-notation, prove that max(f(n), g(n)) = Ɵ(f(n)+g(n)).

17 If T1(n) = O(f(n)) & T2(n) = O(g(n)) then prove that T1(n) + T2(n) =
max(O(g(n)), O(f(n))).

18 Prove that (n + a)b = Ө( nb), b>0

19 Find upper bound of function f(n)= lg(n2) + n2lg n.

20 Is 2n+1 = Ο (2n)? Explain.

21 Prove that T(n) = 1+2+3+….+n = Θ(n2).

22 Find out time complexity for the following pseudo code using O-notation.
for(i = 0; i< n; i++)
{
for(j = n ; j > 0 ; j--)
{
if( i< j )
c = c + 1;
}
}

23 What is the average case time complexity of bubble sort?

24 Explain Bubble sort algorithm. Derive the algorithmic complexity in Best

case, worst case and Average case analysis.

25 Write and analyze an insertion sort algorithm to arrange n items into

ascending order.

26 Sort given array A = {27, 46, 11, 95, 67, 32, 78} using insertion sort
algorithm. Also perform best case and worst case analysis of insertion sort
algorithm.

27 Sort the letters of word “DESIGN” in alphabetical order using bubble sort.

28 Apply the bubble sort algorithm for sorting{U,N,I,V,E,R,S}. Write its algorithm
& Also derive its time complexity.

29 Sort the letters of word “EXAMPLE” in alphabetical order using insertion sort.

Page no. 3
 Unit 2
Sr. No. Part - 1 : Divide and Conquer Algorithm
TOPIC:1 Introduction
1 How divide and conquer approach work?

2 What is Divide and Conquer Technique? Explain how to apply divide and
conquer technique for solving the problem?

3 What do you mean by Divide & Conquer Approach? List advantages and
disadvantages of it.

TOPIC:2 Recurrence and Different Methods to Solve Recurrence

1 Write iterative and recursive algorithm for finding the factorial of N. Derive
the time complexity of both algorithms.

2 Give the recursive algorithm to find Fibonacci sequence. Comment on the

complexity of the algorithm.

3 Explain in brief: Recurrence Relations

4 What is recurrence? Solve recurrence equation T (n) = T (n-1) + n using

forward substitution and backward substitution method.

5 Explain master Method and solve the following recurrence equation with
master method
a. T(n)= 9T(n/3) + n
b. T(n)= 3T(n/4) + nlgn
c. T(n)= T(n/2) + 1
d. T(n)= 7T(n/3) + n2

TOPIC:3 Problem Solving using Divide and conquer algorithms

1 Which searching algorithm required Sorted list of elements?

2 Explain the use of Divide and Conquer Technique for Binary Search Method.
Give the algorithm for Binary Search Method. What is the complexity of
Binary Search Method?

3 Analyze quick sort algorithm for best case, average case and worst case
with example. In which case it performs similar to selection sort?

4 Explain how multiplication of large integers can be done efficiently by using

divide and conquer technique?

5 Explain how divide and conquer method help multiplying two square
Matrices.
OR
Explain Strasson’s algorithm for matrix multiplication.

Page no. 4
 6 Write an algorithm for quick sort and derive best case, worst case using
divide and conquer technique also trace given data (3,1,4,5,9,2,6,5)

7 Write Merge sort algorithm and compute its worst case and best-case time
complexity.
Sort the List G,U,J,A,R,A,T in alphabetical order using merge sort.

8 Write divide and conquer algorithm to solve Exponential problem. Also solve
29 using same algorithm.

9 Demonstrate Binary Search method to search Key = 14, form the array
A=<2,4,7,8,10,13,14,60>

10 Apply merge sort algorithm on array A = {2,7,3,5,1,9,4,8}. What is time

complexity of merge sort in worst case?

11 Multiply 981 by 1234 by divide and conquer method.

12 Sort the following list using quick sort algorithm:< 5, 3 ,8 ,1 ,4 ,6 ,2 ,7 > Also
write Worst and Best case and Average case of quick sort algorithm.

Sr. No. Part - 2 : Greedy Algorithm

TOPIC:1 General Characteristics of Greedy Algorithm
1 Define: Optimal Solution

2 What is the basic nature of greedy strategy?

3 What is meant by an optimal solution for a given problem?

4 Define the terms: Principal of Optimality

5 Give the characteristics of Greedy Algorithms.

6 Briefly describe greedy choice property and optimal substructure.

TOPIC:2 Problem Solving using Greedy Algorithms

1 Mention applications of minimum spanning tree.

2 Suppose that we have a set of activities to schedule among a large number

of lecture halls, where any activity can take place in any lecture hall. We wish
to schedule all the activities using as few lecture halls as possible. Give an
efficient greedy algorithm to determine which activity should use which
lecture hall.

3 Write greedy algorithm for activity selection problem. Give its time
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), I6(7-9).

4 Give and Explain the Prim’s Algorithm to find out Minimum Spanning Tree
with illustration.

5 Give and Explain the Kruskal’s Algorithm to find out Minimum Spanning Tree
with illustration.
Page no. 5
6 Define spanning tree and MST. How Krushkal’s algorithm is different from
Prim’s algorithm.

7 Design and explain Dijkstra’s shortest path algorithm.

8 What are the differences between greedy approach and dynamic

programming approach? Given n jobs J1 , J2, ….Jn having execution
deadlines d1 , d2, …, dn. Design an algorithm using greedy approach to
schedule these jobs as per earliest deadline first.

9 Examples of Prim’s & Kruskal’s Algorithm.

Page no. 6
Page no. 7
Page no. 8
10 Using greedy algorithm find an optimal solution for knapsack instance n=7,
M = 15 (P1, P2, P3, P4, P5, P6, P7) = (10, 5, 15, 7, 6, 18, 3) and (w1, w2,
w3, w4, w5, w6, w7) = (2, 3, 5, 7, 1, 4, 1).

11 Consider Kanpsack capacity W=50, w=(10,20,40) and v=(60,80,100) find the

maximum profit using greedy approach

12 Solve the following knapsack problem using greedy method. Number of

items = 5, knapsack capacity W – 100, weight vector = {50,40,30,20,10} and
profit vector = {1,2,3,4,5}.

13 Consider the instance of the 0/1 (binary) knapsack problem as below with P
depicting the value and W depicting the weight of each item whereas M

Page no. 9
 denotes the total weight carrying capacity of the knapsack. Find optimal
answer using greedy design technique. Also write the time complexity of
greedy approach for solving knapsack problem. P = [40 10 50 30 60] W =
[80 10 40 20 90] M = 110

14 Using greedy algorithm find an optimal schedule for following jobs with n=7
profits: (P1, P2, P3, P4, P5, P6, P7) = (3, 5, 18, 20, 6, 1, 38) and deadline
(d1, d2, d3, d4, d5, d6, d7) = (1, 3, 3, 4, 1, 2, 1)

15 Using greedy algorithm find an optimal schedule for following jobs with n=6.
Profits: (P1, P2, P3, P4, P5, P6) = (20, 15, 10, 7, 5, 3)
Deadline: (d1, d2, d3, d4, d5, d6) =(3, 1, 1, 3, 1, 3)

16 Find single source shortest path using Dijkstra’s algorithm form a to e.

17 Consider Knapsack capacity W=15, w = (4, 5, 6, 3) and v=(10, 15,12, 8) find

the maximum profit using greedy method.

Page no. 10