X hits on this document

# Part – I - page 10 / 27

50 views

0 shares

10 / 27

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)

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

 Document views 50 Page views 50 Page last viewed Sat Oct 22 14:16:32 UTC 2016 Pages 27 Paragraphs 1177 Words 8520