2 MARKS QUESTIONS

UNIT-I
1. Define an algorithm?
The algorithm is defined as a collection of unambiguous instructions occurring in some specific
sequence and such an algorithm should produce output for given set of input in finite amount of time.
(or)
An algorithm is a step by step process of solving a particular problem.
2. List few algorithm strategies.
 Divide and Conquer
 Greedy Method
 Dynamic Programming
 Backtracking
 Branch and Bound
3. What are the measures that are used to measure the complexity of an algorithm?
The following are the two measures that are used to measure the complexity of an algorithm.
Time Complexity
Space Complexity
4. Write the concept of time and space complexity?
Time Complexity: The amount of time required by an algorithm to execute is called time complexity.
Space Complexity : The amount of space required by a program to execute is called space complexity.
5. Define Big oh notation?
Let f(n) and g(n) be two non-negative functions.
Let n0 and constant c are two integers such that n0 denotes some value of input
and n > n0. Similarly c is some constant such that c > 0 . we can write
f(n) ≤ c*g(n)
Then f(n) is big oh of g(n).
It is also denoted as f(n) Є (g(n)). In other words f(n) is than g(n) if g(n) is
multiple of some constant c.
6. Define Big Omega notation?
A function f(n) is said to be in Ω (g(n)) if f(n) is bounded below by some positive
constant multiple of g(n) such that
f(n) ≥ c*g(n) for all n ≥ n0
It is denoted as f(n) Є Ω(g(n)).

7. Define Big theta notation?

Let f(n) and g(n) be two non-negative functions. There are two positive constants namely c 1 and c2 such
that
c1 ≤ g(n) ≤ c2 g(n) , then we can say that f(n) Є θ (g(n))
8. What is a B tree?
B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential
access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree,
allowing for nodes with more than two children.
9. What is the balance factor in AVL Tree?
Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that
of the right subtree of that node.
Balance Factor = height(left-subtree) – height(right – subtree)
The balanced factor should be -1, 0 or +1. Otherwise, the tree will be considered an unbalanced tree.
10. Name the three asymptotic notations
big O, big Theta (Θ), and big Omega (Ω). big-Θ is used when the running time is the same for all cases,
big-O for the worst case running time, and big-Ω for the best case running time.
11. What are the characteristics of an algorithm?
The 5 properties of an algorithm are well-defined inputs, well-defined outputs, unambiguity, finiteness,
language independence, and feasibility.
12. Define balanced search tree.
A balanced binary tree is also known as height balanced tree. It is defined as binary tree in when the
difference between the height of the left subtree and right subtree is not more than m, where m is
usually equal to 1. The height of a tree is the number of edges on the longest path between the root
node and the leaf node.
13. Explain AVL rotation.
In AVL trees, the heights of the two child subtrees of any node differ by no more than one. This
balance is maintained through rotations during insertion and deletion operations. The balancing factor
(BF) of a node in an AVL tree is defined as the height difference between its left and right subtrees.
14. What are the different types of Rotation in AVL Tree?
To maintain balance, an AVL tree uses four types of rotations: left rotation, right rotation, left-right
rotation, and right-left rotation.
15. What does AVL stand for?
In Computer Science, AVL stands for Adelson-Velski & Landis. This is because the AVL tree was
introduced by these two inventors.

UNIT-II
1. Define quick sort.
QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a pivot and
partitions the given array around the picked pivot by placing the pivot in its correct position in the
sorted array.
2. Define merge sort.
Merge sort is a sorting algorithm that follows the divide-and-conquer approach. It works by
recursively dividing the input array into smaller subarrays and sorting those subarrays then merging
them back together to obtain the sorted array.
3. Difference between MIN heap and MAX heap.
In Min Heap, the root node has the smallest key, and in Max Heap, the root node has the largest key .
Also, the priority of elements differs while constructing these heaps.
4. Write the control abstraction for divide and conquer technique?
A control abstraction is a procedure whose flow of control is clear but whose primary operations are
specified by other procedures whose precise meanings are left undefined. The control abstraction for
divide and conquer technique is DANDC(P), where P is the problem to be solved.
5. Define graph.
A graph is a non-linear kind of data structure made up of nodes or vertices and edges. The edges
connect any two nodes in the graph, and the nodes are also known as vertices.
6. Define graph traversal in data structure.
Graph traversal is a technique used for searching a vertex in a graph. The graph traversal is also used to
decide the order of vertices is visited in the search process. A graph traversal finds the edges to be used
in the search process without creating loops. That means using graph traversal we visit all the vertices
of the graph without getting into looping path.
There are two graph traversal techniques and they are as follows...
 1. DFS (Depth First Search)
2. BFS (Breadth First Search)

7. Define heap tree.

A heap tree is typically either a min-heap tree, in which each parent node is smaller than its children; or
a max-heap tree, in which each parent node is larger than its children.
8. Define priority queue.
A priority queue is a special type of queue in data structure where each element is associated with a
priority. In this queue, elements with higher priority are dequeued before the elements with lower
priority. If two elements carry the same priority, they are served as per their ordering in the queue.
9. Define articulation point in biconnected components.
A biconnected component of a graph is a connected subgraph that cannot be broken into disconnected
pieces by deleting any single node (and its incident links). An articulation point is a node of a graph
whose removal would cause an increase in the number of connected components.
10. Define strassen's matrix multiplication.
Strassen's Matrix Multiplication is the divide and conquer approach to solve the matrix multiplication
problems. The usual matrix multiplication method multiplies each row with each column to achieve the
product matrix. The time complexity taken by this approach is O(n3), since it takes two loops to
multiply. Strassen’s method was introduced to reduce the time complexity from O(n3) to O(nlog 7) which
is approximately O(n^2.81).
11. What is meant by divide and conquer technique?
General strategy of divide and conquer method – Divide and conquer is an algorithm strategy in which
the given problem is broken into the smaller sub problems and the solutions to these sub problems is
obtained. Later on these solutions are combined together to obtain the solution for the original given
problem.
12. Write the control abstraction for divide and conquer.
Algorithm DC (P)
{
if P is too small then
return solution of P.
else
{
Divide (P) and obtain p1, p2, p3 ……, Pn
where n >= 1
Apply DC to each subproblem
return combine ( DC (p1), DC(p2),…..(DC(pn));
}
}

Unit-III
1. Define dynamic programming.
Dynamic programming is a technique for solving problems with overlapping subproblems. These sub
problems arise from a recurrence relating a solution to a given problem with solutions to its smaller sub
problems only once and recording the results in a table from which the solution to the original problem
is obtained.
2. What are the features of dynamic programming?
a. Optimal solutions to sub problems are retained so as to avoid recomputing their values.
b. Decision sequences containing subsequences that are sub optimal are not considered.
 c. It definitely gives the optimal solution always.
3. Write the general procedure of dynamic programming.
The development of dynamic programming algorithm can be broken into a sequence of 4 steps.
o Characterize the structure of an optimal solution.
o Recursively define the value of the optimal solution.
o Compute the value of an optimal solution in the bottom-up fashion.
o Construct an optimal solution from the computed information.
4. What is feasible solution ?
For solving the particular problem there exists n inputs and we need to obtain a subset that satisfies
some constraints. Then any subset that satisfies these constraints is called feasible solution.
5. What is optimal solution?
Optimal solution is the best choice selected from the set of feasible solutions. This solution can be
minimum or the maximum value of the solution.
6. What is knapsack problem?
If we are given n objects and a knapsack or a bag in which the object i that has weight wi is to be
placed. The knapsack has capacity W. Then the profit can be earned is pixi. The objective is to obtain
filling of knapsack with maximum profit earned.
7. What are the applications of greedy method?
The following are the some problems that make use of greedy method
 Single source shortest path problem
 Knapsack problem
 Job Scheduling with deadlines
 Minimum cost spanning tree
8. Write the difference between the Greedy method and Dynamic programming.
Greedy method
1. Only one sequence of decision is generated.
2. It does not guarantee to give an optimal solution always.
Dynamic programming
1. Many number of decisions are generated.
2. It definitely gives an optimal solution always.
9. What is 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 can device an algorithm that works in stages
considering one input at a time.
10. What are the labels in Prim’s algorithm used for?
Prim‘s algorithm makes it necessary to provide each vertex not in the current tree with the information
about the shortest edge connecting the vertex to a tree vertex. The information is provided by attaching
two labels to a vertex.
The name of the nearest tree vertex.
The length of the corresponding edge.
11. What is the use of Dijksra’s algorithm?
Dijkstra‘s algorithm is used to solve the single-source shortest-paths problem: for a given vertex called
the source in a weighted connected graph, find the shortest path to all its other vertices. The single-
source shortest-paths problem asks for a family of paths, each leading from the source to a different
vertex in the graph, though some paths may have edges in common.
12. Define Spanning tree.
Spanning tree of a connected graph G: a connected acyclic subgraph of G that includes all of G‘s
Vertices
13. What is minimum spanning tree.
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a
connected, edge-weighted undirected graph that connects all the vertices together, without any cycles
and with the minimum possible total edge weight.
14. What is minimum cost spanning tree.
The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many
spanning trees. Minimum spanning tree is the spanning tree where the cost is minimum among all the
spanning trees. There also can be many minimum spanning trees.
15. Give the problem formulation of Knapsack problem using greedy method.
Firstly, we have given a knapsack of the maximum capacity of m kg and n items with their weight and
profit. Fill in the knapsack with a subset of items such that the selected weight is less than or equal to
the capacity of the knapsack and the profit of items is maximum.
Assume a knapsack of capacity M and n items having profit pi and weight wi
->Sort items by profit/weight ratio: pi/wi
->Consider items in order of decreasing ratio
->Take as much of each item as possible.
16. Greedy approach for job scheduling problem.
Greedy choose the jobs with maximum profit first, by sorting the jobs in decreasing order of their
profit. This would help to maximize the total profit as choosing the job with maximum profit for every
time slot will eventually maximize the total profit.
17. Explain Knapsack problem
 The problem
• Find the most valuable subset of the given n items that fit into a knapsack of capacity W.
 Consider the following sub problem P(i, j)
• Find the most valuable subset of the first i items that fit into a knapsack of capacity j,
where 1  i  n, and 1 j  W
• Let V[i, j] be the value of an optimal solution to the above subproblem P(i, j). Goal: V[n,
W]

Unit-IV
1. What are the factors that influence the efficiency of the backtracking algorithm?
The implicit and explicit constraints need to be satisfied by the solution in backtracking.
Implicit Constraints: Implicit constraints are rules which determine the tuples.
Explicit Constraints: Explicit constraints are rules, which restrict, each vector element to be
chosen from given set.
2. What are the applications of backtracking?
Following are the applications of backtracking –
 Eight queens problem
 Sum of subset problem
 Knapsack problem
 Graph coloring
3. what is backtracking?
The backtracking algorithm explores various paths to find a sequence path that takes us to the solution.
Along these paths, it establishes some small checkpoints from where the problem can backtrack if no
feasible solution is found. This process continues until the best solution is found.
4. Define State Space tree.
A space state tree is a tree representing all the possible states (solution or nonsolution) of the
problem from the root as an initial state to the leaf as a terminal state.
5. What is subset- sum problem?
 Given a set of non-negative integers and a value sum, the task is to check if there is a subset of the
given set whose sum is equal to the given sum.
6. Define branch and bound problem
Branch and is a method for solving optimization problems by breaking them down into smaller
sub-problems and using a bounding function to eliminate sub-problems that cannot contain the
optimal solution.
7. Define N queens problem
N - Queens problem is to place n - queens in such a manner on an n x n chessboard that no queens
attack each other by being in the same row, column or diagonal.

Unit-V
1. Define P and NP problems.
P is set of problems that can be solved by a deterministic Turing machine in Polynomial time. NP is
set of problems that can be solved by a Non-deterministic Turing Machine in Polynomial time.
2. Give examples for NP Complete problems
NP-complete problem, any of a class of computational problems for which no efficient solution
algorithm has been found. Many significant computer-science problems belong to this class—e.g.,
the traveling salesman problem, satisfiability problems, and graph-covering problems.
3. Define Cook’s Theorem
Any problem in N P can be reduced in polynomial time by a deterministic Turing machine to
the problem of determining whether a formula in CN F is satisfiable (SAT )
4. Define clique decision problem
The clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent
to each other, also called complete subgraphs) in a graph.
5. Define chromatic number decision problem.
Chromatic Number is the minimum number of colors required to properly color any graph. such
that no two adjacent vertices of it are assigned the same color.
6. How NP-Hard problems are different from NP-Complete?
The NP-Hard Problem does not have to exist in the NP for anyone to solve it. For solving an NP-
Complete Problem, the given problem must exist in both NP-Hard and NP Problems. This type of
problem need not be a Decision problem. This type of problem is always a Decision problem
7. What is deterministic and non-deterministic algorithm?
Deterministic algorithms are entirely predictable and always produce the same output for the same
input.
Non-deterministic algorithms may produce different outputs for the same input due to random
events or other factors.
 10 MARKS QUESTIONS
Unit-I
1. What is asymptotic notation and what is its importance in representing time complexity?
2. What are the Asymptotic notations and its properties?
3. Write the Pseudo code conventions for representation of an algorithm? write an algorithm for
factorial of a number?
4. Construct the AVL Tree for following data: 7, 14, 2, 5, 10, 33, 56, 30, 15, 25, 66, 70, 4.
5. What do you mean by a balance factor in AVL tree and explain about LL & RR rotations with an
example?
6. Construct a B tree of order 4 with the following data:5, 3, 21, 9, 1, 13, 2, 7, 10, 12, 4, 8
7. Define B-Tree. Generate a B-Tree of order 3 (2-3 tree) for the following key values
25,10,12,15,39,64,53.
8. Explain insertion into B tree with example.
9. What is a B-Tree. Specify its properties and describe the construction of a B-Tree for the following
elements 5, 2, 13, 3, 45, 72, 4, 6, 9, 22.?
Unit-II
1. Construct max heap for the following sequence of input: 25 14 16 13 10 7 12. What is the resultant
max heap after 2nd delete.
2. Explain graph traversal techniques with example?
3. Find the Minimum cost Spanning Tree(MST) for the following graph:

4. Explain about Breadth First Search Traversal technique with an example.

5. Write Strassen’s matrix multiplication procedure with its time complexity?
6. Write the General method of Divide – And – Conquer approach.
7. Write an algorithm for Quick sort with given array of elements where a = [5, 3, 1, 9, 8, 2, 4, 7]using
divide and conquer technique
8. Explain the merge sort with example.
9. Describe Quick Sort with suitable example.
10. Explain Connected Components and Bi-connected components.
Unit-III
1. Explain the greedy technique for solving the Job Sequencing problem.
2. What is a Spanning tree? Explain Prim’s Minimum cost spanning tree algorithm with suitable
example.
3. State the Greedy Knapsack Problem. Find an optimal solution to the knapsack instance n=4 objects
and the capacity of knapsack m=15, profits (10, 5, 7, 11) and weight are (3, 4, 3, 5).
4. Give any one algorithm for finding minimum spanning tree.
5. Explain 0/1 Knapsack problem using dynamic programming with an example.
6. Explain the Single source shortest path problem with an example
7. Briefly explain the optimal binary search trees with example?
8. Describe All-pairs shortest path problem using dynamic progarmming with an example.
9. Differentiate between greedy method and dynamic programming.
10. Explain travelling sales man problem with an example by using dynamic programming?
 Unit-IV
1. Explain any one application for back tracking with example?
2. Describe in detail 8-queens problem using back tracking?
3. Explain sum of subsets problem. Illustrate its working with an example.
4. Explain 0/1 knapsack problem by using backtracking with an examples?
5. Describe in detail graph coloring using back tracking?
6. Explain the general method of branch and bound?
7. Apply branch and bound to 0/1 knapsack problem and elaborate it?
8. Explain the method of reduction to solve TSP problem using branch and bound?
9. Draw the portion of the state space tree generated by LC branch and bound for the knapsack
instances. N=5,M=15,(p1,p2,p3,p4,p5)=(10,15,6,8,4),(w1,w2,w3,w4,w5)=(4,6,3,4,2).
10. Briefly explain the Least Count branch and bound solution with example?
11. State 0/1 knapsack problem of LC Branch and Bound and find the solution for the knapsack
instance with any example?
12. Given the cities and the distance between them as follows, solve the travelling Salesman problem
using branch and bound method.

13. Draw the portion of the state space tree generated by FIFO branch and bound for the following
instances. N=4,M=15,(p1,p2,p3,p4)=(10,10,12,18),(w1,w2,w3,w4)=(12,4,6,9).
14. Solve the following instances of travelling sales person problem using LCBB

∞ 7 3 12 8
3 ∞ 6 14 9
5 8 ∞ 6 18
9 3 5 ∞ 11
18 14 9 8 ∞

15. Explain Travelling sales person person problem LCBB procedure with the following instance and
draw the portion of the state space tree and find an optimal tour.

Unit-V
1. What is NP hard problem? Give an example of NP hard problem.
2. State and explain cook’s theorem?
3. Distinguish between deterministic and non-deterministic algorithms?
4. Explain the class of P and NP with example?
5. Differentiate between NP- complete and NP-hard problems?
6. Explain clique decision problem.