Bellari, V.V.

Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

Course syllabus

Name of Staff : INDIRA Course Code : 21CS42

Subject / Course : DESIGN AND ANALYSIS OF ALGORITHM Class: IV Semester
Total Number of Lecture Hours : 40 Section : A
Class: IV Semester
Commencement of Semester : 22 /04/2024 Last Working Day :

Course objectives:
This course will enable students to
 To learn the methods for analyzing algorithms and evaluating their performance.
 To demonstrate the efficiency of algorithms using asymptotic notations.
 To solve problems using various algorithm design methods, including brute force, greedy, divide and conquer,
decrease and conquer, transform and conquer, dynamic programming, backtracking, and branch and bound.
● To learn the concepts of P and NP complexity classes.
Module # Topics RBT Level
INTRODUCTION: What is an Algorithm?, Fundamentals of Algorithmic
Problem Solving. FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM
EFFICIENCY: Analysis Framework, Asymptotic Notations and Basic
Module-1 Efficiency Classes, Mathematical Analysis of Non recursive Algorithms,
L1,L2
Mathematical Analysis of Recursive Algorithms. BRUTE FORCE
APPROACHES: Selection Sort and Bubble Sort, Sequential Search and
Brute Force String Matching.
BRUTE FORCE APPROACHES (contd..): Exhaustive Search (Travelling
Salesman probem and Knapsack Problem). DECREASE-AND-CONQUER:
Module-2 Insertion Sort, Topological Sorting. DIVIDE AND CONQUER: Merge Sort,
Quick Sort, Binary Tree Traversals, Multiplication of Large Integers and L2, L3, L4, L5,
Strassen’s Matrix Multiplication.
TRANSFORM-AND-CONQUER: Balanced Search Trees, Heaps and
Heapsort. SPACE-TIME TRADEOFFS: Sorting by Counting: Comparison
Module-3
counting sort, Input Enhancement in String Matching: Horspool’s L2, L3, L4, L5,
Algorithm
DYNAMIC PROGRAMMING: Three basic examples, The Knapsack Problem
and Memory Functions, Warshall’s and Floyd’s Algorithms. THE GREEDY
Module-4
METHOD: Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm, L2, L3, L4, L5,
Huffman Trees and Codes.
LIMITATIONS OF ALGORITHMIC POWER: Decision Trees, P, NP, and NP- L2, L3, L4, L5,
Complete Problems. COPING WITH LIMITATIONS OF ALGORITHMIC
Module-5 POWER: Backtracking (n-Queens problem, Subset-sum problem), Branch-
and-Bound (Knapsack problem), Approximation algorithms for NP-Hard
problems (Knapsack problem).

Course Outcomes:
Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

After studying this course, students will be able to:

Apply asymptotic notational method to analyze the performance of the algorithms in
22CS201.1 terms of time complexity

22CS201.2 Demonstrate divide & conquer approaches and decrease & conquer approaches to
solve computational problems.

22CS201.3 Make use of transform & conquer and dynamic programming design approaches to
solve the given real world or complex computational problems.

22CS201.4 Apply greedy and input enhancement methods to solve graph & string based
computational problems

22CS201.5 Analyse various classes (P,NP and NP Complete) of problems

22CS201.6 Illustrate backtracking, branch & bound and approximation methods.

.
Text Books:
T1. Introduction to the Design and Analysis of Algorithms, By Anany Levitin, 3rd Edition (Indian), 2017, Pearson
Reference Books:
1. Computer Algorithms/C++, Ellis Horowitz, SatrajSahni and Rajasekaran, 2nd Edition, 2014, Universities Press.
2. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein, 3rd Edition, PHI.
3. Design and Analysis of Algorithms, S. Sridhar, Oxford (Higher Education)

Web links and Video Lectures (e-Resources):

● Design and Analysis of Algorithms: https://nptel.ac.in/courses/106/101/106101060/
Activity Based Learning (Suggested Activities in Class)/ Practical Based learning
● Promote real-world problem-solving and competitive problem solving through group discussions to engage students
actively in the learning process.
● Encourage students to enhance their problem-solving skills by implementing algorithms and solutions through
programming exercises, fostering practical application of theoretical concepts. Assessment Methods - 1. Problem Solving
Assignments (Hacker Rank/ Hacker Earth / Leadcode) 2. Gate Based Aptitude Test
Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

RBT and Learning Levels

Revised Bloom’s
Level of Learning Action Verbs
Taxonomy
Choose, Describe, Define, Identify, Label, List, Locate, Match,
Level 1 Memorize, Name, Omit, Recite, Select, State, Count, Draw, Remember
Outline, Point, Quote, Read, Recall, Recognize, Repeat,
Reproduce
Classify, Defend, Demonstrate, Distinguish, Explain, Express,
Extend, Give, Examples, Illustrate, Indicate, Interrelate, Interpret,
Level 2 Infer, Judge, Match, Paraphrase, Represent, Restate, Rewrite, Understand
Select, Show, Summarize, Tell, Translate, Associate, Compute,
Convert, Discuss, Estimate, Extrapolate, Generalize, Predict
Apply, Choose, Dramatize, Explain, Generalize, Judge, Organize,
Paint, Prepare, Produce, Select, Show, Sketch, Solve, Use, Add,
Level 3 Calculate, Change, Classify, Complete, Compute, Discover, Apply
Divide, Examine, Graph, Interpolate, Manipulate, Modify,
Operate, Subtract, Use
Analyze, Categorize, Classify, Compare, Differentiate,
Distinguish, Identify, Infer, Select, Subdivide, Survey, Arrange,
Level 4 Breakdown, Combine, Design, Detect, Diagram, Develop, Analyse
Discriminate, Illustrate, Outline, Relate, Point out, Separate,
Utilize
Appraise, Judge, Criticize, Defend, Compare, Assess, Conclude,
Level 5 Contrast, Critique, Determine, Grade, Justify, Measure, Rank, Evaluate
Rate, Support, Test
Choose, Combine, Compose, Construct, Create, Design,
Develop, Do, Formulate, Hypothesize, Invent, Make, Originate,
Level 6 Organize, Plan, Produce, Role Play, Tell, Compile, Drive, Create
Devise, Explain, Generate, Group, Integrate, Prescribe, Propose,
Rearrange, Reconstruct, Reorganize, Revise, Rewrite, Transform
Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

Ref No.: PDIT/Branch/Course Plan/ sem/Course name/Academic year

LESSON PLAN
Department: Computer Science And Engineering
Academic Year: 2023-2024

Semester : IV
Branch : Computer Science And Engineering
Course : Computer science
Course Code : CS
Faculty Name : INDIRA
Designation : Assistant Professor

Faculty Course-coordinator H.O.D

Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

Periodic Lesson Plan

Date of Tools Used
Sl. COs Resources
Handling Time Topics to be covered
No. BB PPT Video Activity
Class
Introduction:
1. 
What is an Algorithm?, 
Fundamentals of
2.
Algorithmic Problem
Solving
FUNDAMENTALS 
OF THE ANALYSIS
OF ALGORITHM
3.
EFFICIENCY:
Analysis
Framework,
Asymptotic Notations 
4. and Basic Efficiency
Classes,
Mathematical Analysis 
5. of Non recursive
Algorithms,
Mathematical Analysis 
6. of Recursive Algorithms.

Selection Sort and 

7.
Bubble Sort,
Sequential Search and 
8. Brute Force String
Matching
Exhaustive Search 
(Travelling Salesman
9.
probem and Knapsack
Problem).
Decrease and Conquer 
Approach:
10.
Introduction, Insertion
sort,
Graph searching 
11. algorithms, Topological
Sorting. It’s efficiency
analysis.
Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

Recurrence equation for 

12. divide and conquer

solving it using 
13.
Master’s theorem. ,
Divide and Conquer 
14. algorithms and
complexity
Analysis of Finding the 
15.
maximum & minimum,
Binary search, 
16.
Merge sort, 
17.
Quick sort. 
18.
Greedy Method: Merge 
19.
Sort
Binary Tree 
20.
Traversals,
Multiplication of Large 
21. Integers and Strassen’s
Matrix Multiplication
TRANSFORM-AND- 
22. CONQUER: Balanced
Search Trees,
Heaps and Heapsort 
23.
SPACE-TIME 
24. TRADEOFFS: Sorting by
Counting
Comparison counting 
25.
sort
Input Enhancement in 
26. String Matching:
Horspool’s Algorithm.
DYNAMIC 
PROGRAMMING:
27.
Three basic
examples,
The Knapsack 
28. Problem and
Memory
Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

The Knapsack Problem 

29.
and Memory
Warshall’s Algorithms 
30.

31. Floyd’s Algorithms
THE GREEDY METHOD: 
32.
Prim’s Algorithm,
Kruskal’s Algorithm, 
33.
Dijkstra’s Algorithm, 
34.

35. Huffman Trees and
Codes

LIMITATIONS OF
36. ALGORITHMIC POWER:
Decision Trees
, P, NP, and NP- 
37.
Complete Problems.
Backtracking (n-Queens 
38. problem, Subset-sum
problem),

39. Branch-and-Bound :
Knapsack problem

Approximation
40. algorithms for NP-Hard
problems (Knapsack
problem). .

41.

42.

Signature of faculty Course coordinator Signature of H O D

Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering
Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

Moderately mapped as students learn to demonstrate proficiency in writing simple programs involving branching
and looping structures. This can be used to providesolutions for various engineering problems.PO2

2 Moderately mapped as students learn to analyze and exhibit proficiency in writingsimple programs involving branching
and looping structures.PO3

1Slightly mapped as students use the proficiency in writing simple programs involving branching and looping structures in
designing and development of many software problems.PO4

1Slightly mapped as the students conduct complex analysis in demonstrating proficiency in writing simple programs
involving branching and looping structures.PO5

1Slightly mapped as students use modern tools in demonstrating proficiency in writingsimple programs involving branching
and looping structures.PO12

1Slightly mapped as the student use skills in demonstrating proficiency in writingsimple programs involving branching and
looping structures in lifelong to representtheir work.PSO1

3 Strongly mapped because students will apply Java basics in the field of coding.PSO2 1 Slightly mapped as the students wil
l apply Java basics to build network applications.
CO No. PO/PSO CL Justification
Moderately mapped as students learn to demonstrate proficiency in writing
simple programs involving branching and looping structures. This can be used to
providesolutions for various engineering problems.

https://www.scribd.com/document/721980320/BCS306A-Justification-CSE
Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering
Bellari, V.V. Sangha’s
PROUDHADEVARAYA INSTITUTE OF TECHNOLOGY
T. B. DAM, HOSAPETE – 583 225
(Affiliated to VTU, Belagavi, Karnataka & Recognized by AICTE, New Delhi)
Department of COMPUTER SCEINCE AND Engineering

Moderately mapped as students learn to demonstrate proficiency in writing simple programs involving branching and looping
structures. This can be used to providesolutions for various engineering problems