ANALYSIS AND DESIGN OF ALGORITHMS

Paper Code: 
MCS 224
Credits: 
04
Periods/week: 
04
Max. Marks: 
100.00
Objective: 

It is being taught with the intention to teach the student how to measure the effectiveness of an algorithm and also to build an efficient way to carry out various types of sorting and searching techniques.

12.00
Unit I: 
Basic Concepts of Algorithms

Introduction, Notion of Algorithm, Fundamentals of Algorithmic Solving, Important Problem types, Fundamentals of the Analysis Framework, Asymptotic Notations and Basic Efficiency Classes, Problem Classifications, NP class, NP completeness, reducibility, NP complete problems.

12.00
Unit II: 
Mathematical Aspects and Analysis of Algorithms

Mathematical Analysis of Non-Recursive Algorithm, Mathematical Analysis of Recursive Algorithm, Solving Recurrence Relations, Example: Fibonacci Numbers, Empirical Analysis of Algorithms, Algorithm Visualization.

12.00
Unit III: 
Analysis Of Sorting and Searching Algorithms

Radix Sort, Sequential Search and Brute-force string matching, Divide and conquer, Merge sort, Quick Sort, Hashing, Binary Search, Binary tree, Traversal and Related Properties, Decrease and Conquer , Insertion Sort , Depth first Search and Breadth First Search.

12.00
Unit IV: 
Algorithmic Techniques

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, Kruskal’s Algorithm, Dijkstra’s Algorithm , Huffman trees.

12.00
Unit V: 
Algorithm Design Methods

Backtracking, n-Queen’s Problem, Hamiltonian Circuit problem, Subset-Sum problem, Branch and bound, Assignment problem, Knapsack problem, Traveling salesman problem, Flow-Shop Scheduling.

ESSENTIAL READINGS: 

1. T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, “Introduction to Algorithms”, PHI Pvt. Ltd., 2001
2. Y. Langsam, M.J. Angestein and A.M. Tanenbaum, “Data Structures Using C and C++”, Prentice Hall of India.

REFERENCES: 

1. Anany Levitin, “Introduction to the Design and Analysis of Algorithm”, Pearson Education Asia, 2003.
2. Sara Baase and Allen Van Gelder, “Computer Algorithms, Introduction to Design and    Analysis”, Pearson Education Asia, 2003.
3. A.V.Aho, J.E. Hopcroft and J.D.Ullman, “The Design and Analysis of Computer Algorithms”, Pearson Education Asia, 2003.
4. Ellis Horowitz, Sarataj Sahni, S. Rajsekaran, ”Fundamentals of Computer Algorithms”, University press.
5. Mark Allen Weiss, “Data Structure & Algorithm Analysis in C++”, Third Edition,     Pearson Education.

  • Printer-friendly version