Sunday, July 8, 2012

CS 9201 DESIGN AND ANALYSIS OF ALGORITHMS-B.E -CSE-COMPUTER SCIENCE AND ENGINEERING THIRD -III SEMESTER 2008 REGULATION ANNA UNIVERSITY SYLLABUS



CSE Computer Science And Engineering III -third Semester Syllabus 2008 Regulation Anna University

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           PRELIMINARIES                                                                                         9
The Role of Algorithms in Computing-Getting Started-Growth of    Functions Recurrences-The  Substitution  Method-  The  Recurrence  Tree  Method-The  Master Metho -Probabilistic  Analysis  an Randomized  Algorithms-Th Hiring  Problem- Random Variables-Randomized Algorithms

UNIT II          DESIGN TECHNIQUE I                                                                               9
Quicksort-Description-Performance-Randomized version-Analysis.Sorting in linear time- Lower bounds for sorting-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         DESIGN TECHNIQUE II                                                                              9
Greedy Algorithms-Activity selection problem-Elements o Greedy Strategy- Huffman code.Matrix Operations-Properties of matrices-Strassen's algorithm- Solving systems of linear equations-Inverting matrices.

UNIT IV
APPLICATIONS
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         NP PROBLEMS                                                                                          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 BOOK:


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.

7/08/2012 12:10:00 AM

0 comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...