Teaching Scheme

Course Course Credits Assigned

(Contact Hours)
Code Name
Theory Pract. Tut. Theory Pract. Tut. Total
Analysis of - - - -
2113113 2 2 2
Algorithm - - - -

Theory Term Pract Total

work /
Internal Assessment End Exam Oral
Course
Course Name Test 1 Test IAT-I Sem Duration
Code
2 + Exam (in Hrs)
IAT-II
(Total)
Analysis of
2113113 20 20 40 60 2 -- -- 100
Algorithm

Course Objectives:
1. To provide mathematical approaches for Analysis of Algorithms
2. To understand and solve problems using various algorithmic approaches
3. To analyze algorithms using various methods

Course Outcomes:
1. Evaluate the time and space complexity of algorithms.
2. Implement the Divide and Conquer strategy and assess its complexity.
3. Utilize the Greedy algorithm approach and determine its efficiency.
4. Develop solutions using Dynamic Programming and examine its complexity.
5. Employ Backtracking and Branch and Bound techniques.
6. Apply String Matching algorithms for pattern searching

Prerequisite: Data structure concepts

DETAILED SYLLABUS:

Sr. CO
Name of Module Detailed Content Hours
No. Mapping
Performance analysis- Master Method, space,
and time complexity Growth of function, Big-
Oh, Omega Theta notation Mathematical
I Introduction background for algorithm analysis. Analysis of 4 CO1
selection sort, insertion sort.
Self-learning Topics: Complexity class:
Definition of P, NP, NP-Hard, NP-Complete
General method, Merge sort, Quick sort,
Analysis of Binary search.
Divide and Conquer Self-learning Topics: Finding minimum and
II 5 CO2
Approach maximum algorithms and their Analysis,
Strassen's Algorithm, real life applications of all
algorithms
General Method, Single source shortest path:
Dijkstra AlgorithmFractional Knapsack problem,
Minimum cost spanning trees: Kruskal and Prim’s
Greedy Method algorithms
III 5 CO3
Approach
Self-learning Topics: Job sequencing with
deadlines, real life applications of all algorithms
 General Method, Multistage graphs, All pair
shortest path: Floyd Warshall Algorithm, 0/1
Dynamic knapsack Problem, Travelling Salesperson
IV Programming problem, Longest common subsequence. 8 CO4
Approach
Self-learning Topics: Bellman Ford Algorithm,
real life applications of all algorithms
General Method, Backtracking: N-queen
problem, Sum of subsets,Graph coloring.
Branch and Bound: Travelling Salesperson
Backtracking and
V Problem, 15 Puzzle problem 7 CO1
Branch and bound
Self-learning Topics: Real life applications of
all algorithms
The Naïve string-matching algorithm, The Rabin
Karp algorithm, The Knuth-Morris-Pratt
String Matching algorithm
VI 3 CO2
Algorithms
Self-learning Topics: Real life applications of
all algorithms

Text Books:
1. T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms”, 2nd
Edition, PHI Publication 2005
2. Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals of computer algorithms”
University Press.
Reference Books:
1. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, “Algorithms”, Tata McGraw- Hill
Edition.
2. S. K. Basu, “Design Methods and Analysis of Algorithm”, PHI
Online References:
Sr. No. Website Name
1. https://nptel.ac.in/courses/106/106/106106131/
2. https://swayam.gov.in/nd1_noc19_cs47/preview
3. https://www.coursera.org/specializations/algorithms

4. https://www.mooc-list.com/tags/algorithms

Assessment:
• Internal Assessment (IA) for 40 marks:

IA will consist of Two Compulsory Internal Assessment Tests. Approximately 40% to

50% of syllabus content must be covered in First IA Test and remaining 40% to 50% of
syllabus content must be covered in Second IA Test
End Semester Examination for 60 Marks:
Question paper format:
• Question Paper will comprise of a total of six questions each carrying 20 marks Q.1 will be
compulsory and should cover maximum contents of the syllabus

• Remaining questions will be mixed in nature (part (a) and part (b) of each question must be from
different modules. For example, if Q.2 has part (a) from Module 3 then part (b) must be from any other
Module randomly selected from all the modules)

• A total of Three questions needs to be answered.