Design and Analysis of Algorithm

Course Objectives :

1. To Introduce various designing techniques and methods for algorithms
2. Performance analysis of Algorithms using asymptotic and empirical approaches
3. Demonstrate a familiarity with major algorithms and data structures.
4. To give clear idea on algorithmic design paradigms like Divide-and-Conquer, Dynamic Programming, Greedy, Branch & Bound, Back tracking and string matching and network flow.

Course Outcomes (CO)

• CO 1 Analyse asymptotic runtime complexity of algorithms including formulating recurrence relations and divide and conquer designing method.
• CO 2 Describe the greedy paradigm and apply Greedy strategy for solving various problems.
• CO 3 Apply dynamic programming and Branch & Bound approach to solve suitable problems
• CO 4 Understand the concept of NP problems and string matching algorithm and various flow & sorting networks

UNIT-I

Asymptotic notations for time and space complexity, Methods for solving Recurrence relations, Brief Review of Graphs, Sets and disjoint sets, union, sorting and searching algorithms and their analysis in terms of space and time complexity.

Divide and Conquer: General method, binary search, merge sort, Quick sort, selection sort, Strassen’s matrix multiplication algorithms and analysis of algorithms for these problems.

UNIT-II

Greedy Method: General method, knapsack problem, Huffman Codes, job sequencing with deadlines, minimum spanning trees, single souce paths and analysis of these problems.

Back Tracking: General method, 8 queen’s problem, graph colouring, Hamiltonian cycles, and analysis of these problems.

UNIT-III

Dynamic Programming: Ingredients of Dynamic Programming. Matrix Chain Multiplication, Longest common subsequence and optimal binary search trees problems, 0-1 knapsack problem, Traveling salesperson problem, Floyd Warshall algorithm.

Branch and Bound: Method, O/I knapsack and traveling salesperson problem

UNIT - IV

String Matching: The naïve String Matching algorithm, The Rabin-Karp Algorithm, String Matching with finite automata, The Knuth-Morris Pratt algorithm.

Computational Complexity: Basic Concepts, Polynomial vs Non-Polynomial Complexity, NP- hard & NP complete classes. Approximation Algorithms

Flow and Sorting Network:, Ford- Fulkerson method, Maximum bipartite matching, Sorting Networks, Comparison network, Zero- one principle, Bitonic sorting network, merging network

Textbook(s):

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein, Introduction to Algorithms, 3rd Ed., PHI, 2013.
2. Udit Aggarwal, Algorithm Design and Analysis, Dhanpat Rai and Co.

References:

1. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer Algorithms/C++, Second Edition, Universities Press.
2. Jon Klenberg, Eva Tardos, Algorithm Design, Pearson Publications,2014.
3.  A. V. Aho, J. E. Hopcroft, J. D. Ullman, The Design and Analysis of Computer Algorithms, Pearson, 2013.
4. Richard Neapolitan, Foundations of Algorithms, Fifth Edition, Jones & Bartlett Learning
5. Sara Base, Introduction to Design & analysis,Pearson