06CS43 - ANALYSIS AND DESIGN OF ALGORITHMS Regulation 2006 - 2007 |
PART – A |
UNIT 1 |
1. Introduction: What is an Algorithm?, Fundamentals of Algorithmic
Problem Solving, Important Problem Types, Fundamental Data
Structures. |
UNIT 2 |
2. Fundamentals of the Analysis of Algorithm Efficiency: Analysis
Framework.
3. Asymptotic Notations and Basic Efficiency Classes, Mathematical
Analysis of Nonrecursive and Recursive Algorithms, Example –
Fibonacci Numbers |
UNIT 3 |
4. Brute Force: Selection Sort and Bubble Sort, Sequential Search and
Brute-Force String Matching, Exhaustive Search.
5. Divide and Conquer: Mergesort, Quicksort, Binary Search
|
UNIT 4 |
6. Divide and Conquer contd.: Binary tree traversals and related
properties, Multiplication of large integers and Stressen’s Matrix
Multiplication.
7. Decrease and Conquer: Insertion Sort, Depth First Search, Breadth
First Search, Topological Sorting,
Algorithms for Generating Combinatorial Objects
|
PART – B |
UNIT 5 |
8. Transform and Conquer: Presorting, Balanced Search Trees, Heaps
and Heapsort, Problem Reduction
9. Space and Time Tradeoffs: Sorting by Counting, Input Enhancement
in String Matching |
UNIT 6 |
10. Space and Time Tradeoff contd.: Hashing
11. Dynamic Programming: Computing a Binomial Coefficient,
Warshall’s and Floyd’s Algorithms, The Knapsack Problem and
Memory Functions
|
UNIT 7 |
12. Greedy Technique: Prim’s Algorithm,Kruskal’s Algorithm,
Dijkstra’s Algorithm, Huffman Trees.
13. Limitations of Algorithm Power: Lower-Bound Arguments, Decision
Trees
|
UNIT 8 |
14. Limitations of Algorithm Power contd.: P, NP and NP-Complete
Problems
15. Coping with the Limitations of Algorithm Power: Backtracking,
Branch-and-Bound, Approximation Algorithms for NP-Hard
Problems
|
REFERENCE |
TEXT BOOKS: |
Introduction to The Design & Analysis of Algorithms, Anany
Levitin, 2nd Edition, Pearson Education, 2007.
(Chapter 1, 2.1 to 2.5, 3.1, 3.2, 3.4, 4.1 to 4.5, 5.1 to 5.4, 6.1, 6.3,
6.4, 6.6, 7.1 to 7.3, 8.1, 8.2, 8.4, 9, 11.1, 11.2, 11.3, 12.1, 12.2,
12.3).
|
Reference Books |
1. Introduction to Algorithms, Thomas H. Cormen, Charles E.
Leiserson, Ronal L. Rivest, Clifford Stein, 2nd Edition, PHI, 2006.
2. Computer Algorithms by Horowitz E., Sahni S., Rajasekaran S.,
Galgotia Publications, 2001.
|
|