Analysis and Design of Algorithm

Paper Code: 
MCA 523
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 
  • To Learn the algorithm analysis techniques.
  • To Become familiar with the different algorithm design techniques.

To Understand the limitations of Algorithm power

10.00
Unit I: 
Introduction

Introduction - algorithm definition and specification – Design of Algorithms, and Complexity of Algorithms, Asymptotic Notations, Growth of function

 

 

12.00
Unit II: 
Elementary Data structures

Elementary Data structures

Stacks and queues – Link Lists- Trees – priority queues –sets  and disjoint set union – graphs – basic traversal and search techniques.

 

12.00
Unit III: 
Divide – and – conquer

Divide – and – conquer:-

General method – binary search – merge sort – Quick sort – The  Greedy method:-General method – knapsack problem – minimum cost spanning tree – single  source shortest path

 

 

13.00
Unit IV: 
Dynamic Programming

Dynamic Programming – general method – multistage graphs – all pair shortest path – optimal binary search trees – 0/1 Knapsack – traveling salesman problem

 

13.00

Backtracking:- general method – 8-Queens problem – sum of subsets

Hamiltonian cycles – knapsack problem – Branch and bound:- The Method – 0/1 Knapsack problem – traveling salesperson.

 

 

ESSENTIAL READINGS: 
  • Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, Third Edition, Pearson Education, 2012.
  • Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”, Third Edition, PHI Learning Private Limited, 2012.

 

REFERENCES: 

Donald E. Knuth, “The Art of Computer Programming”, Volumes 1& 3 Pearson Education,2009.

Steven S. Skiena, “The Algorithm Design Manual”, Second Edition, Springer, 2008.

Academic Year: 
2016-17
  • Printer-friendly version