Home / KTU B.Tech S6 Syllabus for all branches

# KTU B.Tech S6 Syllabus for all branches

## KTU B.Tech S6 Syllabus Computer Science

CS 302: Design and Analysis of Algorithms

MODULE I

Introduction to Algorithm AnalysisTime and Space Complexity- Elementary operations and Computation of Time Complexity- Best, worst and Average Case Complexities- Complexity Calculation 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, Red-Black Trees insertion and deletion (Techniques only; algorithms not expected). B-Trees – insertion and deletion operations. Sets- Union and find operations on disjoint sets.

FIRST INTERNAL EXAMINATION

MODULE III

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, Bellman-Ford 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.

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 NP-Complete 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 NP-Complete Classes