Tuesday, July 10, 2012

CS9201-DESIGN AND ANALYSIS OF ALGORITHMS-ANNA UNIVERSITY SYLLABUS IT


CS9201-DESIGN AND ANALYSIS OF ALGORITHMS-ANNA UNIVERSITY SYLLABUS IT


CS9201                     DESIGN AND ANALYSIS OF ALGORITHMS                     L T P C 3  0 0  3
AIM:

The aim  is to  introduce  the  basics  of algorithm  design  paradigms  and  analysis  to enable designing of efficient algorithms.

OBJECTIVES:

·      To introduce the basic concepts of algorithm analysis
·      To introduce the design paradigms for algorithm design
·      To introduce the basic complexity theory.

UNIT I                                                                                                                                 9
The Role of Algorithms in Computing-Getting  Started-Growth of    Functions Recurrences-The   Substitution  Method-  The  Recurrence  Tree  Method-The  Master Method  -Probabilisti Analysi and  Randomize Algorithms-The   Hiring  Problem- Random Variables-Randomized  Algorithms.

UNIT II                                                                                                                                9
Quicksort-Description-Performance-Randomized   version-Analysis.Sorting    i linear time-Lower  bounds  fosorting-Counting  sort-Medians  and  order  statistics-Minimum and maximum-Selection in expected linear time- Selection in worst-case linear time- Dynamic  Programming  –  Matrix  chain  multiplication  Elements  of  Dynamic programming- Longest common sequences.
          UNIT III
Greedy Algorithms-Activity selection problem-Elements of  Greedy Strategy-Huffman code.Matrix  Operations-Properties  of  matrices-Strassen's  algorithm-Solving  systems of linear equations-Inverting matrices.


UNIT IV                                                                                                                              9
Linear  Programming-Standard  and  slack  forms-Formulating  problems-Simplex algorithm-Duality-Initial  basic feasible solution - String Matching-Naive  string matching algorithm-Knuth-Morris-Pratt algorithm.

UNIT V                                                                                                                                9
NP-completeness-Polynomial time-Polynomial-time  verification-NP-completeness and reducibility-NP-completeness proofs - NP-completeness problems. Approximation Algorithms-The vertex-cover problem-The traveling-salesman problem.



TEXT BOOKS:

TOTAL: 45 PERIODS

1.  Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest, Cliford Stein, Introduction to Algorithms, Second Edition, Prentice Hall of India, 2007.

REFERENCES

1.  Jon Kleinberg, Eva Tardos, Algorithm Design, Pearson Education, 2006.
2.  Michael T. Goodrich, Toberto Tamassisa, Algorithm Design: Foundations, Analysis and Internet Examples,                                              Wiley Student Edition, 2007.
3.  Anany Levitin, Introduction to Design and Analysis of Algorithms, Pearson
Education, 2003.


CLICK HERE FOR ALL SUBJECTS

7/10/2012 10:42:00 AM

0 comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...