DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

& INFORMATION TECHNOLOGY & CYBER SECURITY

SUBJECT CODE :

CS3401 – ALGORITHMS
QUESTION BANK

PREPARED BY

Ms S.ASHWINI NAIDU

Assistant professor

AI&DS Department
  Vision:
To be a leading department in computer science education and research, recognized for its
innovative contributions and impact on society.
 Mission:
To provide a high-quality education in computer science, foster a culture of research and
innovation, and prepare graduates to be leaders and innovators in the field.

MISSION:
M1 Producing successful graduates enriched with professional and leadership capabilities.
M2 Imparting the skills necessary to continue education and grow professionally.
M3 Inculcating strong ethical and human values.
M4 Establishing a research centre in Computer Science and Engineering.
M5 Contributing towards empowering the rural youth with computer Education.
PROGRAM EDUCATIONAL OBJECTIVES (PEOs)

Apply their technical competence in computer science to solve real world

PEO1
problems, with technical and people leadership.
Conduct cutting edge research and develop solutions on problems of social
PEO2
relevance.
Work in a business environment, exhibiting team skills, work ethics,
PEO3
adaptability and lifelong learning.

Engineering knowledge: Apply the knowledge of mathematics, science,

PO1 engineering fundamentals and an engineering specialization to the solution of
Complex engineering problems.
Problem analysis: Identify, formulate, review research literature, and
analyze complex engineering problems reaching substantiated conclusions
PO2 Using first principles of mathematics, natural sciences, and engineering
sciences.
Design / development of solutions: Design solutions for complex
engineering problems and design system components or processes that meet
PO3 the specified needs with appropriate consideration for public health and
safety, and the cultural, societal, and environmental considerations.
Conduct investigations of complex problems: Use research-based
knowledge and research methods including the design of experiments,
PO4
Analysis and interpretation of data, and synthesis of the information to
provide valid conclusions.
Modern tool usage: Create, select, and apply appropriate techniques,
resources, and modern engineering and IT tools including prediction and
PO5
Modeling to complex Engineering activities with an Understand of the
limitations.
The engineer and society: Apply to reason in formed by the contextual
PO6 Knowledge to assess societal, health, safety, legal and cultural issues and the
Consequent responsibilities relevant to the professional engineering practice.
Environment and sustainability: Understand the impact of the professional
PO7 engineering solutions in societal and environmental contexts, and
demonstrate the knowledge of, and need for sustainable development.
Ethics: Apply ethical principles and commit to professional ethics and
PO8
Responsibilities and norms of the engineering practice.
Individual and team work: Function effectively as an individual, and as a
PO9
Member or leader in Diverse teams, and in multidisciplinary settings.
 Communication: Communicate effectively on complex engineering
activities with the engineering community and with society at large, such as,
PO10 being able To comprehend And write effective reports and design
documentation, make effective presentations, and give and Receive clear
instructions.
Project management and finance: Demonstrate knowledge and Understand
of the engineering and management principles and apply these to one’s own
PO11 work, as a member and leader in a team, to manage projects and in
multidisciplinary environments.
Life-long learning: Recognize the need for, and have the preparation and
ability to Engage in in dependent and life-long learning in the broadest
PO12
context of technological change.

Exhibit design and programming skills to build and automate business

PSO1
solutions using cutting edge technologies.
Strong theoretical foundation leading to excellence and excitement towards
PSO2
research, to provide elegant solutions to complex problems.
Strong theoretical foundation leading to excellence and excitement towards
PSO3
research, to provide elegant solutions to complex problems.
 CS3401 ALGORITHMS LTPC
3 0 2 4
COURSE OBJECTIVES:
 To understand and apply the algorithm analysis techniques on searching and
sorting algorithms.
 To critically analyze the efficiency of graph algorithms.
 To understand different algorithm design techniques.
 To solve programming problems using state space tree.
 To understand the concepts behind NP Completeness, Approximation
algorithms and randomized algorithms.

UNIT I INTRODUCTION 9
Algorithm analysis: Time and space complexity - Asymptotic Notations and its
properties Best case, Worst case and average case analysis – Recurrence relation:
substitution method - Lower bounds – searching: linear search, binary search and
Interpolation Search, Pattern search: The naïve string-matching algorithm - Rabin-
Karp algorithm - Knuth-Morris-Pratt algorithm. Sorting: Insertion sort – heap sort.
UNIT II GRAPH ALGORITHMS 9
Graph algorithms: Representations of graphs - Graph traversal: DFS – BFS -
applications - Connectivity, strong connectivity, bi-connectivity - Minimum spanning
tree: Kruskal’s and Prim’s algorithm- Shortest path: Bellman-Ford algorithm -
Dijkstra’s algorithm - Floyd-Warshall algorithm Network flow: Flow networks -
Ford- Fulkerson method – Matching: Maximum bipartite matching.

UNIT III ALGORITHM DESIGN TECHNIQUES 9

Divide and Conquer methodology: Finding maximum and minimum - Merge sort -
Quick sort Dynamic programming: Elements of dynamic programming — Matrix-
chain multiplication - Multi stage graph — Optimal Binary Search Trees. Greedy
Technique: Elements of the greedy strategy - Activity-selection problem –- Optimal
Merge pattern - Huffman Trees.

UNIT IV STATE SPACE SEARCH ALGORITHMS 9

Backtracking: n-Queens problem - Hamiltonian Circuit Problem - Subset Sum
Problem – Graph colouring problem Branch and Bound: Solving 15-Puzzle problem
- Assignment problem - Knapsack Problem - Travelling Salesman Problem.
 UNIT V NP-COMPLETE AND APPROXIMATION ALGORITHM 9
Tractable and intractable problems: Polynomial time algorithms – Venn diagram
representation - NP-algorithms - NP-hardness and NP-completeness – Bin
Packing problem - Problem reduction: TSP – 3-CNF problem. Approximation
Algorithms: TSP - Randomized Algorithms: concept and application - primality
testing - randomized quick sort - Finding kth smallest number.
TOTAL : 45 PERIODS

On completion of this course, the students expected to be able to:

To understand and apply the algorithm analysis techniques on
CO1
searching and sorting algorithms.
CO2 To critically analyze the efficiency of graph algorithms.

CO3 To understand different algorithm design techniques.

CO4 To solve programming problems using state space tree.

To understand the concepts behind NP Completeness, Approximation

CO5
algorithms and randomized algorithms.

Correlation of COs with POs / PSOs

COs PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3

CO1 3 2 - - - 1 - - - - 1 - 1 -

CO2 2 3 - - - - 1 - - - - 1 - 1 -

CO3 1 2 3 1 - - 2 - - - - - - 1 1

CO4 1 1 - - - - - - - - - - - - -

CO5 1 1 - - - - - - - - - - - - -

AVG. 2.67 1.8 3 1 - - 1.33 - - - - 1 - 1 1

3 – High; 2 – Medium; 1 – Low; ‘-‘ - No Correlation

TEXT BOOKS:
1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein,
"Introduction to Algorithms", 3rd Edition, Prentice Hall of India, 2009.
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran “Computer Algorithms/C++”
Orient Blackswan, 2nd Edition, 2019.

REFERENCE BOOKS:
1. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, 3rd Edition,
Pearson Education, 2012.
 UNIT– I

INTRODUCTION

PART–A
Q. No Questions CO Mapping BT Level Complexity
1 Define time and space complexity. CO1 Remember Low

2 What are asymptotic notations? CO1 Understand Low

Differentiate best, worst, and average case
3 CO1 Understand Low
analysis.
Write the recurrence relation for Tower of
4 CO1 Create High
Hanoi.

5 Define the working of binary search. CO1 Remember Low

List the advantages of interpolation

6 CO1 Remember Low
search over binary search.
What is the role of a prefix function in the
7 CO1 Understand Low
KMP algorithm?
State the purpose of Rabin-Karp
8 CO1 Remember Low
algorithm.
9 Compare insertion sort and heap sort. CO1 Analyze Medium
How does the naive string matching
10 CO1 Understand Low
algorithm work?

PART–B
Q. No Questions CO Mapping BT Level Complexity
Analyze the time complexity of linear
1 search, binary search, and interpolation CO1 Analyze Medium
search.
Illustrate recurrence relations and solve
2 T(n) = 3T(n/2) + n using substitution CO1 Analyze Medium
method.
Compare the working principles of
3 Knuth-Morris-Pratt and Rabin-Karp CO1 Evaluate High
algorithms.
Design an algorithm for heap sort and
4 CO1 Create High
analyze its time complexity.
 Discuss the significance of lower bounds
5 CO1 Understand Low
in algorithm analysis.

Analyze and compare the complexities

6 of sorting algorithms: insertion sort, CO1 Analyze Medium
quick sort, and heap sort.

Explain how recurrence relations are

7 CO1 Understand Low
solved using recursion tree method.

Design a pattern matching algorithm

8 using the KMP approach and analyze CO1 Create High
its efficiency.
Evaluate the impact of different case
9 complexities (best, worst, and average) CO1 Evaluate High
on sorting algorithms.

Demonstrate the working of Rabin-Karp

10 CO1 Create High
algorithm with an example.
 UNIT – II
GRAPH ALGORITHMS

PART–A

Q. No Questions CO Mapping BT Level Complexity

1 Define graph traversal. CO2 Remember Low

2 Differentiate DFS and BFS. CO2 Understand Low

3 What is a minimum spanning tree? CO2 Remember Low

Define the use of Bellman-Ford
4 CO2 Remember Low
algorithm.
List the applications of network flow
5 CO2 Remember Low
algorithms.
What is bipartite matching in graph
6 CO2 Understand Low
theory?
Compare Dijkstra’s and Floyd-Warshall
7 CO2 Evaluate High
algorithms.

8 Define strong connectivity in graphs. CO2 Remember Low

What is the difference between

9 CO2 Understand Low
Kruskal’s and Prim’s algorithms?

10 What is the Ford-Fulkerson method? CO2 Understand Low

PART–B
Q. No Questions CO Mapping BT Level Complexity
Explain DFS and BFS with their
1 CO2 Understand Low
applications.
Illustrate Kruskal’s algorithm to find
the minimum spanning tree of a graph
and analyze its complexity.
2 CO2 Apply Medium
 Apply an appropriate algorithm to
find the shortest path from “A” to
every other node of “A” for the given
graph.
3 CO2 Apply Medium

Run the Bellman-Ford algorithm on

the directed graph of the given figure
below using vertex ‘s’ as the source
and show the results after each pass of
an algorithm.
4 CO2 Analyze Medium

Discuss the maximum bipartite

5 CO2 Understand Low
matching problem and its
applications.
Apply Ford Fulkerson algorithm for
the following example.

6 CO2 Apply Medium

Analyze the time complexity of various

7 CO2 Evaluate High
graph traversal algorithms.
Apply Floyd Warshall algorithm for
the following example.

8 CO2 Apply Medium

Design a solution for bi-connectivity in

9 CO2 Create High
graphs using DFS.

Compare and contrast minimum

10 CO2 Evaluate High
spanning tree algorithms.
 UNIT – III
ALGORITHM DESIGN TECHNIQUES

PART–A
Q. No Questions CO Mapping BT Level Complexity

1 Define divide and conquer technique. CO3 Remember Low

What is the optimal substructure

2 CO3 Understand Low
property?
List the steps of the greedy algorithm
3 CO3 Remember Low
approach.
How does Merge Sort differ from Quick
4 CO3 Understand Low
Sort?
5 Define the activity selection problem. CO3 Remember Low
What is the time complexity of Huffman
6 CO3 Understand Low
Coding?
How does recursion differ from dynamic
7 CO3 Understand Low
programming?

Explain how the Principle of Optimality

8 CO3 Understand Low
is used in solving optimization problems.

State the importance of Matrix Chain

9 CO3 Remember Low
Multiplication.
Write an example of a real-world
10 application of an Optimal Binary Search CO3 Understand Medium
Tree.

PART–B
Q. No Questions CO Mapping BT Level Complexity
Explain the Divide and Conquer strategy
1 CO3 Apply Medium
with Merge Sort as an example.

Implement Quick Sort and analyze its

2 best, worst, and average case CO3 Apply Medium
complexities.

Explain in detail about the Matrix chain

Multiplication for A1(5X4), A2(4X6),
3 CO3 Understand Low
A3(6X2) and A4(2X7) using Dynamic
Programming Technique.
 Write the Huffman’s Algorithm.
Construct the Huffman’s tree for the
following data and obtain its Huffman’s
4 Code. Create High 15
Character A B C D E -
Probability 0.5 0.35 0.5 0.1 0.4 0.2

Explain the Optimal Binary Search Tree

in detail.
5 Keys 10 20 30 40 CO3 Understand Low
Frequency 4 2 6 3

Explain in detail about the Activity

Selection Problem using Dynamic
6 Programming Technique. CO3 Understand Low
Start 1 3 2 0 5 8 11
End 3 4 5 7 9 10 12

Compare Divide and Conquer, Dynamic

7 Programming, and Greedy techniques CO3 Evaluate High
with suitable examples.
Explain the Multi-stage Graph Problem
8 and its solution using dynamic CO3 Understand Low
programming.

Design and analyze an efficient

9 CO3 Create High
algorithm for the Optimal Merge Pattern.

Illustrate Huffman Encoding process

with an example.
10 A = {a/20, b/15, c/5, d/15, e/45} be the CO3 Apply Medium
alphabet and its frequency distribution
using the following graph.
 UNIT – IV
STATE SPACE SEARCH ALGORITHMS

PART–A
Q. No Questions CO Mapping BT Level Complexity

1 Define Backtracking. CO4 Remember Low

What is the significance of the n-Queens
2 CO4 Understand Low
problem?
3 State the principle of Branch and Bound. CO4 Remember Low
What is the difference between
4 CO4 Analyze Medium
Backtracking and Branch and Bound?
Give an example of the Subset Sum
5 CO4 Apply Medium
Problem.
Draw the Hamiltonian circuit for the given
graph.

6 CO4 Remember Low

What are the applications of the Graph

7 CO4 Understand Low
Coloring Problem?

State the time complexity of the Travelling

8 CO4 Remember Low
Salesman Problem.

What is the purpose of the 15-Puzzle

9 CO4 Understand Low
Problem?

Describe the Assignment Problem in

10 CO4 Understand Low
optimization.

PART–B
Q. No Questions CO Mapping BT Level Complexity

Solve the n-Queens problem using

1 CO4 Create High
Backtracking and analyze its complexity.

Explain in detail about the sum of subset

2 Problem for 3 items w1 = 2, w2 = 4, w3 = CO4 Understand Low
6 and S = 6 using Backtracking
Technique.
 Describe the Travelling Salesman Problem
3 CO4 Understand Low
and explain its solution approaches.
Solve the 15-Puzzle problem using the
Branch and Bound technique.

4 CO4 Create High

Compare Backtracking and Branch and

5 CO4 Evaluate High
Bound with suitable examples.
Explain in detail about Hamiltonian
Circuit Problem for the following graph
using Backtracking Technique.
6 CO4 Understand Low

Solve the Assignment Problem and how it

is solved using Branch and Bound
technique.
Job1 Job2 Job3 Job4
7 CO4 Create High
A 9 2 7 8
B 6 4 3 7
C 5 8 1 8
D 7 6 9 4

Solve the Graph Coloring Problem using

Backtracking and analyze its complexity.
M={G,B,R}
8 CO4 Create High

Explain in detail about the Knapsack

Problem for n =4, V = {10, 10, 12, 18},
9 Understand Low
w = {2, 4, 6, 9} and W = 15 using Branch CO4
and Bound technique.

Implement the Travelling Salesman

10 Problem using the Branch and Bound CO4 Apply Medium
approach.
 Solve the following instance of Knapsack
problem by Branch and bound Algorithm
Item weight profit

11 CO3 Create High

PART–A
Q. No Questions CO Mapping BT Level Complexity
1 Define NP-Completeness. CO5 Remember Low

2 What is an NP-Hard problem? CO5 Understand Low

Define the significance of the Bin Packing
3 CO5 Remember Low
problem.
State the difference between NP and P
4 CO5 Remember Low
problems.
Define Problem Reduction in
5 CO5 Remember Low
computational complexity.
What is the role of Approximation
6 CO5 Understand Low
Algorithms?
Explain the significance of randomized
7 CO5 Understand Low
algorithms.
What is the purpose of Primality Testing in
8 CO5 Understand Low
randomized algorithms?

9 Write a short note on 3-CNF Problem. CO5 Understand Low

How does Randomized Quick Sort differ

10 CO5 Understand Low
from deterministic Quick Sort?
 PART–B
Q. No Questions CO Mapping BT Level Complexity
Explain the significance of NP-
1 CO5 Understand Low
Completeness with suitable examples.

Describe the Bin Packing Problem and its

2 CO5 Understand Low
Approximation Algorithms.

Explain the concept of problem reduction

3 CO5 Understand Low
using TSP and 3-CNF examples.

Analyze an Approximation Algorithm for

4 CO5 Analyze Medium
TSP.

Explain the role of randomized algorithms

5 CO5 Understand Low
in Primality Testing.

Compare NP, NP-Hard, and NP-Complete

6 CO5 Evaluate High
problems with examples.

Illustrate the Randomized Quick Sort and

7 CO5 Analyze Medium
analyze its performance.

Discuss the significance of the kth

8 smallest number problem using CO5 Understand Low
randomized methods.

Analyze the performance of an

9 Approximation Algorithm for a given CO5 Analyze Medium
problem.

Design an efficient Randomized Algorithm

10 CO5 Create High
for an optimization problem.