Design And Analysis Of Algorithms 21CS42
Module 1`
Introduction: What is an Algorithm? It’s Properties. Algorithm Specification-using natural language, using Pseudo code convention, Fundamentals of Algorithmic Problem solving, Analysis Framework-Time efficiency and space efficiency, Worst-case, Best-case and Average case efficiency.
Performance Analysis: Estimating Space complexity and Time complexity of algorithms.
Asymptotic Notations: Big-Oh notation (O), Omega notation (Ω), Theta notation () with examples, Basic efficiency classes, Mathematical analysis of Non-Recursive and Recursive Algorithms with Examples.
Brute force design technique: Selection sort, sequential search, string matching algorithm with complexity Analysis.
Module 2
Divide and Conquer: General method, Recurrence equation for divide and conquer, solving it using Master’s theorem. , Divide and Conquer algorithms and complexity Analysis of Finding the maximum & minimum, Binary search, Merge sort, Quick sort.
Decrease and Conquer Approach: Introduction, Insertion sort, Graph searching algorithms, Topological Sorting. It’s efficiency analysis.
Module 3
Greedy Method: General method, Coin Change Problem, Knapsack Problem, solving Job sequencing with deadlines Problems.
Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm with performance analysis.
Single source shortest paths: Dijkstra’s Algorithm.
Optimal Tree problem: Huffman Trees and Codes.
Transform and Conquer Approach: Introduction, Heaps and Heap Sort.
Module 4
Dynamic Programming: General method with Examples, Multistage Graphs.
Transitive Closure: Warshall’s Algorithm. All Pairs Shortest Paths: Floyd’s Algorithm,
Knapsack problem, Bellman-Ford Algorithm, Travelling Sales Person problem.
Space-Time Tradeoffs: Introduction, Sorting by Counting, Input Enhancement in String Matching-Harspool’s algorithm.
Module 5
Backtracking: General method, solution using back tracking to N-Queens problem, Sum of subsets problem, Graph coloring, Hamiltonian cycles Problems.
Branch and Bound: Assignment Problem, Travelling Sales Person problem, 0/1 Knapsack problem
NP-Complete and NP-Hard problems: Basic concepts, non- deterministic algorithms, P, NP, NP-Complete, and NP-Hard classes.