Syllabus
|
Course Code: MCA-20-25 Course Name: Elective-II - (ii) Design and Analysis of Algorithms |
||
| MODULE NO / UNIT | COURSE SYLLABUS CONTENTS OF MODULE | NOTES |
|---|---|---|
| 1 | Introduction: Algorithms, Role of algorithms in computing, Analysing algorithms, Designing algorithms, Asymptotic notations. Divide and Conquer: Solving recurrence equations: Back substitution method, Recursion tree method, Masters theorem. Probabilistic Analysis and Randomized Algorithms: The hiring problem, Indicator random variables, Randomized algorithms, Probabilistic analysis and further uses of indicator random variables |
|
| 2 | Trees: Red-black trees and Splay trees. Dynamic Programming (DP): Elements of DP, Matrix chain multiplication, Longest common subsequence, optimal binary search trees. Greedy Techniques (GT): Elements of GT, Activity selection problem, Huffman codes, Knapsack Problem. |
|
| 4 | Computational Geometry: Line-segment properties, Convex hull, Closest pair of points. Computational complexity: Notion of Polynomial time algorithms, Complexity classes: P, NP, NP-Hard and NP-Complete, Polynomial time verification, Reducibility, NP-Completeness, Examples of NP-Complete and NP-Hard problems: Traveling Salesman Problem, Knapsack, Bin Packing, Satisfiability, Vertex Cover, Clique, Independent Set. |
|
