MCA

Type: Elective
Contact Hours: 4 hours/week
Examination Duration: 3 Hours
Mode: Lecture
External Maximum Marks: 75
External Pass Marks: 30(i.e. 40%)
Internal Maximum Marks: 25
Total Maximum Marks: 100
Total Pass Marks: 40(i.e. 40%)

Instructions to paper setter for End semester exam:
Total number of questions shall be nine. Question number one will be compulsory and will be consisting of short/objective type questions from complete syllabus. In addition to compulsory first question there shall be four units in the question paper each consisting of two questions. Student will attempt one question from each unit in addition to compulsory question. All questions will carry equal marks.

Course Objectives: The objective of this course is to provide the in-depth coverage of various algorithm design techniques. It focuses on various problems and their solutions using different algorithm design techniques.

Course Outcomes (COs)   At the end of this course, the student will be able to:
MCA-20-25(ii).1                   understand the complexity of problems and apply the solutions accordingly;
MCA-20-25(ii).2                  categorize problems based on their characteristics and practical importance;
MCA-20-25(ii).3                  design solutions to problems using various algorithmic techniques;
MCA-20-25(ii).4                  classifying and solving problems as P, NP or NP Complete.
                                                                                         Unit – I
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
                                                                                        Unit – II
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.
                                                                                        Unit – III
Graph Algorithms: Topological sort, Strongly connected components, Single source shortest path: Analysis of Dijkstra’s Algorithm, Limitations of Dijkstra’s Algorithm, Negative weight cycle, Bellman-Ford algorithm. All Pairs Shortest Path: Relation of Shortest path and matrix multiplication, Analysis of Floyd Warshall algorithm. Maximum Flow: Flow network, Ford-Fulkerson method.
Strings: Storage of strings, Naive string-matching algorithm, Rabin-Karp algorithm, String matching with finite automata, Knuth-Morris-Pratt algorithm

                                                                                        Unit – IV
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.
Text Books:
⦁ Cormen, Leiserson, Rivest, Introduction to Algorithms, PHI India.
⦁ Neapolitan R., Foundations of Algorithms, Jones and Bartlett Learning.
Reference Books:
⦁ . Cooper A., Computability Theory, Chapman and Hall/ CRC Press.
⦁ A.V.Aho, J.E.Hopcroft, and J.D.Ullman, The Design and Analysis of Computer Algorithms, Pearson Education India
⦁ AnanyLevitin: Introduction to the Design and Analysis of Algorithms, Pearson Education.
⦁ R.C.T Lee, S.S. Tseng, R.C. Chang, Y.T. Tsai, Introduction to Design and Analysis of Algorithms: A Strategic Approach, Tata McGraw Hill
⦁ Steven Skiena, The Algorithm Design Manual, Springer India.