JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Pre-requisites:

• 1. A course on “Computer Programming & Data Structures”
• 2. A course on “Advanced Data Structures & Algorithms”

Course Objectives:

• Introduces the recurrence relations for analyzing the algorithms
• Introduces the graphs and their traversals.
• Describes major algorithmic techniques (divide-and-conquer, greedy, dynamic programming, Brute Force, Transform and Conquer approaches) and mention problems for which each technique is appropriate;
• Describes how to evaluate and compare different algorithms using worst-case, average-case and best-case analysis.
• Introduces string matching algorithms
• Introduces linear programming.

Course Outcomes:

• Ability to analyze the performance of algorithms
• Ability to choose appropriate data structures and algorithm design methods for a specified application
• Ability to understand how the choice of data structures and the algorithm design methods impact the performance of programs

UNIT - I

Introduction: Role of Algorithms in computing, Order Notation, Recurrences, Probabilistic Analysis and Randomized Algorithms. Sorting and Order Statistics: Heap sort, Quick sort and Sorting in Linear Time. Advanced Design and Analysis Techniques: Dynamic Programming- Matrix chain Multiplication, Longest common Subsequence and optimal binary Search trees.

UNIT - II

Greedy Algorithms - Huffman Codes, Activity Selection Problem. Amortized Analysis. Graph Algorithms: Topological Sorting, Minimum Spanning trees, Single Source Shortest Paths, Maximum Flow algorithms.

UNIT - III

Sorting Networks: Comparison Networks, Zero-one principle, bitonic Sorting Networks, Merging Network, Sorting Network. Matrix Operations- Strassen's Matrix Multiplication, Inverting matrices, Solving system of linear Equations

UNIT - IV

String Matching: Naive String Matching, Rabin-Karp algorithm, matching with finite Automata, Knuth- Morris - Pratt algorithm.

UNIT - V

NP-Completeness and Approximation Algorithms: Polynomial time, polynomial time verification, NP-Completeness and reducibility, NP-Complete problems. Approximation Algorithms- Vertex cover Problem, Travelling Sales person problem

TEXT BOOK:

• 1. Introduction to Algorithms,'' T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Third Edition, PHI.

REFERENCE BOOKS:

• 1. Fundamentals of Computer Algorithms, Ellis Horowitz, Satraj Sahni and Rajasekharam, Galgotia publications pvt. Ltd.
• 2. Design and Analysis Algorithms - Parag Himanshu Dave, Himanshu Bhalchandra Dave Publisher: Pearson
• 3. Algorithm Design: Foundations, Analysis and Internet examples, M.T. Goodrich and R. Tomassia, John Wiley and sons.
• 4. Data structures and Algorithm Analysis in C++, Allen Weiss, Second edition, Pearson education.