This course is part of the B.E. Computer Science Engineering curriculum under Anna University Regulation 2021. The knowledge from this course continues to be actively applied in professional software development.
Semester 4 (Second Year)
4 Credits
60 Lecture Hours
Course Overview
UniversityAnna University
Regulation2021
Semester4
Credits4
TypeCore
Units5
Course Objectives
1
To analyze the efficiency of algorithms
2
To apply graph algorithms
3
To understand divide and conquer, dynamic programming, and greedy techniques
4
To use the state space tree method
5
To solve problems using approximation and randomized algorithms
Syllabus
Detailed unit-wise breakdown of the course curriculum as per Anna University Regulation 2021.
1
INTRODUCTION
12 Hours
Algorithm analysisTime and space complexityAsymptotic notationsBest, worst, and average case analysisRecurrence relationSubstitution methodLower boundsLinear and Binary SearchInterpolation SearchPattern search – Naive string-matchingRabin-Karp algorithmKnuth-Morris-Pratt algorithmInsertion sort and Heap sort
Divide and Conquer – Finding max and minMerge sortQuick sortDynamic programming – Matrix-chain multiplicationMulti stage graphOptimal Binary Search TreesGreedy Technique – Activity-selection problemOptimal Merge patternHuffman Trees
4
STATE SPACE SEARCH ALGORITHMS
12 Hours
Backtracking – N-Queens problemSum of subsetsGraph coloringHamiltonian circuitsBranch and Bound – Assignment problemTravelling Salesman Problem0/1 Knapsack problemA* algorithm
5
NP-COMPLETE AND APPROXIMATION ALGORITHMS
12 Hours
Tractable and intractable problemsPolynomial time algorithmsNP-hardness and NP-completenessBin Packing problemProblem reductionTSP and 3-CNF problemApproximation algorithmsRandomized algorithmsPrimality testingRandomized quick sort
Course Outcomes
Upon completion of this course, students will be able to:
CO1
Analyze the efficiency of algorithms using various frameworks
CO2
Apply graph algorithms to solve problems
CO3
Use divide and conquer, dynamic programming, and greedy techniques
CO4
Employ state space tree methods for problem solving
CO5
Solve problems using approximation and randomized algorithms
Industry Application & Relevance
How the concepts learned in this course are applied in real-world software development projects across Banking, Healthcare, and Enterprise domains over 20+ years of experience.
Professional Application
Optimization, system design, performance tuning
Textbooks & References
Textbooks
Thomas H. Cormen et al., 'Introduction to Algorithms', MIT Press
Anany Levitin, 'Introduction to the Design and Analysis of Algorithms', Pearson
Reference Books
S. Dasgupta et al., 'Algorithms', McGraw Hill
Jon Kleinberg, Eva Tardos, 'Algorithm Design', Pearson
Related Courses from Semester 4
Other courses from the same semester that are actively used in professional work.