Title of the Subject: Design and Analysis of Algorithms (DAA) Course Code: MCA 206
Teaching Scheme: Lectures: 4 Hrs/Week Practical : 2 Hrs/Week
Examination Scheme: Theory Paper: 100 Marks (3 Hrs) Practical Exam: 25 Marks Term Work: 25 Marks
To study different methods to devise an algorithm
To use computational complexity to analyze algorithms
Unit 1: Introduction and a brief review of Elementary Data Structures
Definition of an Algorithm, Algorithm specification, Performance analysis: -Space and time complexity, Asymptotic Notation, Practical Complexities, Performance Measurement, heap and
heap sort, sets and disjoint set, Union, graphs, hashing.
Unit 2: Divide and Conquer -
General method of Divide and Conquer, Binary search, finding the maximum and minimum, merge
sort, quick sort, Selection, Strassen’s Matrix Multiplication.
Unit 3: The Greedy Method: -
General method, Knapsack Problem, Tree vertex splitting, Job sequencing with deadlines, Minimum cost spanning trees, optimal storage on tape, optimal merge Patterns, Single sources shortest paths.
Unit 4: Basic Search and Traversal Techniques -
The techniques for binary trees, Techniques for graphs, connected components and spanning trees,
Biconnected Components and DFS
Unit 5: Backtracking and Branch and Bound Technique -
The general method of backtracking, The 8- queens problem, sum of subsets, Graph coloring, Hamiltonian cycles, Knapsack problem using backtracking. The method of branch and bound, 0/1 knapsack problem, Traveling sales person problem using branch and bound.
Text Books/Reference Books:
E. Horowitz and S. Sahni, “Fundamentals of Computer Algorithms”, Galgotia Pub
Aho, Hopcroft, Ulman, “The Design and Analysis of Computer Algorithms”, Addison Wesley
Term Work: The term work shall consist of at least 10 experiments/ assignments based on the syllabus above. Assessment of term work should be done which will consider the points below and the marks should be awarded accordingly.