18MCA33 Design and Analysis of Algorithms syllabus for MCA



A d v e r t i s e m e n t

Module-1 Introduction, Fundamentals of the Analysis of Algorithm Efficiency 0 hours

Introduction, Fundamentals of the Analysis of Algorithm Efficiency

Notion of Algorithm, Fundamentals of Algorithmic Problem Solving, Important Problem Types, Fundamental data Structures. Analysis Framework, Asymptotic Notations and Basic efficiency classes, Mathematical analysis of Recursive and Non-recursive algorithms.

Module-2 Brute Force 0 hours

Brute Force:

Selection Sort and Bubble Sort, Sequential Search, Exhaustive search and String Matching.

 

Divide-and-Conquer

Mergesort, Quicksort, Binary Search, Binary tree Traversals and related properties, Multiplication of large integers.

Module-3 Decrease-and-Conquer 0 hours

Decrease-and-Conquer

Insertion Sort, Depth First and Breadth First Search, Topological sorting, Algorithms for Generating Combinatorial Objects: generating permutations.

 

Greedy Technique

Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffmann Trees.

Module-4 Space and Time Tradeoffs 0 hours

Space and Time Tradeoffs

Sorting by Counting, Input Enhancement in String Matching, Hashing.

 

Dynamic Programming

Computing a binomial coefficient, Warshall’s and Floyd’s Algorithms, The Knapsack Problem and Memory Functions

Module-5 Limitations of Algorithm Power 0 hours

Limitations of Algorithm Power

Lower-Bound Arguments, Decision Trees, P, NP and NP-Complete Problems.

 

Coping with Limitations of Algorithm Power

Backtracking: n-Queens problem, Hamiltonian Circuit Problem, Subset – Sum Problem. Branch-and- Bound: Assignment Problem, Knapsack Problem, Traveling Salesperson Problem.

 

Course Outcome (CO):

At the end of this course, the students will be able to

CO1: Categorize problems based on their characteristics and practical importance.

CO2: Develop Algorithms using iterative/recursive approach

CO3: Compute the efficiency of algorithms in terms of asymptotic notations

CO4: Design algorithm using an appropriate design paradigm for solving a given problem

CO5: Classify problems as P, NP or NP Complete

CO6: Implement algorithms using various design strategies and determine their order of growth.

 

Question paper pattern:

  • The question paper will have ten questions.
  • Each full question consists of 16 marks.
  • There will be 2 full questions (with a maximum of four sub questions) from each module.
  • Each full question will have sub questions covering all the topics under a module.
  • The students will have to answer 5 full questions, selecting one full question from each module.

 

Text Books:

1. Anany Levitin: Introduction to the Design and Analysis of Algorithms, Pearson Education, 2nd Edition.(Chapters 1.1-1.4, 2.1-2.4, 3.1, 3.2, 3.4, 4.1-4.5, 5.1-5.4, 7.1-7.3, 8.1, 8.2, 8.4, 9.1-9.4, 11.1- 11.3, 12.1-12.2)

 

Reference Books:

1. Coremen T.H., Leiserson C.E., and Rivest R.L.: Introduction to Algorithms, PHI 1998.

2. Horowitz E., Sahani S., Rajasekharan S.: Computer Algorithms, Galgotia Publication 2001.

3. Michael T Goodrich and Roberto Tamassia : Algorithm Design, Wiley India

4. 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

Last Updated: Tuesday, January 24, 2023

Categories

VTU Updates