Design and Analysis of Algorithms (DAA)

Unit I . Fundamentals (09 Hours)

The Role of Algorithms in Computing - What are algorithms, Algorithms as technology, Evolution of Algorithms, Design of Algorithm, Need of Correctness of Algorithm, Confirming correctness of Algorithm – sample examples, Iterative algorithm design issues.

Unit II. Models and Design (09 Hour)

Functional Model – Features, Recursive processes, Scope rules, Tail recursion, Checking correctness of Iterative process. Imperative Model – Basics, Specifications and Prototyping, Stepwise Refinement, Proof Rules – Basics, For loops, Goto and Exit loops, Functions and Procedures, Problem Solving using Greedy strategy - Knapsack problem, Huffman code generation algorithm.

Unit III . Abstract Algorithms (09 Hours)

Dynamic Programming, Divide and Conquer, Greedy strategy, Branch-n-Bound, Natural Algorithms –Evolutionary Algorithms and Evolutionary Computing, Introduction to Genetic Algorithm, Simulated Annealing, Artificial Neural Network and Tabu Search.

Unit IV . Complexity Theory (09 Hour)

Complexity theory – Counting Dominant operators, Growth rate, upper bounds, asymptotic growth, O, Ω, Ɵ, o and ω notations, polynomial and non-polynomial problems, deterministic and non-deterministic algorithms, P-class problems, NP-class of problems, Polynomial problem reduction NP complete problems- vertex cover and 3-SAT and NP hard problem – Hamiltonian cycle.

Unit V . Amortized Analysis (09 Hours)

Amortized Analysis – Binary, Binomial and Fibonacci heaps, Dijkstra’s Shortest path algorithm, Splay Trees, Time-Space trade-off, Introduction to Tractable and Non-tractable Problems, Introduction to Randomized and Approximate algorithms, Embedded Algorithms: Embedded system scheduling (power optimized scheduling algorithm), sorting algorithm for embedded systems.

Unit VI . Multi-threaded and Distributed Algorithms (09 Hours)

Multi-threaded Algorithms - Introduction, Performance measures, Analyzing multi-threaded algorithms, Parallel loops, Race conditions.Problem Solving using Multi-threaded Algorithms - Multi-threaded matrix multiplication, Multi-threaded merge sort.Distributed Algorithms - Introduction, Distributed breadth first search, Distributed Minimum Spanning Tree.String Matching- Introduction, The Naive string matching algorithm, The Rabin-Karp algorithm

Text Books:

1. Parag Himanshu Dave, Himanshu Bhalchandra Dave, “Design And Analysis of Algorithms”, Pearson Education, ISBN 81-7758-595-9

2. Gilles Brassard, Paul Bratley, “Fundamentals of Algorithmics”, PHI, ISBN 978-81-203- 1131-2

Reference Books:

1. Michael T. Goodrich, Roberto Tamassia , “Algorithm Design: Foundations, Analysis and Internet Examples”, Wiley, ISBN 978-81-265-0986-7

2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”, MIT Press; ISBN 978-0-262-03384-8

3. Horowitz and Sahani, "Fundamentals of Computer Algorithms", University Press, ISBN: 978 81 7371 6126, 81 7371 61262

4. Rajeev Motwani and Prabhakar Raghavan, “Randomized Algorithms”, Cambridge University Press, ISBN: 978-0-521-61390-3

5. Dan Gusfield, “Algorithms on Strings, Trees and Sequences”, Cambridge University Press,ISBN:0-521-67035-7