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

SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
Ċ
View Download
  49k v. 2 Mar 7, 2018, 2:33 AM Sandip Walunj
Ċ
View Download
  50k v. 2 Mar 7, 2018, 2:33 AM Sandip Walunj
Ċ
View Download
  52k v. 2 Mar 7, 2018, 2:33 AM Sandip Walunj
Ċ
View Download
  53k v. 2 May 15, 2018, 8:32 PM Sandip Walunj
Ċ
View Download
  50k v. 2 May 15, 2018, 8:32 PM Sandip Walunj
Ċ
View Download
  48k v. 2 May 15, 2018, 8:32 PM Sandip Walunj
Ċ
View Download
  159k v. 2 Jan 31, 2018, 1:36 AM Sandip Walunj
SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
Ċ
View Download
  95k v. 2 Mar 7, 2018, 3:46 AM Sandip Walunj
Ċ
View Download
  87k v. 2 Mar 7, 2018, 3:46 AM Sandip Walunj
Ċ
View Download
  109k v. 2 Mar 7, 2018, 3:46 AM Sandip Walunj
Ċ
View Download
  37k v. 2 Mar 7, 2018, 3:46 AM Sandip Walunj
Ċ
View Download
  189k v. 2 Mar 7, 2018, 3:46 AM Sandip Walunj
Ċ
View Download
  71k v. 2 Mar 7, 2018, 3:46 AM Sandip Walunj
SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
Ċ
View Download
  13772k v. 2 Jan 31, 2018, 1:30 AM Sandip Walunj
Ċ
View Download
  11401k v. 2 Jan 31, 2018, 1:30 AM Sandip Walunj
Ċ
View Download
  8053k v. 2 Jan 31, 2018, 1:30 AM Sandip Walunj
Ċ
View Download
  12467k v. 2 Jan 31, 2018, 1:30 AM Sandip Walunj
Ċ
View Download
  2342k v. 2 Mar 6, 2018, 11:38 PM Sandip Walunj
Ċ
View Download
  10156k v. 2 Jan 31, 2018, 1:30 AM Sandip Walunj
Ċ
View Download
  9246k v. 3 Jan 31, 2018, 1:30 AM Sandip Walunj
Ċ
View Download
  4396k v. 2 Jan 31, 2018, 1:30 AM Sandip Walunj
Ċ
View Download
  6681k v. 2 Mar 6, 2018, 8:52 PM Sandip Walunj
SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
Ċ
View Download
  327k v. 2 Jun 19, 2018, 2:14 AM Sandip Walunj
Ċ
View Download
  2607k v. 2 Mar 6, 2018, 11:38 PM Sandip Walunj
SelectionFile type iconFile nameDescriptionSizeRevisionTimeUser
Ċ
View Download
  138k v. 2 Sep 9, 2011, 4:26 AM Sandip Walunj
Comments