JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Prerequisites:

• 1. A course on “Computer Programming and Data Structures”
• 2. A course on “Discrete Structures and Graph Theory”

Course Objectives:

• Introduces to theory of computational complexity classes
• Discuss about algorithmic techniques and application of these techniques to problems.
• Introduce to randomized algorithms and discuss how effective they are in reducing time and space complexity.
• Discuss about Graph based algorithms and approximation algorithms
• Discuss about search trees

Course Outcomes:

• Ability to classify decision problems into appropriate complexity classes
• Ability to specify what it means to reduce one problem to another, and construct reductions for simple examples.
• Ability to classify optimization problems into appropriate approximation complexity classes
• Ability to choose appropriate data structure for the given problem
• Ability to choose and apply appropriate design method for the given problem

UNIT - I

Computational Complexity: Polynomial time and its justification, Nontrivial examples of polynomial-time algorithms, the concept of reduction (reducibility), Class P Class NP and NP- Completeness, The P versus NP problem and why it’s hard

UNIT - II

Algorithmic paradigms: Dynamic Programming – Longest common subsequence, matrix chain multiplication, knapsack problem, Greedy – 0-1 knapsack, fractional knapsack, scheduling problem, Huffman coding, MST, Branch-and-bound – travelling sales person problem, 0/1 knapsack problem, Divide and Conquer – Merge sort, binary search, quick sort.

UNIT - III

Randomized Algorithms: Finger Printing, Pattern Matching, Graph Problems, Algebraic Methods, Probabilistic Primality Testing, De-Randomization Advanced Algorithms.

UNIT - IV

Graph Algorithms: Shortest paths, Flow networks, Spanning Trees; Approximation algorithms, Randomized algorithms. Approximation algorithms: Polynomial Time Approximation Schemes.

UNIT - V

Advanced Data Structures and applications: Decision Trees and Circuits, B-Trees, AVL Trees, Red and Black trees, Dictionaries and tries, Maps, Binomial Heaps, Fibonacci Heaps, Disjoint sets, Union by Rank and Path Compression

TEXT BOOKS:

• 1. T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, Third Edition, McGraw-Hill, 2009.
• 2. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
• 3. J. J. McConnell, Analysis of Algorithms: An Active Learning Approach, Jones & Bartlett Publishers, 2001.
• 4. D. E. Knuth, Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition, Addison-Wesley Professional, 1998.
• 5. S. Dasgupta, C. H. Papadimitriou and U. V. Vazirani, Algorithms, McGraw-Hill, 2008.