Design and Analysis of Algorithms (PCC-CS404)
5 units: Introduction, Fundamental Algorithmic Strategies, Graph and Tree Algorithms, Tractable and Intractable Problems, Advanced Topics · L-T-P 3L/week.
Detailed syllabus
Unit 1: Introduction (8 hours)
Introduction: Characteristics of algorithm. Analysis of algorithm: Asymptotic analysis of complexity bounds – best, average and worst-case behavior; Performance measurements of Algorithm, Time and space trade-offs, Analysis of recursive algorithms through recurrence relations: Substitution method, Recursion tree method and Masters’ theorem.
Unit 2: Fundamental Algorithmic Strategies (8 hours)
Fundamental Algorithmic Strategies: Brute-Force, Greedy, Dynamic Programming, Branch and- Bound and Backtracking methodologies for the design of algorithms; Illustrations of these techniques for Problem-Solving, Bin Packing, Knap Sack TSP. Heuristics –characteristics and their application domains.
Unit 3: Graph and Tree Algorithms (6 hours)
Graph and Tree Algorithms: Traversal algorithms: Depth First Search (DFS) and Breadth First Search (BFS); Shortest path algorithms, Transitive closure, Minimum Spanning Tree, Topological sorting, Network Flow Algorithm.
Unit 4: Tractable and Intractable Problems (10 hours)
Tractable and Intractable Problems: Computability of Algorithms, Computability classes – P,NP, NP- complete and NP-hard. Cook’s theorem, Standard NP-complete problems and Reduction techniques.
Unit 5: Advanced Topics (6 hours)
Advanced Topics: Approximation algorithms, Randomized algorithms, Class of problems beyond NP – P SPACE
Source: official document