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

# Objectives:

•

To study different methods to devise an algorithm

•

To use computational complexity to analyze algorithms

# Contents:

Unit 1: Introduction and a brief review of Elementary Data Structures

(8 Hrs)

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 -

(8 Hrs)

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: -

(8 Hrs)

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 -

(8 Hrs)

# 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 -

(8 Hrs)

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:

1.

E. Horowitz and S. Sahni, “Fundamentals of Computer Algorithms”, Galgotia Pub

2.

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.