DEPARTMENT OF ARTIFICIAL INTELLIGENCE & DATA SCIENCE

AD3351-DESIGN & ANALYSIS OF ALGORITHMS

QUESTION BANK
R 2021

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 1
 DEPARTMENT OF ARTIFICIAL INTELLIGENCE AND DATA SCIENCE

II YEAR / III SEMESTER

REGULATION - 2021
AD3351 - DESIGN AND ANALYSIS OF ALGORITHMS

Faculty In Charge Head of the Department

Mrs. A. Mallika, M.E., Dr. S. Sureshkumar, M.E., Ph.D.,
Assistant Professor, Assistant Professor,
Dept. of Artificial Intelligence and Dept. of Artificial Intelligence and
Data Science Data Science

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 2
 INSTITUTE VISION AND MISSION

VISION:

To become a globally recognized “Centre of Academic Excellence” providing

Quality Education to all students.

MISSION:

To provide Quality Education in the fields of Engineering,

Management, Information, Technology and other Engineering areas.

DEPARTMENT VISION AND MISSION

VISION:

The Vision is to achieve International recognition through research and

innovation supremacy in Artificial Intelligence.

MISSION:

M1: To impart the skills necessary through quality teaching and

learning process.
M2: To acquire innovation through hands-on training.
M3: To provide best research opportunities through well designed
curriculum.
M4: Our Mission is achieved through highest quality of teaching,
learning, research opportunities through well designed
curriculum.

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 3
 PROGRAM EDUCATIONAL OBJECTIVES (PEOS)

PEOs Content

Utilize their proficiencies in the fundamental knowledge of basic sciences,

PEO1 mathematics, Artificial Intelligence, data science and statistics to build systems
that require management and analysis of large volumes of data.

Advance their technical skills to pursue pioneering research in the field of AI and
PEO2 Data Science and create disruptive and sustainable solutions for the welfare
of ecosystems.

Think logically, pursue lifelong learning and collaborate with an ethical attitude in
PEO3
a multidisciplinary team.

PEO4 Design and model AI based solutions to critical problem domains in the real world.

Exhibit innovative thoughts and creative ideas for effective contribution towards
PEO5
economy building.

PROGRAM OUTCOMES (POS)

POs Title Content
Apply the knowledge of mathematics, science,
engineering fundamentals, and an engineering
PO1 Engineering knowledge
specialization to the solution of complex
engineering problems.
Identify, formulate, review research literature, and
analyze complex engineering problems reaching
PO2 Problem analysis substantiated conclusions using first principles of
mathematics, natural sciences, and engineering
sciences.
Design solutions for complex engineering problems
and design system components or processes that meet
Design/development of
PO3 the specified needs with appropriate consideration for
solutions
the public health and safety, and the cultural, societal,
and environmental considerations.
Use research-based knowledge and research methods
Conduct investigations of including design of experiments, analysis and
PO4
complex problems interpretation of data, and synthesis of the
information to provide valid conclusions.
Create, select, and apply appropriate techniques,
resources, and modern engineering and IT tools
PO5 Modern tool usage including prediction and modeling to complex
engineering activities with an understand of the
limitations.

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 4
 Apply reasoning informed by the contextual
knowledge to assess societal, health, safety, legal and
PO6 The engineer and society
cultural issues and the consequent responsibilities
relevant to the professional engineering practice.
Understand the impact of the professional
Environment and engineering solutions in societal and environmental
PO7
sustainability contexts, and demonstrate the knowledge of, and
need for sustainable development.
Apply ethical principles and commit to professional
PO8 Ethics ethics and responsibilities and norms of the
engineering practice.
Function effectively as an individual, and as a
PO9 Individual and team work member or leader in diverse teams, and in
multidisciplinary settings.
Communicate effectively on complex engineering
activities with the engineering community and with
society at large, such as, being able to comprehend
PO10 Communication
and write effective reports and design documentation,
make effective presentations, and give and receive
clear instructions.
Demonstrate knowledge and understand of the
engineering and management principles and apply
Project management and
PO11 these to one‘s own work, as a member and leader in a
finance
team, to manage projects and in multidisciplinary
environments.
Recognize the need for, and have the preparation and
ability to engage in independent and life-long
PO12 Life-long learning
learning in the broadest context of technological
change.

PROGRAM SPECIFIC OUTCOMES (PSOS)

PSOs Content

Evolve AI based efficient domain specific processes for effective decision making
PSO1
in several domains such as business and governance domains.

Arrive at actionable Foresight, Insight, hindsight from data for solving business and
PSO2
engineering problems.
Create, select and apply the theoretical knowledge of AI and Data Analytics along
PSO3 with practical industrial tools and techniques to manage and solve wicked societal
problems.
Develop data analytics and data visualization skills, skills pertaining to
PSO4 knowledge acquisition, knowledge representation and knowledge engineering, and
hence be capable of coordinating complex projects.

Able to carry out fundamental research to cater the critical needs of the society
PSO5
through cutting edge technologies of AI.

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 5
AD3351 DESIGN AND ANALYSIS OF ALGORITHM LTPC
3 024

UNIT - I INTRODUCTION 8

Notion of an Algorithm – Fundamentals of Algorithmic Problem Solving – Important Problem

Types –Fundamentals of the Analysis of Algorithm Efficiency – Analysis Framework -
Asymptotic Notations and their properties – Empirical analysis - Mathematical analysis of
Recursive and Nonrecursive algorithms – Visualization.

UNIT - II BRUTE FORCE AND DIVIDE AND CONQUER 10

Brute Force – String Matching - Exhaustive Search - Traveling Salesman Problem - Knapsack
Problem - Assignment problem. Divide and Conquer Methodology – Multiplication of Large
Integers and Strassen’s Matrix Multiplication – Closest-Pair and Convex - Hull Problems.
Decrease and Conquer: - Topological Sorting – Transform and Conquer: Presorting – Heaps
and Heap Sort.

UNIT - III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE 10

Dynamic programming – Principle of optimality - Coin changing problem – Warshall’s and

Floyd‘s algorithms – Optimal Binary Search Trees - Multi stage graph - Knapsack Problem
and Memory functions. Greedy Technique – Dijkstra’s algorithm - Huffman Trees and codes -
0/1 Knapsack problem.

UNIT - IV ITERATIVE IMPROVEMENT 8

The Simplex Method-The Maximum-Flow Problem – Maximum Matching in Bipartite

Graphs- The Stable marriage Problem

UNIT - V LIMITATIONS OF ALGORITHM POWER 9

Lower - Bound Arguments - P, NP, NP- Complete and NP Hard Problems. Backtracking –
NQueen problem - Hamiltonian Circuit Problem – Subset Sum Problem. Branch and Bound –
LIFO 59 Search and FIFO search - Assignment problem – Knapsack Problem – Traveling
Salesman Problem - Approximation Algorithms for NP-Hard Problems – Traveling Salesman
problem – Knapsack problem.

Total : 45 Periods

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 6
 COURSE OUTCOMES

At the end of this course, the students will be able to:

CO1 Analyze the efficiency of recursive and non-recursive algorithms mathematically

Analyze the efficiency of brute force, divide and conquer, decrease and conquer,
CO2 Transform and conquer algorithmic techniques

Implement and analyze the problems using dynamic programming and greedy
CO3 algorithmic techniques.

CO4 Solve the problems using iterative improvement techniques for optimization.

Compute the limitations of algorithmic power and solve the problems using
CO5 backtracking and branch and bound techniques

CO’S- PO’S & PSO’S MAPPING

PO’s PSO’s
CO’s
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3

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

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

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

CO4 3 2 3 2 2 - - - 2 2 2 2 3 1 3

CO5 3 1 2 3 3 - - - 2 2 2 2 3 1 3

AVG 3 2 2 2 2 - - - 2 2 2 2 2 2 2

1 - Low, 2 - Medium, 3 - High, ‘-' - No Correlation

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 7
TEXT BOOK

1. Anany Levitin, Introduction to the Design and Analysis of Algorithms, Third Edition,
Pearson Education, 2012.

REFERENCE BOOKS

1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/

C++, Second Edition, Universities Press, 2019.
2. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein,
Introduction to Algorithms, Third Edition, PHI Learning Private Limited, 2012.
3. S. Sridhar, Design and Analysis of Algorithms, Oxford university press, 2014.
4. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, Data Structures and
Algorithms, Pearson Education, Reprint 2006.

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 8
 UNIT I
INTRODUCTION

PART - A
Q. CO
Questions BT Level Complexity
No Mapping
State the transpose symmetry property of O
1. CO1 Remember Low
and Ω.
2. Define recursion. CO1 Remember Low
How do you measure the efficiency of an
3. CO1 Understand Low
Algorithm?
Prove that f(n)= O(g(n)) and g(n)=O(f(g(n))
4. CO1 Create Medium
then f(n)=(g(n)).
5. What is an Algorithm? CO1 Understand Low

6. How to measure algorithm’s running time? CO1 Understand Low

7. Compare the order of growth n(n-1)/2 and n2.. CO1 Evaluate Medium

8. Define recurrence relation. CO1 Remember Low

Write down the properties of asymptotic
9. notations. CO1 Understand Low

Give the Euclid’s Algorithm for Computing

10. CO1 Understand Low
GCD (m,n).
Write an algorithm to find the number of
11. binary digits in the binary representation of a CO1 Understand Medium
positive decimal integer.

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 9
 PART - B
Q. CO
Questions BT Level Complexity
No Mapping
Write short note on Fundamentals of
1. CO1 Understand Medium
Algorithmic Problem Solving.
Discuss about the fundamental analysis of
2. CO1 Understand Medium
efficiency algorithm.
Explain the asymptotic notation and its
3. CO1 Understand Medium
properties.
List out the Steps in Mathematical Analysis of
4. CO1 Remember High
non- recursive Algorithms.
List out the Steps in Mathematical Analysis of
5. CO1 Remember High
recursive Algorithms.
Write an Algorithm using recursion that
6. determines the GCD of two numbers. CO1 Create High
Determine the time and space complexity.
Compare the orders of growth following time
complexity functions.
7. a. n(n-1)/2 and 𝑛2 CO1 Evaluate High
b. log n and √𝑛
c. n! and 2𝑛
Prove that if f(n) = O(g(n)) and g(n) = O((n)) then
8. CO1 Create High
f(n)= 𝜃(𝑔(𝑛)).
Explain the recursive algorithm to solve Towers
9. CO1 Understand Medium
of Hanoi problem.
Describe graph problems and combinatorial
10. CO1 Understand Medium
problems in detail.

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 10
 UNIT II
BRUTE FORCE AND DIVIDE AND CONQUER

PART - A
Q. CO
Questions BT Level Complexity
No Mapping
1. State the Convex Hull Problem. CO2 Remember Low
Write the Brute force algorithm to string
2. CO2 Understand Low
matching.
What is the time and space complexity of
3. CO2 Understand Low
Merge Sort?
4. What is exhaustive search? CO2 Understand Low

5. State Master’s Theorem. CO2 Remember Medium

6. What is Closest Pair Problem? CO2 Understand Low

Give the General Plan for Divide and Conquer
7. CO2 Understand Low
Algorithms.
8. Write the advantages of insertion sort. CO2 Understand Low

9. Describe the Complexity of Binary Search. CO2 Understand Medium

10. Write about travelling sales person problem? CO2 Understand Low

11. What is binary search? CO2 Understand Low

12. What is Knapsack problem? CO2 Understand Low

Write the algorithm for Iterative binary
13. CO2 Understand Low
search?
Define internal path length and external path
14. CO2 Remember Low
length.

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 11
 PART - B
Q. CO
Questions BT Level Complexity
No Mapping
Explain the divide and conquer technique.
1. Apply this method to find multiplication on CO2 Apply High
integers 2101 and 1130 .
2. Explain Merge Sort with suitable example. CO2 Understand Medium
Discuss Quick Sort algorithm with suitable
3. example and derive Worst case and Average CO2 Understand Medium
Case Complexity.
Describe Travelling person sales problem
using exhaustive search technique and find
the optimal tour for the following graph.

4. CO2 Understand Medium

Solve the Knapsack problem, use exhaustive

search technique to find solution, The
capacity is W=8
I 𝑊𝑖 𝑉𝑖
5. CO2 Create High
1 2 $1
2 3 $2
3 4 $8
4 5 $6
Write algorithm to find closest pair of points
using divide and conquer and explain it with
6. CO2 Create Medium
example. Derive the worst case and average
case time complexity.
What is Convex hull problem? Explain the
7. brute force approach to solve convex-hull CO2 Understand Medium
with an example. Derive time complexity.
8. Explain about DFS algorithm in detail. CO2 Understand Medium

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 12
 PART - B
Q. CO
Questions BT Level Complexity
No Mapping
Apply the DFS-based algorithm to solve the
topological sorting problem for the
following digraph:

9. CO2 Apply High

Solve the assignment problem, use exhaustive

search technique to find solution
Job Job Job Job
1 2 3 4
10. CO2 Create High
Person 1 9 2 7 8
Person 2 6 4 3 7
Person 3 5 8 1 8
Person 4 7 6 9 4

Construct a presorting based algorithm to

11. compute the mode of a given list of numbers. CO2 Create Medium
For example, for 5,1,5,7,6,5,7 the mode is 5.
12. Explain in detail about heap sort algorithm. CO2 Understand Medium
Apply Strassen’s algorithm to computing the
products of 2-by-2 matrices by the brute-force
algorithm:

13. CO2 Apply High

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 13
 UNIT-III
DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

PART - A
Q. CO
Questions BT Level Complexity
No Mapping
1. State the Principle of Optimality. CO3 Remember Low
What is the Constraint for binary search tree
2. CO3 Understand Low
for insertion?
3. Define multistage graph. CO3 Remember Low
How Dynamic Programming is used to solve
4. CO3 Understand Medium
Knapsack Problem?
5. Define transitive closure of directive graph. CO3 Remember Low

6. Define the Minimum Spanning tree problem. CO3 Remember Low

7. What does Floyd’s Algorithm do? CO3 Understand Low

8. State the Assignment Problem. CO3 Remember Low

Define the Single Source Shortest Path
9. CO3 Remember Low
Problem.
List out the memory function under dynamic
10. CO3 Remember Low
programming.
11. What is a Huffman tree? CO3 Understand Low

12. List the advantage of Huffman’s encoding. CO3 Remember Low

13. What is greedy method? CO3 Understand Low

14. Define Kruskal Algorithm. CO3 Understand Low

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 14
 PART - B
Q. CO
Questions BT Level Complexity
No Mapping
Write short note on Greedy Method with
1. CO3 Understand High
suitable example.

Explain in detail about the Floyd’s

Algorithm and solve the following problem.

2. CO3 Understand High

Explain in detail about the Huffman code for

A = {a/20, b/15, c/5, d/15, e/45} be the
3. CO3 Understand Medium
alphabet and its frequency distribution using
the following graph.

Explain the Optimal Binary Search Tree in

detail.
4. CO3 Understand High
Keys 10 20 30 40
Frequency 4 2 6 3

Apply the above algorithm to solve the all-

pairs shortest path problem for the digraph
with the following weight matrix:

5. CO3 Apply High

Explain in detail about the Coin changing

6. CO3 Understand Medium
problem with an example.
What does dynamic programming have in
7. CO3 Understand Medium
common with divide-and-Conquer?

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 15
 PART - B
Q. CO
Questions BT Level Complexity
No Mapping
Solve the following Multi stage graph.

8. CO3 Understand High

Explain in detail about the Knapsack Problem

for n =4, V = {10, 10, 12, 18}, w = {2, 4, 6,
9. CO3 Understand High
9} and W = 6 using dynamic programming
memory function technique.
Explain the following Dijkstra’s Algorithm.

10. CO3 Understand High

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 16
 UNIT- IV
ITERATIVE IMPROVEMENT

PART - A
Q. CO
Questions BT Level Complexity
No Mapping
1. State the Principle of Duality. CO4 Remember Low
Define the Capacity Constraint in the
2. CO4 Remember Low
context of Maximum flow problem.
3. Define iterative improvement technique. CO4 Remember Low

4. What is solution space? Give an example. CO4 Understand Low

5. What is articulation point in graph? CO4 Understand Low

6. What is state space graph? CO4 Understand Low

What do you mean by ‘perfect matching’ in
7. CO4 Understand Low
bipartite graph?
8. Define Flow ‘cut’. CO4 Remember Low

9. What is maximum cardinality matching? CO4 Understand Low

10. What is meant by Bipartite Graph? CO4 Understand Low

11. Define Stable Marriage Problem. CO4 Remember Medium

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 17
 PART - B
Q. CO
Questions BT Level Complexity
No Mapping
Explain in detail about Maximum Flow
1. CO4 Understand High
Problem.
Illustrate the stable marriage problem with
2. CO4 Analyze Medium
example.
Explain the following problem in the standard
form.

3. CO4 Understand High

Solve the following equation using Simplex

Method.
Maximize: 18x1+ 12.5x2
4. Subject to x1+x2<=20 CO4 Create High
x1<=12
x2<=16
x1,x2>=0
Starting from the following flow (printed
above or to the right of the capacities),
Perform one iteration of the Ford-Fulkerson
algorithm Choose a shortest augmenting path,
i.e., the path with the fewest number of arcs.
5. CO4 Create High

Write the shortest augmenting path.

Explain the maximum matching in bipartite
graph.

6. CO4 Understand High

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 18
 PART - B
Q. CO
Questions BT Level Complexity
No Mapping
Explain Ford Fulkerson algorithm for the
following.

7. CO4 Understand High

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 19
 UNIT V
SECURITY PRACTICES

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

2. State Hamiltonian Circuit Problem. CO5 Remember Low

3. Define P and NP Problems. CO5 Remember Low

4. Define sum of subset Problem. CO5 Remember Low

Differentiate Feasible and Optimal
5. CO5 Understand Medium
Solution.
State the reason for terminating search path
6. at the current node in branch and bound CO5 Remember Low
algorithm.
How is lower bound found by problem
7. CO5 Understand Low
reduction?
Compare backtracking and branch bound
8. CO5 Evaluate Medium
techniques.
9. Define Branch-and-Bound method. CO5 Remember Low
Write the application for Knapsack
10. CO5 Understand Low
problem
11. Illustrate 8 – Queens problem. CO5 Analyze Medium

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 20
 PART - B
Q. CO
Questions BT Level Complexity
No Mapping
How backtracking technique can be used
1. to solve the n-queens problem? Explain CO5 Understand Medium
with an example.
Explain Backtracking technique with
2. CO5 Understand Medium
suitable example.
Evaluate the solution for Subset sum
3. CO5 Evaluate High
problem using Backtracking technique.
4. Explain P, NP and NP complete problems. CO5 Understand Medium
Explain the approximation algorithm for
5. CO5 Understand Medium
the travelling salesman problem (TSP).
Discuss the steps to find approximate
solution to NP-Hard optimization
6. CO5 Understand Medium
problems using approximation algorithms
with an example.
Solve the following instance of the
knapsack problem by the branch-and
bound algorithm.

item weight value

7. 1 10 ₹100 CO5 Create High
2 7 ₹63
3 8 ₹56
4 4 ₹12

W=16
Solve the Hamiltonian circuit using
Backtracking method.

8. CO5 Create High

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 21
 THANK YOU

ALL THE BEST

Prepared by
Mrs. A. Mallika / AP
J. J. College of Engineering and Technology Page 22