Course Code: XXX Design & Analysis of Algorithms L T P C
Version No. XXX Date of Approval: XXX 3 0 2 4
Prerequisite/Exposure Data Structures and Algorithms
Co-requisites
Course Objectives
1. To know the importance of the complexity of a given algorithm.
2. To study various algorithmic design techniques.
3. To utilize data structures and/or algorithmic design techniques in solving new
problems.
4. To know and understand basic computability concepts and the complexity classes P,
NP, and NP-Complete.
Course Outcomes
At the end of the course, students will be able to:
1. Analyze the complexity of the algorithms and use technique divide and conquer to solve
the problems
2. Identify feasible solutions for different problems through greedy method and minimize
the solutions space and to solve the problems through dynamic programming.
3. Solve the problems through graph algorithms.
4. Justify that a certain problem is NP-Complete
5. Understand and apply linear programming concepts to real time applications.
Course Description:
The primary objective of this course is to introduce the topic of algorithms as a precise
mathematical concept, and study how to design algorithms, establish their correctness,
study their efficiency and memory needs. The course consists of a strong mathematical
component in addition to the design of various algorithms.
Text Books:
1. Micheal T. Goodrich and Roberto Tamassia: Algorithm Design: Foundations,
Analysis and Internet examples (John Wiley &Sons, Inc., 2002).
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran. Fundamentalas of Computer
Algorithms Algorithms, MIT Press, Second Edition (Indian reprint: Prentice-Hall),
2008.
Reference Books:
1. Thomas H. Coreman, Charles E. Leiserson and Ronald L. Rivest, “Introduction to
Algorithms”, The MIT Press, 3rd edition, 2009.
2. RCT Lee, SS Tseng, RC Chang and YT Tsai, “Introduction to the Design and Analysis
of Algorithms”, Mc Graw Hill, 2005.
3. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms” Pearson
Education, 2008.
Course Contents
Unit I: Introduction 9 lecture hours
Introduction : Algorithms, Analyzing algorithms, Complexity of algorithms, Growth of
functions, Performance measurements, Sorting and order Statistics - Shell sort, Quick sort,
Merge sort, Heap sort, Comparison of sorting algorithms, Sorting in linear time.
Unit II: Tree 9 lecture hours
Advanced Data Structures: Red-Black trees, B – trees, Binomial Heaps, Fibonacci Heaps.
Unit III: Algorithm 9 lecture hours
Divide and Conquer with examples such as Sorting, Matrix Multiplication, Convex hull and
Searching. Greedy methods with examples Huffman Coding, Knapsack, Minimum Spanning
trees – Prim’s and Kruskal’s algorithms, Single source shortest paths - Dijkstra’s and
Bellman Ford algorithms.
Unit IV: Dynamic Programming 9 lecture hours
Dynamic programming with examples such as Knapsack, All pair shortest paths – Warshal’s
andFloyd’s algorithms, Resource allocation problem. Backtracking, Branch and Bound with
examples such as Travelling Salesman Problem, Graph Coloring, n-Queen Problem,
Hamiltonian Cycles and Sum of subsets.
Unit V: Computations 9 lecture hours
Selected Topics: Algebraic Computation, String Matching, Theory of NP-completeness,
Approximation algorithms and Randomized algorithms.
Mode of Evaluation: Class Quiz, Assignment, CAT -1, CAT – 2 and ETE.
Theory
Components Internal (50) ETE
Assignment
Cat-2 Semester End
Quiz (15)
Marks Cat-1 (15)
(15) Exam (50)
(5)
Total Marks 100
Relationship between the Course Outcomes (COs) and Program Outcomes (POs)
Mapping between Cos and Pos
Mapped Program
Sl. No. Course Outcomes (COs)
Outcomes
Analyze the complexity of the algorithms and
use technique divide and conquer to solve the
1 problems PO1,PO10
Identify feasible solutions for different
problems through greedy method and
2 minimize the solutions space and to solve the PO2,PO3,PO4,PSO1
problems through dynamic programming.
Solve the problems through graph algorithms. PO2
3
PO3,PO4,PO10,PSO1,PSO2
Justify that a certain problem is NP-Complete PO1, PO2, PO4, PO9,
4
PO10, PSO1,PSO2
Understand and apply linear programming
5 concepts to real time applications PO1,PO10,PSO1
