CS1251 – DESIGN AND ANALYSIS OF ALGORITHMS

ANNA UNIVERSITY TIRUCHIRAPPALLI Regulations 2007 Syllabus SEMESTER IV(4)

CS1251 – DESIGN AND ANALYSIS OF ALGORITHMS
L T P
3 0 0

UNIT I BASIC CONCEPTS OF ALGORITHMS 8
Basic Concepts – Notion of Algorithm – Fundamentals of Algorithmic Solving – Important Problem
types – Fundamentals of Analysis Framework – Asymptotic Notations and Basic Efficiency Classes.

UNIT II MATHEMATICAL ASPECTS AND ANALYSIS OF ALGORITHMS 8
Mathematical Analysis of Non–recursive Algorithm – Mathematical Analysis of Recursive Algorithm
– Example Fibonacci Numbers – Empirical Analysis of Algorithms – Algorithm Visualization.

UNIT III ANALYSIS OF SORTING AND SEARCHING ALGORITHMS 10
Brute Force – Selection Sort and Bubble Sort – Sequential Search and Brute – Force String Matching –
Divide And Conquer – Merge Sort – Quick Sort – Binary Search – Binary Tree – Traversal and
Related Properties – Insertion Sort – Depth First Search and Breadth First Search.

UNIT IV ALGORITHMIC TECHNIQUES 10
Transform and Conquer – Presorting – Balanced Search Trees – AVL Trees – Heaps and Heap sort –
Dynamic Programming – Warshall’s and Floyd’s Algorithm – Optimal Binary Search Trees – Greedy
Techniques – Prim’s Algorithm – Kruskal’s Algorithm – Dijkstra’s Algorithm – Huffman Trees.

UNIT V ALGORITHM DESIGN METHODS 9
Backtracking – 8-Queen’s Problem – Hamiltonian Circuit Problem – Subset – Sum Problem – Branch
and Bound – Assignment Problem – Knapsack Problem – Traveling Salesman Problem.
Total: 45

TEXT BOOK
1. Anany Levitin, “Introduction to the Design and Analysis of Algorithm”, Pearson Education,
2003.

REFERENCES

1. T.H. Cormen C.E. Leiserson, R.L. Rivest and C. Stein, “Introduction to Algorithms”, Second
Edition, PHI, 2007.
2. Sara Baase and Allen Van Gelder, “Computer Algorithms – Introduction to Design and
Analysis”, Pearson Education, 2003.
3. A.V.Aho J.E., Hopcroft and J.D.Ullman, “The Design and Analysis of Computer Algorithms”,
Pearson Education, 2003.

FEEL USEFUL PLEASE GIVE +1