KTU B.Tech S6 ModelQuestions Computer Science

KTU B.Tech S6 ModelQuestions Computer Science

 

CS302 Design and Analysis of Algorithms	Download
CS304 Compiler Design	Download
CS306 Computer Networks	Download
HS300 Principles of Management	Download
CS364 Mobile Computing[Elective]	Download
CS366 Natural Language Processing[Elective]	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