#### 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.