Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.

F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

Faculty Name :Mrs.D.KARTHIKA Designation &Dept of Faculty :AP/AI&DS

Course code
:243 Dept (Course) :AI&DS
(as per NBA)

Prerequisite for the Programme:

● DATA STRUCTURES KNOWLEDGE

● DISCRETE MATHEMATICS

Course Objectives:
● To critically analyze the efficiency of alternative algorithmic solutions for the same
problem.
● To illustrate brute force and divide and conquer design techniques.
● To explain dynamic programming and greedy techniques for solving various
problems.
● To apply iterative improvement technique to solve optimization problems
● To examine the limitations of algorithmic power and handling it in different
problems.

Course Outcomes:

CO
Description
Number
Analyze the efficiency of recursive and non-recursive algorithms mathematically
CO1
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

CO3
greedy algorithmic techniques.

CO4 Solve the problems using iterative improvement techniques for optimization

Compute the limitations of algorithmic power and solve the problems

CO5
using backtracking and branch and bound techniques.

Text Books:
Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

S.No Name of the Book Serial Number

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

References:

S.No Name of the Book/Material Serial Number

Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran,
1 Computer Algorithms/ C++, Second Edition, Universities R1
Press, 2007.
Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest
2 and Clifford Stein, ―Introduction to Algorithms‖, Third R2
Edition, PHI Learning Private Limited, 2012.
Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman,
3 ―Data Structures and Algorithms‖, Pearson Education, R3
Reprint 2006.
S. Sridhar, Design and Analysis of Algorithms, Oxford
4 R4
university press, 2014.

Teaching Aids Used:

S.No Name of the Teaching Aids Serial Number

1 Black board A1
2 OHP/LCD A2
3 Models A3
4 Simulation by Computer A4
5 Internet Resources/Tools A5
Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

Date :07.08.2024
Unit No. :I Unit Title: Introduction

Objective: To Understand and apply the algorithm analysis techniques

S.No. Topic Periods

1 Notion of an algorithm 1

2 Fundamentals of Algorithmic Problem Solving 1

3 Important Problem Types 1

4 1
Fundamentals of the Analysis of Algorithm Efficiency
5 1
Asymptotic Notations and their properties
6 1
Analysis Framework,
7 1
Empirical analysis
8 Mathematical analysis for Recursive algorithms 1

9 Mathematical analysis for Non Recursive algorithms 1

10 Visualization 1

Serial numbers of suggested Textbooks/References/ Teaching Aids Page Numbers

Anany Levitin, ―Introduction to the Design and Analysis of
Algorithms‖, Third Edition, Pearson Education, 2012.
1-10
 Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

Date :07.08.2024
Unit No. :II Unit Title: Brute Force and Divide and Conquer

Objective: To critically analyze the efficiency of alternative algorithmic solutions for the same
problem

S.No. Topic Periods

1 Brute Force – Computing an – String Matching 1

2 Exhaustive Search 1

3 Travelling Salesman Problem 1

4 Knapsack Problem 1

5 Assignment Problem 1

6 Divide and Conquer methodology 1

7 Multiplication of Large Integers- and Strassen’s Matrix Multiplication 1

8 Closest-pair and Convex-Hull Problems 1

9 Decrease and Conquer: - Topological Sorting 1

10 Transform and Conquer: Presorting 1

11 Heaps and Heap Sort 1

Serial numbers of suggested Textbooks/References/ Teaching Aids Page Numbers

Anany Levitin, ―Introduction to the Design and Analysis of
Algorithms‖, Third Edition, Pearson Education, 2012.
1-11
Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

Date :07.08.2024
Unit No. :III Unit Title: Dynamic Programming and Greedy Technique

Objective: To understand different algorithm design techniques

S.No. Topic Periods

1 Dynamic Programming – Principal of optimality 1

2 1
Coin changing problem
3 1
Warshall’s and Floyd’s algorithm
4 1
Optimal Binary Search Trees
5 1
Multi stage graph
6 1
Knapsack Problem and Memory Functions
7 1
Greedy Technique –
8 1
Dijkstra’s algorithm
9 1
Huffman Trees and codes
10 1
0/1 Knapsack problem

Serial numbers of suggested Textbooks/References/ Teaching Aids Page Numbers

Anany Levitin, ―Introduction to the Design and Analysis of
Algorithms‖, Third Edition, Pearson Education, 2012.
1-10
Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

Date :07.08.2024
Unit No. :IV Unit Title: Iterative Improvement

Objective: Become familiar with the different algorithm design techniques.

S.No. Topic Periods

1 The Simplex Method 2

2 The Maximum-Flow Problem 2

3 The Maximum-Flow Problem example 1

4 2
Maximum Matching in Bipartite Graphs
5 2
The Stable marriage Problem

Serial numbers of suggested Textbooks/References/ Teaching Aids Page Numbers

Anany Levitin, ―Introduction to the Design and Analysis of
Algorithms‖, Third Edition, Pearson Education, 2012.
1-5
Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

Date :07.08.2024
Unit No. :V Unit Title: Coping with the limitations of Algorithm Power

Objective: To Understand the limitations of Algorithm Power

S.No. Topic Periods

1 Lower Bound Arguments 1

2 P,NP, NP Complete and NP Hard problems 1

3 1
Backtracking n-Queens Problem
4 2
Hamiltonian circuit problem- Subset sum problem
5 1
Branch and Bound – LIFO search and FIFO search
6 2
Assignment Problem - Knapsack problem
7 1
Travelling Salesman problem
8 1
Approximation Algorithms for NP – Hard problems
9 1
Travelling Salesman problem – Knapsack problem

Serial numbers of suggested Textbooks/References/ Teaching Aids Page Numbers

Anany Levitin, ―Introduction to the Design and Analysis of
Algorithms‖, Third Edition, Pearson Education, 2012.
1-9
 Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

PRACTICAL EXERCISES:

S.No. Topic Periods

1 Recursive and non-recursive algorithms 4

2 Divide and Conquer 4

3 2
Decrease and Conquer
4 2
Transform and Conquer
5 4
Dynamic programming
6 4
Greedy Technique
7 2
Iterative improvement
8 4
Backtracking
9 4
Branch and Bound
CO’s- PO’s & PSO’s MAPPING
PO PSO’s
CO ’s
’s 1 2 3 4 5 6 7 8 9 10 1 1 1 2 3
1 2
1 3 3 3 1 1 - - - 1 1 2 2 3 2 1
2 2 1 1 3 2 - - - 2 2 1 2 2 2 2
3 3 2 1 2 2 - - - 2 1 1 2 1 3 3
4 3 2 3 2 2 - - - 3 3 3 2 2 1 2
5 3 1 2 3 3 - - - 2 2 2 2 3 1 3
AV 3 2 2 2 2 - - - 2 2 2 2 2 2 2
G
1 - low, 2 - medium, 3 - high, ‘-' - no correlation
Arunai Engineering College Department of Artificial Intelligence And Data Science Format No.F-LP-02

LESSON PLAN
SUBJECT CODE & NAME

AD3351-DESIGN AND ANALYSIS OF ALGORITHMS

Regulation :R2021
Academic Year :2024-2025 (ODD SEMESTER) Semester :III

Prepared by Verified by HOD

AI&DS