Currently Empty: ₹0.00
Gate 2025
Design and Analysis of Algorithms (CST-010) UTU
This course aims to equip students with skills in analyzing and designing algorithms, comparing their efficiencies, and understanding their limitations.
- Intermediate
- 38
- September 22, 2024
- Certificate of completion
About Course
COURSE OUTCOMES: The objectives of this course:
Unit 1- Introduction:
Characteristics of an algorithm, Analysis of algorithm: Asymptotic analysis of complexity bounds – best, average, and worst-case behavior, Sorting techniques and their performance analysis, Time a space trade-off.
Analysis of recursive algorithms through recurrence relations:
Substitution method, Recursion tree method and master’s theorem.
Unit 2- Fundamental Algorithmic Strategies:
Brute-Force, Greedy, Dynamic Programming, Branch- and Bound and Back tracking methodologies for the design of an algorithms, Illustrations of these techniques for Problem-Solving, Knapsack, Matrix Chain Multiplication, Activity selection and LCS Problem.
Unit 3- Graph and Tree Algorithms:
Traversal algorithms: Depth First Search (DFS) and Breadth First Search (BFS), Shortest path algorithms, Minimum Spanning Tree, Topological sorting, Network Flow Algorithm, Binomial Heap and Fibonacci Heap.
Unit 4- Tractable and Intractable Problems:
Computability of Algorithms, Computability classes – P, NP, NP-complete and NP-hard, Standard NP-complete problems and Reduction techniques.
Unit 5- Advanced Topics:
Approximation algorithms and Randomized algorithms, Distributed Hash Table.
Course Content
Unit 1- Introduction
-
Introduction of DESIGN & ANALYSIS.
-
Characteristics of an Algorithm.
-
Analysis of algorithm:
-
Asymptotic analysis of complexity bounds – best, average, and worst-case behavior.
-
Analysis of recursive algorithms through recurrence relations:
-
Substitution method of design & analysis.
-
Recursion tree method
-
Master Theorem
-
Sorting techniques and their performance analysis.
-
Time a space trade-off.
Unit 2- Fundamental Algorithmic Strategies.
Unit 3- Graph and Tree Algorithms.
Unit 4- Tractable and Intractable Problems.
Unit 5- Advanced Topics.
Instructors
No Review Yet
