UNIT I

PART-A

Q. No. Questions CO Bloo

m’s
Level
Define Algorithm. [AU-A/M2023] C213.1 BTL1

1. An algorithm is a sequence of unambiguous instructions for solving a

problem in a finite amount of time

Compare Time Efficiency and Space Efficiency C213.1 BTL 2

 Time Efficiency measured by counting the number of times the

2. algorithms basic operation is executed.
 Space Efficiency is measured by counting the number of extra
memory units consumed by the algorithm
What is Big ‘Oh’ Notation? C213.1 BTL 1
The Big ‘Oh’ notation provides an upper bound for the function. A function
3.
f(n) is said to be in O(g(n)), if there exist some positive constant C and some
non negative number no, such that , f(n)<=Cg(n), for all n>=no
What is a Recurrence Equation? C213.1 BTL 1
The recurrence equation is an equation that defines a sequence recursively.
It is normally in the following form.
T(n) = T(n –1) + n , n>0 -----------(1)
4. T(0) = 0. --------------(2)
Here the equation (1) is called recurrence relation. Equation (2) is called
initial condition.
The recurrence Equation have infinite number of sequences.
The general solution to the recursive function specifies some formula.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 5. What is meant by linear search? C213.1 BTL 1

Linear search or sequential search is a method for finding a particular value

in a list that consists of checking every one of its elements, one at a time
and in sequence, until the desired one is found.

Best case – O(1)

Worst case –O(n)

Average case – O(n)

6. What is Pseudo Code? C213.1 BTL 1

Pseudo Code is a mixture of Natural Language and Programming Language

Constructs such as functions, loops, decision making statements..etc

7. Classify Algorithm Design and Analysis of Process. C213.1 BTL 4

 Understanding the problem

 Decision making
-Capabilities of computational devices
-Choice for either exact or approximate problem solving
method.
-Data Structures
-Algorithm Design Techniques.
 Design an algorithm.
-Natural Language.
-Pseudocode
-Flowchart
 Prove correctness
 Analysis of Algorithm.
 Code the Algorithm.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 List the important Problem Types C213.1 BTL4
 Sorting
 Searching

 String Processing
8.
 Graph Problem

 Combinatorial Problem
 Geometric Problem
 Numerical Problem
What is Sorting Problem? C213.1 BTL1

Sorting algorithm is rearranging the items of a given list in

descending/ascending order.
9.
Sorting algorithms classified into
 Stable Sorting Algorithm
 Non-Stable Algorithm
What is Searching Problem? C213.1 BTL1

10. Finding a given value, called search key in a given set. Searching
Algorithms needs more memory space and sorted array.
What is Graph Problem? C213.1 BTL1

11. Graph is a collection of edges and vertices. G=(V,E). For eg. Traversal
Algorithms, Shortest Path Algorithm, Graph Coloring Problem .
What is Combinatorial Problem? C213.1 BTL1

This problem that ask to find a combinatorial object such as

12.
permutations, combinations or a subset. Combinatorial problems are
most difficult to solve. For eg Traveling sales man problem .
List the features of efficient algorithm. C213.1 BTL4
 Free of ambiguity
13.  Efficient in execution time
 Concise and compact Completeness
 Definiteness Finiteness

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 Illustrate the different criteria used to improve the effectiveness of C213.1 BTL2
algorithm?
 Input- Zero or more quantities are externally supplied
 Output-At least one quantity is produced
14.  Definiteness-Each instruction is clear and unambiguous
 Finiteness-If we trace out the instructions of an algorithm, then
for all case the algorithm terminates after a finite number of
steps.
 Effectiveness-Every instruction must be very clear
What is the substitution method? C213.1 BTL1

One of the methods for solving any such recurrence relation is called
15. the substitution method. Types of Substitution :
1. Forward Substitution
2. Backward Substitution
Define the asymptotic notation “theta” (θ ) C213.1 BTL1
16. The function f(n) =θ (g(n)) if there exist positive constant C1, C2, and no
such that C1 g(n)≤ f(n) ≤ C2 g(n) for all n, n ≥ n0.
List the desirable properties of algorithm. C213. BTL
1 1
The characteristics of a good algorithm are:
Precision – the steps are precisely stated(defined).
Uniqueness – results of each step are uniquely defined and only depend on the
input and the result of the preceding steps.

17. Finiteness – the algorithm stops after a finite number of instructions are
executed.
Input – the algorithm receives input.
Output – the algorithm produces output.
Generality – the algorithm applies to a set of inputs.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 Define best ,worst, average case time complexity. [AU-A/M2023] C213. BTL
1 1
Best, worst, and average cases of a given algorithm express what the resource
usage is at least, at most and on average, respectively. Usually the resource being
considered is running time, i.e. time complexity, but it could also be memory or
other resource.
18.  Best case is the function which performs the minimum number of steps
on input data of n elements.
 Worst case is the function which performs the maximum number of steps
on input data of n elements.
 Average case is the function which performs an average number of steps
on input data of n elements.
What is Algorithm visualization? C213.1 BTL1
Algorithm visualization is a technique in which images are used to convey the
information about the algorithms
19.
There are two approaches of algorithm visualization
 Static algorithm visualization (includes still images)
 Dynamic Algorithm visualization(continuous movie like presentation)
What is the order of growth? C213.1 BTL1
Measuring the performance of an algorithm in relation with the input size n is
20.
called the order of growth.

Write general plan for analysis of non-recursive algorithms. C213.1 BTL1

 Decide the input size based on parameter n.

 Identify algorithm’s basic operatio(s)
 Check how many times the basic operation is executed. Then find
whether the execution of basic operation depend upon the input
21. size ‘n’. Determine worst, average, best cases for input size n. If
the basic operation depends upon worst, average, best case then
that has to be analysed separately.
 Set up a sum for the number of times the basic operation is
executed.
 Simplify the step using standard formula and rules.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 Write general plan for analysis of recursive algorithms. C213.1 BTL1

 Decide the input size based on parameter n.

 Identify algorithm’s basic operatio(s)
 Check how many times the basic operation is executed. Then find
whether the execution of basic operation depend upon the input
size ‘n’. Determine worst, average, best cases for input size n. If
the basic operation depends upon worst, average, best case then
22.
that has to be analysed separately.
 Set up the recurrence relation with some initial condition and
expressing the basic operation.
 Solve the recurrence or atleast determine the order of growth.
While solving the recurrence we will use the forward and
backward substituition method. And then correctness of formula
can be provided with the help of mathematical induction method.
Distinguish sequential and parallel algorithm. [AU-N/D 2023] C213.1 BTL1

Sequential algorithms follow a step-by-step approach, executing one operation at

a time, while parallel algorithms divide the problem into smaller parts and solve
23. them concurrently. The choice between using a sequential or parallel algorithm
depends on the nature of the problem, the resources available, and the performance
requirements.

What is abstraction? Why do we need abstract data type?[AU-A/M 2024] C213.1 BTL1
Abstraction is the process of hiding complex implementation details and
showing only the essential features of an object or concept.
Need of ADT:

24.  Encapsulation: They bundle data and operations together.

 Modularity: You can update the implementation without changing how
the rest of your code interacts with it.
 Flexibility: Different implementations (e.g., array vs linked list) can serve
different needs—all hidden behind a common interface.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 Reliability: ADTs help ensure that code behaves predictably by strictly defining
operations.

What is Empirical Analysis? How it is Done?[AU-A/M2024] C213.1 BTL1

Empirical analysis is a research method that uses observable and measurable
25. data to draw conclusions. It’s guided by the scientific method and aims to
eliminate personal bias by focusing on facts that can be verified through
experience, observation, or experimentation.

PART-B

Q. No. Questions CO Bloom’

s Level
1. Explain fundamentals of Algorithmic problem solving. C213.1 BTL5
2. Explain important problem types. [AU-N/D2024] C213.1 BTL5

3. Elaborate on Asymptotic Notations [AU-A/M2023] C213.1 BTL6

Explain mathematical Analysis of Non recursive Algorithm with examples C213.1 BTL5
4.
[AU-A/M2023]

5. Explain mathematical Analysis of Recursive Algorithm with examples. C213.1 BTL5

Write the Asymptotic notations used for worst-case,best-case and the C213.1 BTL1
average case analysis of algorithms.Write an algorithm for finding
6.
maximum element in an array.Give worst-case,best-case and the average
case complexities.
7. What is empirical analysis of an algorithm? Discuss its strength &weakness? C213.1 BTL1
8. Write short notes on algorithm visualization. C213.1 BTL1
If you have to solve the searching problem for a list of n numbers, how can C213.1 BTL6
you take advantage of the fact that the list is known to be sorted?
9.
Give separate answers for
(i) lists represented as arrays

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 (ii) lists represented as linked lists. Compare the time complexities
involved in the analysis of both the algorithms.
10. Write Euclid's algorithm and explain the steps. C213.1 BTL1
11 Explain the general plan for analyzing efficiency of recursive algorithms. C213.1 BTL1
Explain in detail the general framework for analyzing an algorithm's C213.1 BTL1
12.
efficiency. [AU-N/D2024]
13. Write the general plan for analyzing efficiency of non recursive algorithms. C213.1 BTL1
Write sieve of Eratosthenes algorithm which generates consecutive primes and C213.1 BTL1
14.
explain

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 UNIT II
PART-A

Bloo
m’s
Q. No. Questions CO Leve
l
Write an algorithmic steps for string matching problem using brute- C213.1 BTL1
force technique. [AU-A/M2023]

 Start at the beginning of the text string T.

 Repeat for each possible starting position i in T from 0 to n - m:
 Compare the substring T[i...i+m-1] with pattern P character by
character.
 If all m characters match:
1.
Report i as a match position.

 Else:

Move to the next position i+1.

 End of Algorithm.

How different is the travelling salesman problem from the problems of C213.1 BTL1
finding a Hamiltonian circuit? [AU-A/M2023]

Hamiltonian Circuit and Travelling Salesman Problem are both combinatorial

optimization problems that involve finding the most efficient path through a
set of vertices.
2.
However, the main difference between the two is that a Hamiltonian Cycle
seeks to find a closed loop that visits each vertex exactly once, while the
Travelling Salesman Problem aims to find the shortest possible route that
visits each vertex exactly once before returning to the starting point. Both
problems are NP-hard and require exponential time to solve, making them
challenging for large datasets.

Define Convex -Hull Problem. [AU-N/D 2022] C213.2 BTL1

3.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 The convex hull H(S) the smallest convex set S. The convex set is a set of
points (finite or infinite) in the plane that denotes the smallest convex
polygon in the plane that contains all of the points S. The polygon is convex
ii any two points from the set forming a line segment with end points entirely
within the polygon.
What is Divide and Conquer Algorithm? C213.2 BTL1

It is a general algorithm design techniques that solved a problem’s instance

4. by dividing it into several smaller instance, solving each of them recursively,
and then combining their solutions to the original instance of the problem.

What is Brute Force method? [AU-N/D 2023] C213.2 BTL1

Brute Force is a straightforward approach of solving the problem. It is

5.
directly based on the problem’s statement and definitions of the concepts
that are directly involved in the problem.
List out the Advantages in Quick Sort C213.2 BTL4
It is in-place since it uses only a small auxiliary stack
It requires only n log(n) time to sort n items
6. It has an extremely short inner loop
This algorithm has been subjected to a thorough mathematical analysis, a very
precise statement can be made about performance issues
Show the recurrence relation of divide-and-conquer? C213.2 BTL2
The recurrence relation is
7.
T(n) = { g(n) if n is small
T(n1)+t(n2)+……..+T(nr)+F(n) when n is sufficiently large.
What is Exhaustive search? C213.2 BTL2
 The exhaustive search is a method in which solution is obtained by
8. searching each element of given problem.
 Exhaustive search makes use of straight forward brute force’s
approach.
What is Knapsack problem? C213.2 BTL1
Suppose that there are n objects i=1, 2…n. each object i has some weight Wi
9.
and values Vi associated with each object and capacity of knapsack is W. for

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 example athief has to pick up the most valuable objects to fill the knapsack
to the capacity.

What is the use of TSP? C213.2 BTL1

The traveling salesman problem (TSP) is a popular mathematics problem that

10. asks for the most efficient trajectory possible given a set of points and
distances that must all be visited. In computer science, the problem can be
applied to the most efficient route for data to travel between various nodes.
List the strength and weakness of brute force algorithm. C213.2 BTL1
Strengths
a. wide applicability,
b. simplicity
c. yields reasonable algorithms for some important problems (e.g., matrix
11.
multiplication, sorting, searching, string matching)
Weaknesses
a. rarely yields efficient algorithms
b. some brute-force algorithms are unacceptably slow not as constructive
as some other design techniques
What is closest pair problem? C213.2 BTL1
The closest pair problem is to find the two closest points in a set of n points.
12.
The distance between two Cartesian coordinates is calculated by Euclidean
distance formula. d(pi,pj)=(xi-xj)2+(yi-yj)2
Illustrate the Assignment problem? MAY/JUNE 2016 C213.2 BTL2

Consider there are n people who need to be assigned to execute n jobs, i.e
13. only one person is assigned to execute one job at a time. Then people is to
find such assignment that gives smallest total cost. The cost can be
computed as cost C[i,j] i.e. ith person is assigned to jth job.
State extreme point theorem. C213.2 BTL1

14. An extreme point of a convex set S in real vector space is point in S which
does not lie in any open line segment joining two points of S.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 What is Topological Sorting? C213.2 BTL1

It is a sorting for directed acyclic graph(DAG)_ is linear ordering of vertices

15. that for every directed edge u v, vertex u comes before v in the ordering.
Topological sorting for a graph is not possible if the graph is not a DAG.

What is heap and heap sort? C213.2 BTL1

Heap is a complete binary tree or almost complete binary tree in which every
parent node be greater than or lesser than its child nodes.
There are two types of heaps
16.
1. Max heap: It is a heap structure in which each node is greater than or equal
to its child nodes.
2. Min heap: It is a heap structure in which value of each node is lesser than
or equal to its child node.
Give some examples of Brute force approach? C213.2 BTL1
17.
a) Selection sort b) bubble sort c) string matching
What is decrease-and-conquer technique? C213.2 BTL1
The decrease-and-conquer is an approach for solving a problem by:
18. i) Change an instance into smaller instance of the problem.
ii) Solve the smaller instance.

What are the three major variations of the decrease-and-conquer C213.2 BTL1
technique? [AU-N/D 2023]
The three major variations of the decrease-and-conquer technique are
19.
 Decrease by a constant
 decrease by a constant factor
 variable size decrease
What is transform and conquer? C213.2 BTL1
Transform and conquer is an algorithmic strategy in which the problem is
20.
solved by applying transformation.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 Write the selection sort algorithm C213.2 BTL1
The selection sort algorithm sorts an array by repeatedly finding the minimum
element (considering ascending order) from unsorted part and putting it at the
beginning. The algorithm maintains two sub arrays in a given array.

21. 1) The subarray which is already sorted.

2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering
ascending order) from the unsorted subarray is picked and moved to the sorted
subarray.
What is the Asymptotic Best Case and Worst Case running time of Selection C213.2 BTL1
Sort? [AU-N/D2022]
 Best-case: O(n2), best case occurs when the array is
already sorted. (where n is the number of integers in an
array)
 Average-case: O(n2), the average case arises when the
22. elements of the array are in a disordered or random order,
without a clear ascending or descending pattern.
 Worst-case: O(n2), The worst-case scenario arises when
we need to sort an array in ascending order, but the array
is initially in descending order.

PART-B

Bloo m’s
Q. No. Questions CO Leve l

1. Explain Knapsack problem with suitable example.[AU-A/M2023] C213.2 BTL5

Explain Travelling sales man problem with suitable example.[AU- C213.2 BTL5
2.
N/D 2023]

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 2. Explain Assignment problem with suitable example. [AU-A/M 2023]

Explain Multiplication of Large integers And Strassen’s Matrix C213.2 BTL5

3.
multiplication. [AU-A/M 2023]
Explain Closest pair and Convex-Hull Problems by divide and C213.2 BTL1
4.
Conquer method.
Consider the problem of finding the smallest and largest elements in an array C213.2 BTL6
of N numbers. [AU-A/M 2023]
i)Design a presorting based algorithm for solving this problem and
determine its efficiency class.
5.
ii)Compare the efficiency of the three algorithms:
(A)the brute – force algorithm.
(B)this presorting based algorithm
(C)the Divide and conquer algorithm.
Explain heap sort and arrange the following numbers in increasing order using C213.2 BTL5
6.
heap sort. (18, 29, 68, 32, 43,37, 87, 24, 47, 50)
Draw step by step successive key insertion for the list 2,9, 7, 6, 5,8 by bottom C213.2 BTL5
7. up heap. Construct an algorithm for the same and specify its complexity. [AU-
N/D2023]

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 UNIT III

PART-A
Bloom’
Q. No. Questions CO
s Level
State the principles of Optimality in dynamic programming. C213.3 BTL2

[AU-A/M 2023]
1.
The principle of optimality states that “in an optimal sequence of choices or
decisions, each subsequence must also be optimal”.
What is Dynamic programming? C213.3 BTL1
Dynamic programming is an algorithm design technique for solving problem
2. with overlapping subprograms. The smaller subprograms are solved only once
and recording the results in a table from which the solution to the original
problem is obtained
What is greedy method? C213.3 BTL1
In the greedy technique, the solution is constructed through a sequence of
steps, each expanding partially constructed solution obtained so far, until a
3.
complete solution to a problem is reached. At each step the choice of feasible
solution is made. From the set of feasible solutions the optimal solution is
selected as the solution to the problem.
What is meant by feasible solution? C213.3 BTL1

For solving the particular problem there exists ‘n’ inputs and we need to obtain
4.
a subset that satisfies some constraints. Then any subset that satisfies these
constraints is called feasible solution.
Define optimal solution C213.3 BTL1

5. A feasible solution either maximizes or minimizes the given objective function

is called as optimal solution.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 What are the differences between dynamic programming and divide C213.3 BTL1

and conquer approaches?

Divide and Conquer
Divide and Conquer works by dividing the problem into sub-problems,
conquer each sub-problem recursively and combine these solutions.
Dynamic Programming
6.
Dynamic Programming is a technique for solving problems with
overlapping sub problems. Each sub-problem is solved only once and the
result of each sub-problem is stored in a table (generally implemented as
an array or a hash table) for future references. These sub-solutions may
be used to obtain the original solution and the technique of storing the
sub-problem solutions is known as memorization.
Compare Greedy method and Dynamic programming. C213.3 BTL5

Greedy method Dynamic programming C213.3 BTL5

1. Dynamic Programming is 1. Greedy Method is also used to get

used to obtain the optimal the optimal solution.
7. solution.

2.In Dynamic Programming, 2. In a greedy Algorithm, we make

we choose at each step, but whatever choice seems best at the
the choice may depend on moment and then solve the sub-
the solution to sub- problems arising after the choice is
problems. made.
What does Floyd’s algorithm do? Write the pseudocode of Floyd’s C213.3 BTL1
algorithm.(refer notes) [AU-N/D 2023]

Floyd’s algorithm is an application, which is used to find the entire pairs

8.
shortest paths problem. Floyd’s algorithm is applicable to both directed
and undirected weighted graph, but they do not contain a cycle of a
negative length.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 Define Prim’s algorithm. C213.3 BTL1

9. Prim’s algorithm is a greedy and efficient algorithm, which is used to find the
minimum spanning tree of a weighted connected graph.
Can we use prim’s algorithm to find a spanning tree of a connected graph C213.3 BTL1
with no weights on its edges? [AU-N/D2022]

10. yes, we can use Prim’s algorithm, but it’s not the most efficient or meaningful
choice for unweighted graphs. Algorithms like BFS or DFS are simpler and
more natural for this purpose.

Define kruskal’s algorithm C213.3 BTL1

 kruskal’s algorithm is another greedy algorithm for the minimum

spanning tree problem.
11.  kruskal’s algorithm constructs a minimum spanning tree by
selecting edges in increasing order of their weights provided that the
inclusion does not create a cycle. Kruskal’s algorithm provides a
optimal solution.
Define Dijikstra’s Algorithm[AU-A/M2023] C213.3 BTL1

Dijkstra’s algorithm solves the single source shortest path problem of finding
12. shortest paths from a given vertex( the source), to all the other vertices of a
weighted graph or digraph. Dijkstra’s algorithm provides a correct solution
for a graph with non negative weights.
What is Huffman trees? C213.3 BTL1

A Huffman tree is binary tree that minimizes the weighted path length from
13.
the root to the leaves containing a set of predefined weights. The most
important application of Huffman trees are Huffman code.
What do you mean by Huffman code? C213.3 BTL1
A Huffman code is a optimal prefix tree variable length encoding scheme
14.
that assigns bit strings to characters based on their frequencies in a given
text.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 List the advantage of Huffman’s encoding. C213.3 BTL4

a. Huffman’s encoding is one of the most important file

compression methods.
15.
b. It is simple
c. It is versatility
d. It provides optimal and minimum length encoding
Define the single source shortest path problem. C213.3 BTL1
Single source shortest path problem can be used to find the shortest path from
16.
single source to all other vertices.
Example:Dijikstra’s algorithm
List out the memory functions used under dynamic programming. C213.3 BTL4

 Memoization (Top-Down Approach)

 Stores results of expensive function calls and returns the cached

result when the same inputs occur again.
 Typically implemented using recursion with a cache (e.g., dictionary
or array).
 Avoids recomputation by checking if the result is already stored.
17.
 Tabulation (Bottom-Up Approach)

 Builds a table (usually an array or matrix) from the base cases up to

the desired result.
 Iterative and often more space-efficient than memoization.
 Avoids recursion and stack overflow issues.

Define Memory Function. C213.3 BTL1

Dynamic Programming (DP) relies heavily on memory functions to store and
18.
reuse previously computed results, which helps avoid redundant calculations
and improves efficiency.
Define optimal binary search tree. C213.3 BTL1

19.  The optimal binary search tree (Optimal BST) is also known
as a weight-balanced search tree.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

  It is a binary search tree that provides the shortest possible
search time or expected search time. An optimal binary search
tree is helpful in dictionary search.

What is meant by coin changing problem ? C213.3 BTL1

20. Given a set of coins and amount, Write an algorithm to find out how many
ways we can make the change of the amount using the coins given.
Define 0/1 Knapsack problem. C213.3 BTL1
The solution to the Knapsack problem can be viewed as a result of sequence
of decisions. We have to decide the value of xi. xi is restricted to have the
21.
value 0 or 1 and by using the function knap(l, j, y) we can represent the
problem as maximum Σpi xi subject to Σwi xi < y where l - iteration, j -
number of objects, y – capacity.
Define Multi Stage Graph. C213.3 BTL1
A Multistage graph is a directed, weighted graph in which the nodes can
22. be divided into a set of stages such that all edges are from a stage to next
stage only (In other words there is no edge between vertices of same stage
and from a vertex of current stage to previous stage).

PART-B

Q.NO. QUESTIONS CO BLOOM’S

LEVEL
Explain the algorithm to solve all pairs shortest paths problem . [AU- C213.3 BTL5
1.
N/D2022]
2. Discuss Dijkstra’s Algorithm with example. [AU-N/D2024] C213.3 BTL6
Discuss about the algorithm and pseudo code to find the minimum spanning C213.3 BTL6
3.
tree using prim’s algorithm.
Explain how Huffman trees are constructed for assigning shorter bit C213.3 BTL6
4. strings to high frequency symbols and larger ones to low frequency
symbols. [AU-N/D2023]

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 5. Explain Multi stage graph in detail. C213.3 BTL1
Indicate the algorithm to find the optimal feasible subset of first I entries C213.3 BTL6
6.
by memory function for the knapsack problem.[AU-N/D2023]
Explain how coin change problem can be solved by dynamic C213.3 BTL6
7.
programming approach. [AU-N/D2024]
8. Explain warshall’s algorithm with suitable example. . [AU-A/M2023] C213.3 BTL6
Write pseudocode of the bottom up dynamic programming algorithm for the C213.3 BTL6
9.
knapsack problem. [AU-A/M2023]
10. Explain floyd’s algorithm with suitable example. C213.3 BTL6

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 UNIT IV

PART – A

Q. No. Questions CO Bloom’s

Level
What is iterative improvement method? C213.4 BTL1
This is a computational technique in which with the help of initial feasible
1.
solution the optimal solution is obtained iteratively until no improvement is
found.
List various applications of iterative improvement method. C213.4 BTL4
1.Simplex method
2. 2.Matching graph vertices
3.Stable marriage problem
4.Finding maximum network flow.
What is Simplex Method? C213.4 BTL1
The Simplex Method is a powerful and widely used algorithm in linear
programming for solving optimization problems, particularly those
3.
involving maximizing or minimizing a linear objective function subject to
linear equality and inequality constraints.

What are the requirements to represent the simplex method to a C213.4 BTL1
linear programming problem in the standard form?
Standard form is the baseline format for all linear programs before solving for
the optimal solution and has three requirements:
(1) must be a maximization problem,
4. (2) all linear constraints must be in a less-than-or-equal-to inequality,
(3) all variables are non-negative.
Example:
Z = 7x1 + 5x2
subject to
x1 + 2x2 ≤ 6

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 4x1 + 3x2 ≤ 12
x1, x2 ≥ 0

Why do we need slack and surplus variables in the LPP for solving C213.4 BTL1
using simplex method?
 Slack variables are added to ≤ constraints to convert them to
5. equations.
 Surplus variables are subtracted from ≥ constraints.
 Artificial variables are added to = and ≥ constraints to satisfy
non-negativity conditions.
How Iterative improvement solves problems? C213.4 BTL1
Iterative improvement solves problems where:
 The problem is an optimization problem, to find the solution that
6. minimizes or maximizes some value (cost/profit).
 An initial solution can be easily found.
 It can be improved by a sequence of small changes.
 It is returned when no more improvements can be made.
What is linear programming problem? C213.4 BTL1
The standard form of linear programming is
7. P=ax+by+cz
LP problem is a problem in which we have to find the maximum or minimum
value of a linear objective function.
What is meant by Bipartite Graph? C213.4 BTL1
A Bipartite Graph G = (V;E) is a graph in which the vertex set V can be
8.
divided into two disjoint subsets X and Y such that every edge e € E has one
end point in X and the other end point in Y .
What is two colorable graph? C213.4 BTL1
 It is a graph that can be colored with only two colors in such a way
9.
that no edge connects the same color.
 The bipartite graph is two colorable graph.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 What is maximum cardinality matching? C213.4 BTL1
A maximum matching (also known as maximum-cardinality matching) is
10. a matching that contains the largest possible number of edges. There may be
many maximum matchings. The matching number of a graph is the size of
a maximum matching.
What is meant by Maximum Matching problem? C213.4 BTL1
11. A maximum matching problem is a problem of finding maximum matching
in a graph.
What is network? C213.4 BTL1
12. A flow network G=(V,E) is a directed graph in which each edge (u,v) € E
has a nonnegative capacity c(u,v) ≥ 0.
Define Maximum Flow Theorem. C213.4 BTL1
13.
A flow has maximum value if and only if it has no augmenting path.
What is Augmenting path in bipartite graph.? C213.4 BTL1
14. The Augmenting path P is a path in Graph G,such that it is an alternating path
with special property that-Its start and end vertices are free or unmatched.
What is entering variable? C213.4 BTL1
15. The entering variable is the smallest negative entry in the bottommost row of
simplex table.
What is pivot element in simplex method? C213.4 BTL1
16. The intersection of entering variable’s column and departing variable’s row
is called pivot.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 Explain Stable marriage problem algorithm. C213.4 BTL2
Input: A set of n men and a set of n women along with rankings of the women
by each man and rankings of the men by each woman with no ties allowed in
the rankings
Output: A stable marriage matching.
Step 0 :Start with all the men and women being free.
Step 1 :While there are free men, arbitrarily select one of them and do the
following:
17.
Proposal: The selected free man m proposes to w, the next woman
on his preference list (who is the highest-ranked woman who has not rejected
him before).
Response: If w is free, she accepts the proposal to be matched with m. If she
is not free, she compares m with her current mate. If she prefers m to him, she
accepts m’s proposal, making her former mate free; otherwise, she simply
rejects m’s proposal, leaving m free.
Step 2 Return the set of n matched pairs
Define network flow and cut. C213.4 BTL1
 Networkflow: Given a directed graph G with non negative integer
weight and two distinguished vertices s and t called source and the
sink, such that the source only has out edges and sink only has in-
18.
edges, the maximum amount of commodity that can flow through
network from source to sink, is called network flow.
 Cut : cut is a collection of arcs such that if they are removed there is
no path from source to sink
Define Max-Flow Min-Cut Theorem. C213.4 BTL1
19. The value of a maximum flow in a network is equal to the capacity of its
minimum cut.
Define slack variable. C213.4 BTL1
20. Variables transforming inequality constraints into equality constraints are
called slack variables.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 What is an articulation point in a graph? C213.4 BTL1
A vertex in an undirected connected graph is an articulation point(or cut
21.
vertex) iff removing it (and edges through it) disconnects the graph. It can
be thought of as a single point of failure.
Write the requirements of linear programming problem standard form C213.4 BTL1
1.It must be a maximization problem.
22. 2.All the constraints (except the nonnegative constraints ) must be in the form
of linear equations with nonnegative right hand sides.
3.All the variables must be required to be nonnegative.
What is meant by feasible flow in maximum flow problem. C213.4 BTL1
23. It is an assignment of real numbers Xij to edges i.j of a network that satisfy
flow conservation constraints and the capacity constraints.
Write the three important things in Ford-Fulkereson method. C213.4 BTL1
1.Residual network
24.
2.Augmenting path
3.Cuts
What is Augmenting path in maximum flow problem.? C213.4 BTL1
25. The path which never violates the capacity constraints is called Augmenting
path in maximum flow problem .
What is Residual network? C213.4 BTL1
A representation of a network with flow and capacity value for every node is
26.
called residual network.
Write Ford-Fulkerson algorithm C213.4 BTL1
Generic method for solving maxflow problem.
• Start with 0 flow everywhere.
27
• Find an augmenting path.
• Increase the flow on that path, by as much as possible.
• Repeat until no augmenting paths are left.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 PART – B

Q.No. Questions CO BLOOM’S

LEVEL
1. Explain the maximum flow problem in detail.[AU-A/M2023] C213.4 BTL5

2. Explain Maximum Matching in Bipartite Graphs With Suitable Example. C213.4 BTL5
[AU-N/D2024]
3. Find the Stable marriage Matching for the instance defined by the following C213.4 BTL5
ranking matrix. [AU-A/M 2023]
A B C D
P 1,3 2,3 3,2 4,3
Q 1,4 4,1 3,4 2,2
R 2,2 1,4 3,3 4,1
S 4,1 2,2 3,1 1,4
Explain briefly on bipartite perfect matching prototype C213.4 BTL5
4.
[AU-N/D2024]
Solve the following lpp geometrically(graphically[AU-N/D2024] C213.4 BTL5
Maximize x+2y
Subject to
5. 4x>=y
Y<=3+x
X>=0, y>=0

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 UNIT V
PART-A

Bloo
m’s
Q. No. Questions CO Leve
l
What is Tractable and Intractable problem?[AU-N/D2022] C213.5 BTL2

 Tractable Problem: a problem that is solvable by a polynomial-time

1. algorithm. The upper bound is polynomial.
 Intractable Problem: a problem that cannot be solved by a polynomial-
time al gorithm. The lower bound is exponential

What is P and NP Problem? [AU-A/M2024] C213.5 BTL2

 The P in the P class stands for Polynomial Time. It is the collection
of decision problems(problems with a "yes" or "no" answer) that can
be solved by a deterministic machine (our computers) in polynomial
2. time.
 The NP in NP class stands for Non-deterministic Polynomial
Time. It is the collection of decision problems that can be solved by
a non-deterministic machine (note that our computers are
deterministic) in polynomial time.
What is NP hard and NP Complete?[AU-A/M2024] C213.5 BTL2
 An NP-hard problem is at least as hard as the hardest problem in NP
and it is a class of problems such that every problem in NP reduces
3.
to NP-hard.
 A problem is NP-complete if it is both NP and NP-hard. NP-
complete problems are the hard problems in NP.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 What do you mean by polynomial time approximation algorithm? [AU- C213.5 BTL2
A/2024]

Polynomial Time Approximation Scheme (PTAS) is a type of approximate

algorithms that provide user to control over accuracy which is a desirable
feature. These algorithms take an additional parameter ε > 0 and provide a
4.
solution that is (1 + ε) approximate for minimization and (1 - ε) for
maximization.

For example consider a minimization problem, if ε is 0.5, then the solution

provided by the PTAS algorithm is 1.5 approximate.

Write about information-theoritic lower bound. [AU-N/D 2023] C213.5 BTL2

Information-theoretic lower bound is the minimum amount of information or

5. resources (like time, space, or queries) required to solve a problem, regardless
of the algorithm used. It’s derived from the inherent complexity of the
problem itself, not from limitations of specific computational models.

How does the branch and bound algorithm works? [AU-A/M2023] C213.5 BTL2

The Branch and Bound Algorithm is a method used

in combinatorial optimization problems to systematically search for the
best solution.

6. It works by dividing the problem into smaller subproblems, or branches, and

then eliminating certain branches based on bounds on the optimal solution.

This process continues until the best solution is found or all branches have
been explored. Branch and Bound is commonly used in problems like
the traveling salesman and job scheduling.

What is state space tree? C213.5 BTL2

A space state tree is a tree representing all the possible states (solution or
7.
nonsolution) of the problem from the root as an initial state to the leaf as a
terminal state.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 What is meant by ‘n’ queens problem? [AU-A/M2023] C213.5 BTL2

In n- queen problem, we are given an nxn chessboard and we have to place

‘n’ number of queens on the board in such a way that no two queens attack each
8.
other. A queen will attack another queen if it is placed in horizontal, vertical or
.diagonal points in its way. The most popular approach for solving the N Queen
.puzzle is Backtracking.
What is LIFO and FIFO search? C213.5 BTL2
FIFO (first in, first out): always the oldest node in the queue is used to extend
the branch. This leads to a breadth-first search, where all nodes at depth d are
visted first, before any nodes at depth d+1 are visited.
9.
LIFO (last in, first out): always the youngest node in the queue is used to
extend the branch. This leads to a depth-first search, where the branch is
extended through every 1st child discovered at a certain depth, until a leaf node
is reached.
What is Backtracking? C213.5 BTL2
Backtracking algorithms are like problem-solving strategies that help
10. explore different options to find the best solution. They work by trying out
different paths and if one doesn't work, they backtrack and try another until
they find the right one.
Define a live node. C213.5 BTL1
11. A node which has been generated and all of whose children have not yet been
generated is called as a live node
Define a E – node. C213.5 BTL1
12. E – node (or) node being expanded. Any live node whose children are
currently being generated is called as a E – node.
Define a dead node. C213.5 BTL1
13. Dead node is defined as a generated node, which is to be expanded further all
of whose children have been generated
Define Hamiltonian circuit problem. C213.5 BTL1
14. It is a problem of finding a Hamiltonian circuit.hamiltonian circuit is a circuit
that visits every vertex exactly once and return to the starting vertex.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 List the application of backtracking technique? C213.5 BTL4
The application of backtracking technique is
 8-Queens problem
15.
 Sum of subset problem
 Finding Hamiltonian path
 Knapsack problem
Define subset sum problem. C213.5 BTL1
Subset sum problem is a problem, which is used to find a subset of a given
16.
set S={S1,S2,S3,…….Sn} of n positive integers whose sum is equal to given
positive integer d.
What is heuristic? [AU-N/D2023] C213.5 BTL1
A heuristic is a common sense rule drawn from experience rather than from a
17. mathematically proved assertion.
For example, going to the nearest un visited city in the travelling salesman
problem is good example for heuristic
What is promising and non promising node? NOV/DEC 2017 C213.5 BTL1
A node in a state space tree is said to be promising, if it corresponds to a
18.
partially constructed solution that may still lead to a complete solution.
Otherwise, a node is called non- promising.
Compare backtracking and branch bound techniques. C213.5 BTL2
Backtracking is applicable only to non optimization problems.
19. Backtracking generates state space tree in depth first manner.
Branch and bound is applicable only to optimization problem.
Branch and bound generated a node of state space tree using best first rule.
What are the searching techniques that are commonly used in Branch - C213.5 BTL1
and-Bound method?
20. The searching techniques that are commonly used in Branch-and-Bound
method are:
i)FIFO ii) LIFO iii) LC iv) Heuristic search
Illustrate 8 – Queens problem. C213.5 BTL2
21.

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 The problem is to place eight queens on a 8 x 8 chessboard so that no two
queen “attack” that is, so that no two of them are on the same row, column or
on the diagonal.
What is meant by approximation algorithm ? C213.5 BTL1
An approximation algorithm is a way of dealing with NP-completeness for
an optimization problem. This technique does not guarantee the best
22.
solution. The goal of the approximation algorithm is to come as close as
possible to the optimal solution in polynomial time. Such algorithms are
called approximation algorithms or heuristic algorithms.
Define Optimization Problem C213.5 BTL1
An optimization problem is the problem of finding the best solution from all
24.
feasible solutions. The objective may be either min. or max. depending on the
problem considered.
Define Randomized Algorithm. C213.5 BTL1
Randomized algorithms introduce randomness to improve efficiency or
simplify the algorithm design. By incorporating random choices into their
25. processes, randomized algorithms can often provide faster solutions or better
approximations compared to deterministic algorithms. They are particularly
useful in situations where exact solutions are difficult to find or when a
probabilistic approach is acceptable.

PART – B

BLOOM’S
CO
Q. No. Questions LEVEL

1. Explain in detail about approximation algorithms. [AU-A/M 2023] C213.5 BTL3

Prove that the twice around the tree algorithms is a 2 approximation C213.5 BTL3
2. algorithm for the travelling salesman problem with Euclidean distances.
[AU-A/M 2023]

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET

 Discuss how n - queen’s problem can be solved by C213.5 BTL3
3.
backtracking technique. [AU-N/D2023]
Construct all possible subsets of weights that sum to M for the given C213.5 BTL3
4.
instance n=6 M=30 and weights(1:6)=(5,10,12,13, 15,18) [AU-N/D2023]
Describe travelling salesman problem using branch and bound technique C213.5 BTL6
5.
with an example. [AU-N/D2023]
Infer the steps of greedy algorithm for discrete and continuous knapsack C213.5 BTL1
6.
problem with an example. [AU-N/D2023]
Compare and contrast between P,NP,NP-complete and NP Hard problems C213.5 BTL1
7.
with eg. [AU-N/D2024]
Solve the following instance of the knapsack problem by the branch and C213.5 BTL5
bound algorithm. W=16 [AU-A/M2024]

Item Weight Value

9. 1 10 $100

2 7 $63

3 8 $56

4 4 $12

i) Give a randomized algorithms that runs inO(1) time and gives the right C213.5 BTL5
answer with probability atleast 1/3
10.
ii) Give a randomized algorithms that runs inO(1) time and gives the right
answer with probability atleast 5/93 [AU-N/D2022]

PREPARED BY D.SUJATHA, HOD/AI&DS, SRRCET