MG University S6 Computer Science & Engineering B.tech Syllabus
Module 1 Introduction and Complexity
What is an algorithm – Properties of an Algorithm, Difference between Algorithm, Computational Procedure and Program, Study of Algorithms; Pseudo-code Conventions; Recursive Algorithms –Space and Time Complexity –Asymptotic Notations – ‘Oh’, ‘Omega’, ‘Theta’, Common Complexity Functions; Recurrence Relations and Recurrence Trees for Complexity Calculations; Profiling. –Deterministic and non – deterministic algorithms.
What is an algorithm – Properties of an Algorithm, Difference between Algorithm, Computational Procedure and Program, Study of Algorithms; Pseudo-code Conventions; Recursive Algorithms –Space and Time Complexity –Asymptotic Notations – ‘Oh’, ‘Omega’, ‘Theta’, Common Complexity Functions; Recurrence Relations and Recurrence Trees for Complexity Calculations; Profiling. –Deterministic and non – deterministic algorithms.
Module 2 Divide and Conquer
Control Abstraction, Finding Maximum and Minimum, Binary Search, Divide and Conquer Matrix Multiplication, Stressen’s Matrix Multiplication, Merge Sort, Quick Sort.
Control Abstraction, Finding Maximum and Minimum, Binary Search, Divide and Conquer Matrix Multiplication, Stressen’s Matrix Multiplication, Merge Sort, Quick Sort.
Module 3 Greedy Strategy
Control Abstraction, General Knapsack Problem, Optimal Storage on Tapes, Minimum Cost Spanning Trees – Prim’s Algorithm, Kruskal’s Algorithm – Job sequencing with deadlines.
Control Abstraction, General Knapsack Problem, Optimal Storage on Tapes, Minimum Cost Spanning Trees – Prim’s Algorithm, Kruskal’s Algorithm – Job sequencing with deadlines.
Module 4 Dynamic Programming
Principle of Optimality, Multi-stage Graph, All-Pairs Shortest Paths, Travelling Salesman Problem.
Lower Bound Theory – Comparison Trees for Searching and Sorting, Oracles and Adversary Arguments – Merging, Insertion & Selection Sort; Selection of ‘k’th Smallest Element.
Principle of Optimality, Multi-stage Graph, All-Pairs Shortest Paths, Travelling Salesman Problem.
Lower Bound Theory – Comparison Trees for Searching and Sorting, Oracles and Adversary Arguments – Merging, Insertion & Selection Sort; Selection of ‘k’th Smallest Element.
Module 5 Backtracking
Control Abstraction – Bounding Functions, Control Abstraction, N-Queens Problem, Sum of Subsets, Knapsack problem.
Branch and Bound Techniques – FIFO, LIFO, and LC Control Abstractions, 15-puzzle, Travelling Salesman Problem.
Control Abstraction – Bounding Functions, Control Abstraction, N-Queens Problem, Sum of Subsets, Knapsack problem.
Branch and Bound Techniques – FIFO, LIFO, and LC Control Abstractions, 15-puzzle, Travelling Salesman Problem.
Text Book
1. Fundamentals of Computer Algorithms – Horowitz and Sahni, Galgotia
References
1. Computer Algorithms – Introduction to Design and Analysis – Sara Baase & Allen Van Gelder, Pearson Education
2. Data Structures algorithms and applications – Sahni, Tata McGrHill
3. Foundations of Algorithms – Richard Neapolitan, Kumarss N., DC Hearth & Company
4. Introduction to algorithm- Thomas Coremen, Charles, Ronald Rivest -PHI
2. Data Structures algorithms and applications – Sahni, Tata McGrHill
3. Foundations of Algorithms – Richard Neapolitan, Kumarss N., DC Hearth & Company
4. Introduction to algorithm- Thomas Coremen, Charles, Ronald Rivest -PHI