KTU B.Tech S6 Lecture notes Design & Analysis 0f Algorithms
KTU B.Tech S6 Lecture notes – CS302 Design and Analysis of Algorithms
MODULE I

Introduction to Algorithm AnalysisTime and Space ComplexityElementary operations and Computation of Time ComplexityBest, worst and Average Case Complexities ComplexityCalculation of simple algorithms

Recurrence Equations:Solution of Recurrence Equations –Iteration Method and Recursion Tree Methods
MODULE II

Master’s Theorem(Proof not required) – examples

Asymptotic Notations and their properties Application of Asymptotic Notations in Algorithm Analysis Common Complexity Functions

AVL Trees – rotations, RedBlack Trees insertion and deletion (Techniques only; algorithms not expected).

BTrees – insertion and deletion operations.

Sets Union and find operations on disjoint sets.
MODULE III
Graphs – DFS and BFS traversals, complexity, Spanning trees – Minimum Cost Spanning Trees, single source shortest path algorithms, Topological sorting, strongly connected components.Graphs – DFS and BFS traversals, complexity, Spanning trees – Minimum Cost Spanning Trees, single source shortest path algorithms, Topological sorting, strongly connected components.
MODULE IV
Divide and Conquer:The Control Abstraction, 2 way Merge sort, Strassen’s Matrix Multiplication, Analysis Dynamic Programming : The control Abstraction The Optimality Principle Optimal matrix multiplication, BellmanFord Algorithm.
Divide and Conquer:The Control Abstraction, 2 way Merge sort, Strassen’s Matrix Multiplication, Analysis Dynamic Programming : The control Abstraction The Optimality Principle Optimal matrix multiplication, BellmanFord Algorithm
MODULE V
Analysis, Comparison of Divide and Conquer and Dynamic Programming strategies
Greedy Strategy: – The Control Abstraction the Fractional Knapsack Problem,
Minimal Cost Spanning Tree Computation Prim’s Algorithm – Kruskal’s Algorithm.
Analysis, Comparison of Divide and Conquer and Dynamic Programming strategies
Greedy Strategy: – The Control Abstraction the Fractional Knapsack Problem,
Minimal Cost Spanning Tree Computation Prim’s Algorithm – Kruskal’s Algorithm.
MODULE VI
Back Tracking: The Control Abstraction – The N Queen’s
Problem, 0/1 Knapsack Problem Branch and Bound:Travelling Salesman Problem. Introduction to Complexity Theory :Tractable and Intractable Problems The P and NP Classes Polynomial Time Reductions – The NP Hard and NPComplete Classes
Back Tracking: The Control Abstraction – The N Queen’s
Problem, 0/1 Knapsack Problem Branch and Bound:Travelling Salesman Problem. Introduction to Complexity Theory :Tractable and Intractable Problems The P and NP Classes Polynomial Time Reductions – The NP Hard and NPComplete Classes
KTU B.Tech S6 Lecture notes Design and Analysis 0f Algorithms