CS 2209- DESIGN & ANALYSIS OF ALGORITHM
Module ModuleName L S/T AS IS P Credits
Code
CS 2209 Design & Analysis of Algorithm 60 - 15 15 9
PRE-REQUISITE:
Knowledge ofC Programming and Data structure is needed
COURSE AIM:
The course aims to provide the students to acquire the ability of applying various algorithmic
concepts for all domains and efficient interpretation of real life problems
COURSE EXPECTED LEARNING OUTCOMES:
At the end of the course the learner will be able to
Propose the correct algorithmic strategy to solve anyproblem;
Write algorithms for any problem based on thestrategy;
Analyze any given algorithm and express its complexity in asymptoticnotation;
Identify any problem as belonging to the class of P, NP-Complete orNP-Hard;
Propose approximation algorithm for any NPproblem.
COURSE STATUS : Core Module
CREDIT RATING : 9
TOTAL HOURS SPENT : 90
Course Content:
Unit I Basic Concepts of Algorithms:
Introduction – Notion of Algorithm – Fundamentals of Algorithmic Solving – Important
Problem types – Fundamentals of the Analysis of Algorithm Efficiency - Analysis
Framework–Asymptotic Notations and Basic Efficiency Classes.
Unit II Mathematical Aspects and Analysis of Algorithms:
Mathematical Analysis of Non-recursive Algorithm – Mathematical Analysis of Recursive
Algorithm – Example: Fibonacci Numbers – Empirical Analysis of Algorithms – Algorithm
Visualization. Practical: Mathematical Analysis of Recursive Algorithm
Unit III Analysis of Sorting and Searching Algorithms:
Brute Force – Selection Sort and Bubble Sort – Sequential Search and Brute-force string
matching – Divide and conquer – Merge sort – Quick Sort – Binary Search – Binary tree-
Traversal and Related Properties – Decrease and Conquer – Insertion Sort – Depth first Search
and Breadth First Search. Practical:Sorting
Unit IV Algorithmic Techniques:
Transform and conquer – Presorting – Balanced Search trees – AVL Trees – Heaps and Heap
sort – Dynamic Programming – Warshall’s and Floyd’s Algorithm – Optimal Binary Search
trees – Knapsack problem and memory functions - Greedy Techniques – Prim’s Algorithm –
Kruskal’s Algorithm – Dijkstra’s Algorithm – Huffman trees. Practical: Trees
Unit V Algorithm Design Methods:
Backtracking – n-Queen’s Problem – Hamiltonian Circuit problem – Subset-Sum problem –
Branch and bound – Assignment problem – Knapsack problem – Traveling salesman
problem– NP and NP-Complete problems – Approximation Algorithms for NP – Hard
Problems. Practical: Knapsack problem
ASSESSMENT METHODS:
Assignments : 20 %
Practical : -
Continuous assessment test 1 : 10 %
Continuous assessment test 2 : 10 %
End of semester examination : 60 %
Total : 100 %
PrescribedTextbooks:
1. Sridhar S, 2015, Design and Analysis of Algorithms, Oxford University Press, New Delhi.
2. Thomas H Cormen, Charles E Leiserson, Ronald L Revest, Clifford Stein, 2014,
Introduction to Algorithms, 3rd Edition, The MIT Press Cambridge, Massachusetts
London,England.
3. Anany Levitin, 2013, Introduction to the Design and Analysis of Algorithm, 3rd Edition,
Pearson EducationIndia.
4. Cormen T.H, Leiserson C.E, Rivest R.L and Stein C, 2012, Introduction to Algorithms,
PHI Learning Private Limited, NewDelhi.
5. Ellis Horowitz, Sartajsahni, Sanguthevar, Rajesekaran, 2010, Fundamentals of Computer
Algorithms, Galgotia Publication Pvt. Ltd., NewDelhi.
ReferenceMaterials:
1. Rajesh K Shukla, 2015, Analysis and Design of Algorithms-A Beginner’s Approach,
Wiley publisher, NewDelhi.
2. Kenneth A. Berman and Jerome L. Paul, 2010, Algorithms, Cengage LearningIndia.
3. Weiss M.A, 2013, Data Structures and Algorithm Analysis in C, 4th Edition, Pearson
Education.
4. Sara Baase and Allen Van Gelder, 2010, Computer Algorithms - Introduction to Design
and Analysis, 2nd Impression, Pearson Education India, NewDelhi.
5. Donald E. Knuth, 2010, The Art of Computer Programming, Volumes 1& 3, Pearson
Education.