L T P C

IT23C01 DESIGN AND ANALYSIS OF ALGORITHMS

3 0 0 3
COURSE OBJECTIVES:
● To learn about the process of problem solving.
● To be conversant with algorithms for common problems.
● To analyse the algorithms for time/space complexity.
● To learn to write algorithms for a given problem using different design paradigms.
● To understand computational complexity of problems
UNIT I FUNDAMENTALS 9
The Role of Algorithms in Computing – Designing Algorithms – Algorithmic Thinking – Fundamental
stages of Problem-solving - Analyzing Algorithms – Iterative Algorithms - Step Count and Operation
Count— measuring of Input size, Measuring Run time – Best, worst and average case complexity – Rate
of growth - Recursive Algorithms: Formulation and solving recurrence equations – Guess and Verify
method – Substitution method - Asymptotic analysis – asymptotic Notations – Asymptotic complexity
classes.
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:
● Assignments on recursive algorithm analysis and Master Theorem.
● Quizzes on algorithm writing.
UNIT II DIVIDE AND CONQUER AND ITS VARIANTS 9
Introduction to Divide and Conquer - Merge Sort – Quicksort - Long Integer Multiplication – Divide and
Conquer recurrences - Recursion Tree Method – Master Theorem –- Transform and Conquer Approach:
Gaussian Elimination Method – LU and LUP Decomposition – Solving set of equations using LUP – Matrix
Inverse and Determinant using LUP approach - Decrease and Conquer Paradigm - Binary Search and
Insertion Sort.
Suggested Activities:
● External learning - Divide and conquer based algorithms, Hackerrank divide and
conquer algorithms.
● External learning - Dynamic programming based algorithms like coin change.
● Computation of step count and operation count.
● Design of Induction Proofs for algorithm verification.
● Practical - Implementation of Merge sort and Longest Common Sequence like Spell
● Checker, Hackerrank problems like coin change.
Suggested Evaluation Methods:
● Assignment on matrix chain multiplication and longest common sequence.
● Assignments on string edit and string basics.
● Quizzes on algorithm design.
UNIT III GREEDY ALGORITHMS AND DYNAMIC PROGRAMMING APPROACH 9
Greedy Strategy—Generic Greedy Algorithm—Activity Selection—Fractional Knapsack—Dynamic
Programming—Elements of Dynamic Programming—Principle of Optimizity—Computing Binominal
Coefficient—Matrix Chain Multiplication—Longest Common Subsequence—String Edit—Solving
Knapsack problem using dynamic programming approach.
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:
● Assignment on Huffman code and task scheduling.
● Assignments on LUP Decomposition and Matrix Inverse using matrix decomposition.
● Quizzes on greedy approach.
UNIT IV INCREMENTAL APPROACH, BACKTRACKING AND BRANCH & BOUND 9
Linear Programming: Formulation of LPPs – Iterative development – Applications of Linear Programming
- Standard form – Simple solution using Graph techniques - Simplex Algorithm – Maximization and
Minimization of problems - Duality - Backtracking: Basics of Backtracking- 8-queen - Sum of Subsets,
Branch and Bound: Least cost with Branch and Bound - 0/1 Knapsack.
Suggested Activities:
● Flipped classroom on Linear Algebra, Linear Programming basics
● External learning - Problems like Diet Problem in Hackerrank.
● Formulation of Duality for simple Linear Programming problems like Diet Problem.
● Practical - Implementation of Simplex algorithm.
Suggested Evaluation Methods:
● Tutorials on linear programming.
● Assignments in duality and linear programming problem formulations.
● Quizzes on linear programming
UNIT V COMPUTATIONAL COMPLEXITY 9
Understanding of Computational Complexity – Solvability - Tractability - Decision Problems - Decidability
- NP-Hard – NP-Completeness – Reducibility Satisfiability Problem and Cook’s Theorem - NP-
Completeness Proofs for problems like SAT - 3CNF - Clique – Overview of Randomized Algorithm –
Randomized Quicksort – Overview of approximation algorithm – set 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
TOTAL: 45 PERIODS
COURSE OUTCOMES:
Upon successful completion of the course, the student will be able to:
CO 1. Analyze algorithms based on time and space complexity
CO 2. Design efficient Divide and conquer and its variants for solving problems.
 CO 3. Apply greedy methods and dynamic programming strategies for solving real- world problems.
CO 4. Design and implement Linear programming, backtracking, and branch and bound techniques
towards efficient problem-solving.
CO 5. Understand the computational theory and the methods to prove NP-complete
problems.
TEXTBOOKS:
1. Thomas H Cormen, Charles E Leiserson, Ronald L Revest, Clifford Stein, “Introduction to Algorithms”
4th Edition, The MIT Press Cambridge, Massachusetts London, England, 2022.
2. S.Sridhar, “Design and Analysis of Algorithms”, Second Edition, Oxford University Press, 2024.
3. Antany Levitin, “Introduction to the Design and Analysis of Algorithms”, Third Edition,
Pearson Education, 2012.
REFERENCES:
1. Steven S. Skiena, “The Algorithm Design Manual”, Second Edition, Springer, 2010.
2. 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.

Program Outcomes (POs) & Program Specific Outcomes (PSOs)

COURSE
OUTCOMES PO PO PO PO PO PO PO PO PO PO PO PO PSO PSO PSO
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
CO1 3 3 2 2 1 - - - - - - 3 3 3 3
CO2 3 2 3 2 1 - - - - - - 3 3 3 3
CO3 3 3 2 2 1 - - - - - - 3 3 3 3
CO4 3 2 3 2 1 - - - - - - 3 3 3 3
CO5 3 3 2 2 1 - - - - - - 3 3 3 3
CO6 3 2.6 2.4 2 1 - - - - - - 3 3 3 3
AVG 3 3 2 2 1 - - - - - - 3 3 3 3
1-low, 2-medium, 3-high, ‘-“- no correlation