Analysis and Design of Algorithm

Paper Code: 
MCA 523
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 
  • To Understand the limitations of Algorithm power
  • To Learn the algorithm analysis techniques.
  • To Become familiar with the different algorithm design techniques.
10.00
Unit I: 

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

12.00
Unit II: 

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

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 – general method – multistage graphs – all pair shortest path – optimal binary search trees – 0/1 Knapsack – traveling salesman problem

13.00
Unit V: 

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: 
2017-18
  • Printer-friendly version