KTU B.Tech S6 ModelQuestions Computer Science
|
Download |
|
Download |
|
Download |
|
Download |
|
Download |
|
Download |
KTU B.Tech S6 ModelQuestions Computer Science
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