DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

DAA LAB VIVA QUESTIONS

***************************SET I***************************

1. What is an algorithm?
An algorithm is a sequence of unambiguous instructions for solving a problem. i.e., for
obtaining a required output for any legitimate input in a finite amount of time

2. What are important problem types? (or) Enumerate some important types of problems.
1. Sorting 2. Searching
3. Numerical problems 4. Geometric problems
5. Combinatorial Problems 6. Graph Problems
7. String processing Problems

3. Name some basic Efficiency classes

1. Constant 2. Logarithmic 3. Linear 4. nlogn
5. Quadratic 6. Cubic 7. Exponential 8. Factorial

4. What are algorithm design techniques?

Algorithm design techniques ( or strategies or paradigms) are general approaches to solving
problems algorithmatically, applicable to a variety of problems from different areas of
computing. General design techniques are:
(i) Brute force (ii) divide and conquer
(iii) decrease and conquer (iv) transform and concquer
(v) greedy technique (vi) dynamic programming
(vii) backtracking (viii) branch and bound

5. How is an algorithm’s time efficiency measured?

Time efficiency indicates how fast the algorithm runs. An algorithm’s time efficiency is
measured as a function of its input size by counting the number of times its basic operation

Mamatha A, Asst Prof, Dept of IS E, SVIT Page 1

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

(running time) is executed. Basic operation is the most time consuming operation in the
algorithm’s innermost loop.

6. How is the efficiency of the algorithm defined?

The efficiency of an algorithm is defined with the components.

(i) Time efficiency -indicates how fast the algorithm runs
(ii) Space efficiency -indicates how much extra memory the algorithm needs

7. What are the characteristics of an algorithm?

Every algorithm should have the following five characteristics
(i) Input
(ii) Output
(iii) Definiteness
(iv) Effectiveness
(v) Termination
Therefore, an algorithm can be defined as a sequence of definite and effective instructions, which
terminates with the production of correct output from the given input.

8. Write general plan for analyzing non-recursive algorithms.

i. Decide on parameter indicating an input’s size.
ii. Identify the algorithm’s basic operation
iii. Checking the no.of times basic operation executed depends on size of input.
iv. Set up sum expressing the no.of times the basic operation is executed. depends on some
additional property,then best,worst,avg.cases need to be investigated (establishing order of
growth)

9. Define the terms: pseudocode, flow chart

A pseudocode is a mixture of a natural language and programming language like constructs. A
pseudocode is usually more precise than natural language. A flowchart is a

Mamatha A, Asst Prof, Dept of IS E, SVIT Page 2

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

method of expressing an algorithm by a collection of connected geometric shapes containing

descriptions of the algorithm’s steps.

10. write general plan for analyzing recursive algorithms.

i. Decide on parameter indicating an input’s size.

ii. Identify the algorithm’s basic operation
iii. Checking the no.of times basic operation executed depends on size of input.if it depends on
some additional property,then best,worst,avg.cases need to be investigated
of times the basic operation is executed
iv. Set up the recurrence relation,with an appropriate initial condition,for the number
v. Solve recurrence (establishing order of growth)

11. Define the divide an conquer method.

Given a function to compute on ‘n’ inputs the divide-and-comquer strategy suggests splitting the
inputs in to’k’ distinct susbsets, 1<k <n, yielding ‘k’ subproblems. The subproblems must be
solved recursively, and then a method must be found to combine subsolutions into a solution of
the whole.

12. What is Merge sort?

Merge sort is divide and conquer strategy that works by dividing an input array in to
two halves,sorting them recursively and then merging the two sorted halves to get the
original array sorted

13. What is general divide and conquer recurrence?

Time efficiency T(n)of many divide and conquer algorithms satisfies the equation
T(n)=a.T(n/b)+f(n).This is the general recurrence relation.

14. Describe the recurrence relation for merge sort?

If the time for the merging operation is proportional to n, then the computing time of
merge sort is described by the recurrence relation
Mamatha A, Asst Prof, Dept of IS E, SVIT Page 3
 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

T(n) = a n = 1, a a constant
2T (n/2) + n n >1, c a constant

15. The relation between order of growth of functions

O(1) < O(log n) < O(n) < O(n * log n) < O(n2 ) < O(n3 ) < O(2n )

16. Asymptotic notations

Big Oh(Worst Case), Big Theta (Average Case), Big Omega(Best Case)

GREEDY METHOD

1. Explain the greedy method.

Greedy method is the most important design technique, which makes a choice that looks best at
that moment. A given ‘n’ inputs are required us to obtain a subset that satisfies some constraints
that is the feasible solution. A greedy method suggests that one candevice an algorithm that
works in stages considering one input at a time.

2. Define feasible and optimal solution.

Given n inputs and we are required to form a subset such that it satisfies some given constraints
then such a subset is called feasible solution.
A feasible solution either maximizes or minimizes the given objective function is called as
optimal solution

3. What are the constraints of knapsack problem?

To maximize ∑pixi

The constraint is : ∑wixi ≥ m and 0 ≤ xi ≤ 1 1≤ i ≤ n

Mamatha A, Asst Prof, Dept of IS E, SVIT Page 4

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

where m is the bag capacity, n is the number of objects and for each object i wi

and pi are the weight and profit of object respectively.

4. Specify the algorithms used for constructing Minimum cost spanning tree.

a) Prim’s Algorithm

b) Kruskal’s Algorithm

5. State single source shortest path algorithm (Dijkstra’s algorithm).

For a given vertex called the source in a weigted connected graph,find shotrtest paths to all its
other vertices.Dijikstra’s algorithm applies to graph with non-negative weights only.

6. State efficiency of prim’s algorithm.

O(|v|2 ) (WEIGHT MATRIX AND PRIORITY QUEUE AS UNORDERED ARRAY)

O(|E| LOG|V|) (ADJACENCY LIST AND PRIORITY QUEUE AS MIN-HEAP)

7. State Kruskal Algorithm.

The algorithm looks at a MST for a weighted connected graph as an acyclic subgraph with |v|-1
edges for which the sum of edge weights is the smallest.

8. State efficiency of Dijkstra’s algorithm.

O(|v|2 ) (WEIGHT MATRIX AND PRIORITY QUEUE AS UNORDERED ARRAY)

Mamatha A, Asst Prof, Dept of IS E, SVIT Page 5
 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

O(|E| LOG|V|) (ADJACENCY LIST AND PRIORITY QUEUE AS MIN-HEAP)

DYNAMIC PROGRAMMING

1. Define multistage graph

A multistage graph G =(V,E) is a directed graph in which the vertices are partitioned into K>=2
disjoint sets Vi,1<=i<=k.The multi stage graph problem is to find a minimum
cost paths from s(source ) to t(sink)
Two approach(forward and backward)

2. Define All pair shortest path problem

Given a weighted connected graph, all pair shortest path problem asks to find the lengths of
shortest paths from each vertex to all other vertices.

3.Define floyd’s algorithm

To find all pair shortest path

4. State the time efficiency of floyd’s algorithm

O(n3 )

It is cubic

***************************SET II***************************
1) What is the time complexity of linear search?
Θ(n)
2) What is the time complexity of binary search?
Θ(log2 n)
3) What is the major requirement for binary search?
The given list should be sorted.
4) What is binary search?
It is an efficient method of finding out a required item from a given list, provided the list is in
order.
The process is:
1. First the middle item of the sorted list is found.
2. Compare the item with this element.

Mamatha A, Asst Prof, Dept of IS E, SVIT Page 6

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

3. If they are equal search is complete.

4. If the middle element is greater than the item being searched, this process is repeated in the
upper half of the list.
5. If the middle element is lesser than the item being searched, this process is repeated in the
lower half of the list.
5) What is parental dominance?
The key at each node is greater than or equal to the keys at its children.
6) What is heap?
A heap can be defined as a binary tree with keys assigned to its nodes ( one key per node)
provided the following two conditions are met:
1 The tree’s shape requirement – The binary tree is essentially complete ( or simply complete),
that is, all its levels are full except possibly the last level, where only some rightmost leaves may
be missing.

2. The parental dominance requirement – The key at each node is greater than or equal to the
keys at its children
7) What is height of Binary tree?
It is the longest path from the root to any leaf.
8) What is the time complexity of heap sort?
Θ( n logn)
9) What is Merge Sort?
Merge sort is an O (n log n) comparison-based sorting algorithm. Where the given array is
divided into two equal parts. The left part of the array as well as the right part of the array is
sorted recursively. Later, both the left sorted part and right sorted part are merged into a single
sorted array.
10) Who invented Merge Sort?
John Von Neumann in 1945.
11) On which paradigm is it based?
Merge-sort is based on the divide-and-conquer paradigm.
12) What is the time complexity of merge sort?
n log n.

Mamatha A, Asst Prof, Dept of IS E, SVIT Page 7

 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

13) What is the space requirement of merge sort?

Space requirement: Θ(n) (not in-place).
14) When do you say an algorithm is stable and in place?
Stable – if it retains the relative ordering. In – place if it does not use extra memory.
15) Who invented Dijkstra’s Algorithm?
Edsger Dijkstra invented this algorithm.
16) What is the other name for Dijkstra’s Algorithm?
Single Source Shortest Path Algorithm.
17) Which technique the Dijkstra’s algorithm is based on?
Greedy Technique.
18) What is the purpose of Dijkstra’s Algorithm?
To find the shortest path from source vertex to all other remaining vertices
19) Name the different algorithms based on Greedy technique.
Prim’s Algorithm, Kruskal’s algorithm
20) What is the constraint on Dijkstra’s Algorithm?
This algorithm is applicable to graphs with non-negative weights only.
21) What is a Weighted Graph?
A weighted graph is a graph with numbers assigned to its edges. These numbers are called
weights or costs.
22) What is a Connected Graph?
A graph is said to be connected if for every pair of its vertices u and v there is a path from u to v.
23) What is the time complexity of Dijkstra’s algorithm?
For adjacency matrix, It is O(IVI*IVI)
For adjacency list with edges stored as min heap, it is O(IEIlogIVI)
24) Differentiate b/w Traveling Salesman Problem(TSP) and Dijkstra’s Algorithm.
In TSP, given n cities with known distances b/w each pair , find the shortest tour that passes
through all the cities exactly once before returning to the starting city.
In Dijkstra’s Algorithm, find the shortest path from source vertex to all other remaining vertices
25) Differentiate b/w Prim’s Algorithm and Dijkstra’s Algorithm?
Prim’s algorithm is to find minimum cost spanning tree.
Dijkstra’s algorithm is to find the shortest path from source vertex to all other remaining vertices.
Mamatha A, Asst Prof, Dept of IS E, SVIT Page 8
 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

26) What are the applications of Dijkstra’s Algorithm?

It finds its application even in our day to day life while travelling.
They are helpful in routing applications.
27) Who was the inventor of the Quicksort?
C.A.R.HOARE, a British Scientist.
28) Which design strategy does Quicksort uses?
Divide and Conquer
29) What is Divide and Conquer Technique?
(I) Divide the instance of a problem into two or more smaller instances
(II) Solve the smaller instances recursively
(III) Obtain solution to original instances by combining these solutions
30) What is the another name for Quicksort?
Partition Exchange Sort
31)Is Quicksort Stable as well as In place?
Not Stable but In place.
32) When do you say that a Quick sort having best case complexity?
When the pivot exactly divides the array into equal half
33) When do you say that Quick sort having worst case complexity?
When any one of the subarray is empty
34) How many more comparisons are needed for average case compared to best case?
38% more
35) when do you say that the pivot element is in its final position?
When all the elements towards the left of pivot are <= pivot and all the elements towards the
right of pivot are >= pivot.
36) What technique does kruskal’s algorithm follow.
Greedy technique
37) What is the time complexity of kruskal algorithm.
With an efficient sorting algorithm, the time efficiency of an kruskal’s algorithm will be in
O(|E|log|E|).
38) Who is the inventor of kruskal’s algorithm.
Joseph Kruskal.
Mamatha A, Asst Prof, Dept of IS E, SVIT Page 9
 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

39) Which technique is used to solve BFS & DFS problems?

Decrease and Conquer
40) What is DFS traversal?
Consider an arbitrary vertex v and mark it as visited on each iteration, proceed to an unvisited
vertex w adjacent to v. we can explore this new vertex depending upon its adjacent information.
This process continues until dead end is encountered.(no adjacent unvisited vertex is available).
At the dead end the algorithm backs up by one edge and continues the process of visiting
unvisited vertices. This process continues until we reach the starting vertex.
41) What are the various applications of BFS & DFS tree traversal technique?
Application of BFS
Checking connectivity and checking acyclicity of a graph.
Check whether there is only one root in the BFS forest or not.
If there is only one root in the BFS forest, then it is connected graph otherwise disconnected
graph.
For checking cycle presence, we can take advantage of the graph's representation in the form of a
BFS forest, if the latter vertex does not have cross edge, then the graph is acyclic.
Application of DFS
To check whether given graph is connected or not.
To check whether the graph is cyclic or not.
To find the spanning tree.
Topological sorting.
42) Which data structures are used in BFS & DFS tree traversal technique?
We use Stack data structure to traverse the graph in DFS traversal.
We use queue data structure to traverse the graph in BFS traversal.
43) What is Dynamic Programming?
It is a technique for solving problems with overlapping sub problems.
44) What does Dynamic Programming have in common with Divideand-
Conquer?
Both solve the problems by dividing the problem into sub problems. Using the solutions of sub
problems, the solutions for larger instance of the problem can be obtained.
45) What is a principle difference between the two techniques?
Mamatha A, Asst Prof, Dept of IS E, SVIT Page 10
 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

Only one instance of the sub problem is computed & stored. If the same instance of sub problem
is encountered, the solution is retrieved from the table and never recomputed. Very precisely re -
computations are not preformed.
46) What is a spanning tree ?
A spanning tree of a weighted connected graph is a connected acyclic(no cycles) subgraph (i.e. a
tree)that contains all the vertices of a graph and number of edges is one less than number of
vertices.
47) What is a minimum spanning tree ?
Minimum spanning tree of a connected graph is its spanning tree of smallestweight.
48) Prim’s algorithm is based on which technique.
Greedy technique.
49) Name some of the application greedy technique
They are helpful in routing applications: In the case of network where large number of
computers are connected, to pass the data from one node to another node we can find the shortest
distance easily by this algorithm. Communication Networks: Suppose there are 5 different cities
and we want to establish computer connectivity among them, then we take into the account of
cost factor for communication links. Building a road network that joins n cities with minimum
cost.
50) Does Prim’s Algorithm always yield a minimum spanning tree ?
Yes
51) What is the purose of Floyd’s algoreithm?
- To find the all pair shortest path.
52) What is the time efficiency of floyd’s algorithm?
- It is same as warshall’s algorithm that is θ(n3 ).
53) What is shortest path?
- It is the path which is having shortest length among all possible paths.
54) warshall’s algorithm is optimization problem or non-optimization problem ?
Non-optimization problem
55) For what purpose we use Warshall’s algorithm?
Warshall’s algorithm for computing the transitive closure of a directed graph
56) Warshall’s algorithm depends on which property?
Mamatha A, Asst Prof, Dept of IS E, SVIT Page 11
 DESIGN AND ANALYSIS OF ALGORITHMS LABORATORY (15CSL47)

Transitive property
57) what is the time complexity of Warshall’s algorithm?
Time complexity of warshall’s algorithm is θ(n3 ).
58) what is state space tree?
Constructing a tree of choices being made and processing is known as state-spacetree.
Root represents an initial state before the search for solution begins.
60) what are promising and non-promising state-space-tree?
Node which may leads to solution is called promising.
Node which doesn’t leads to solution is called non-promising.

61) What are the requirements that are needed for performing Backtracking?
Complex set of constraints. They are:
i. Explicit constraints.
ii. Implicit constraints.

Mamatha A, Asst Prof, Dept of IS E, SVIT Page 12