Design and Analysis of Algorithms detailed syllabus for Information Technology (IT) for 2019 regulation curriculum has been taken from the Anna Universities official website and presented for the IT students. For course code, course name, number of credits for a course and other scheme related information, do visit full semester subjects post given below.
For Information Technology 4th Sem scheme and its subjects, do visit IT 4th Sem 2019 regulation scheme. The detailed syllabus of design and analysis of algorithms is as follows.
Course Objective:
For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier.
.
Unit I
Fundamentals
The Role of Algorithms in Computing – Algorithms – Designing Algorithms – Analysing Algorithms – Iterative Algorithms – Step Count – Operation Count – Recursive Algorithms – Recurrence Equations – Substitution Method – Recursion Tree Method – Master Theorem -Proof – Asymptotic Notations – Growth of Functions.
Suggested Activities:
- Discussion on role of algorithms in computer science.
- External learning – Design of simple problems, sample problems in Hackerrank, like, diagonal difference in matrices, staircase construction.
- Computation of step count and operation count for merge sort and Quicksort.
- Design of induction proofs for algorithm verification for recursive algorithms.
- Practical – Implementation of time complexity in Python.
Suggested Evaluation Methods:
- Tutorials on operation count and step count for iterative algorithms such as linear search and array sum.
- Assignments on recursive algorithm analysis and Master Theorem.
- Quizzes on algorithm writing.
Unit II
For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier..
Unit III
Greedy Approach and Matrix Operations
Elements of The Greedy Strategy – Huffman Code – Task Scheduling Problem – Activity Selection – Set Cover and Vertex Cover – Transform and Conquer Approach – Matrix Operations – Solving Systems of Linear Equations – LUP Decomposition – Matrix Inverse and Determinant of a Matrix.
Suggested Activities:
- Flipped classroom on algorithm design.
- External learning – Greedy approach based algorithms like set cover and vertex. cover – Hackerrank problems like Password cracker.
- Computation of step count and operation count of Huffman code.
- Design of greedy based proofs for set cover problems.
- Practical – Implementation of matrix inverse using Gaussian Elimination problem.
Suggested Evaluation Methods:
- Tutorial on Huffman code and task scheduling.
- Assignments on LUP Decomposition and Matrix Inverse using matrix decomposition.
- Quizzes on greedy approach.
Unit IV
For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier..
Unit V
Computational Complexity
Understanding of Computational Complexity – NP-Hard – NP-Completeness – Reducibility -Cook”s Theorem – NP-Completeness Proofs – Probabilistic Analysis and Randomized Algorithms – Quicksort – Approximation Algorithms – Set Cover and Vertex Cover.
Suggested Activities:
- Flipped classroom on computational complexity.
- External learning – NP complexity, Turing machines.
- Computation and derivation of exponential complexity for set cover and vertex cover problems.
- Design of approximation bounds for randomized quicksort.
- Practical – Implementation of approximation algorithm for set cover problem.
Suggested Evaluation Methods:
- Tutorials on NP-complete proofs such as SAT problem.
- Assignments on set cover and vertex cover approximation problems.
- Quizzes on computational complexity.
Course Outcome:
For the complete syllabus, results, class timetable, and many other features kindly download the iStudy App
It is a lightweight, easy to use, no images, and no pdfs platform to make students’s lives easier..
Text Books:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms”, Third Edition, McGraw Hill, 2009.
- S. Sridhar, “Design and Analysis of Algorithms”, Oxford University Press, 2015.
References:
- Steven S. Skiena, “The Algorithm Design Manual”, Second Edition, Springer, 2010.
- Robert Sedgewick, Kevin Wayne, “Algorithms”, Fourth Edition, Pearson Education, 2011.
- Donald E. Knuth, “Art of Computer Programming, Volume I – Fundamental Algorithms”, Third Edition, Addison Wesley, 1997.
For detailed syllabus of all other subjects of Information Technology, 2019 regulation curriculum do visit IT 4th Sem subject syllabuses for 2019 regulation.
For all Information Technology results, visit Anna University IT all semester results direct link.