Teaching Plan For Design and Analysis of Algorithm (DAA), TE : CE, Savitribai Phule Pune University (SPPU)

Unit	Topic and sub topics covered	Lecture
I	Fundamentals : The Role of Algorithms in Computing – What are algorithms	2
	Algorithms as technology	1
	Evolution of Algorithms	1
	Design of Algorithm	1
	Need of Correctness of Algorithm	1
	Confirming correctness of Algorithm – sample examples	1
	Iterative algorithm design issues	2
II	Models and Design : Functional Model – Features, Recursive processes, Recursive processes,  Recursive processes	1
	Scope rules, Tail recursion	1
	Checking correctness of Iterative process	1
	Imperative Model – Basics	1
	Specifications and Prototyping	1
	Stepwise Refinement	1
	Proof Rules – Basics, For loops, Goto and Exit loops	1
	Functions and Procedures	1
	Problem Solving using Greedy strategy - Knapsack problem, Huffman code generation algorithm	1
III	Abstract Algorithms: Dynamic Programming	1
	Divide and Conquer	1
	Greedy strategy	1
	Branch-n-Bound	1
	Natural Algorithms –Evolutionary Algorithms and Evolutionary Computing	2
	Introduction to Genetic Algorithm	1
	Simulated Annealing	1
	Artificial Neural Network and Tabu Search	1
IV	Complexity Theory: Complexity theory – Counting Dominant operators
	Growth rate, upper bounds, asymptotic growth, O, Ω, Ɵ, o and ω notations	2
	polynomial and non-polynomial problems	1
	deterministic and non-deterministic algorithms	1
	P-class problems, NP-class of problems	2
	Polynomial problem reduction NP complete problems- vertex cover	1
	Polynomial problem reduction NP complete problems-   3-SAT	1
	NP hard problem - Hamiltonian cycle.	1
V	Amortized Analysis: Amortized Analysis – Binary, Binomial and Fibonacci heap	2
	Dijkstra‘s Shortest path algorithm, Splay Trees, Time-Space tradeoff	2
	Introduction to Tractable and Non-tractable Problems	1
	Introduction to Randomized and Approximate algorithms	1
	Embedded Algorithms: Embedded system scheduling (power optimized scheduling algorithm)	2
	sorting algorithm for embedded systems	1
VI	Multithreaded and Distributed Algorithms: Multithreaded Algorithms - Introduction, Performance measures	1
	Analyzing multithreaded algorithms	1
	Parallel loops, Race conditions	1
	Problem Solving using Multithreaded Algorithms - Multithreaded matrix multiplication,	1
	Multithreaded merge sort	1
	Distributed Algorithms - Introduction, Distributed breadth first search	1
	Distributed Minimum Spanning Tree	1
	String Matching- Introduction, The Naive string matching algorithm	1
	The Rabin-Karp algorithm	1

Text books: (T)

T1. Parag Himanshu Dave, Himanshu Bhalchandra Dave, ―Design And Analysis of Algorithms‖, Pearson Education, ISBN 81-7758-595-9

T2. Gilles Brassard, Paul Bratley, ―Fundamentalsof Algorithmics‖, PHI, ISBN 978-81-203-1131-2

References Books: (R)

R1. Michael T. Goodrich, Roberto Tamassia , ―Algorithm Design: Foundations, Analysis and Internet Examples‖, Wiley, ISBN 978-81-265-0986-7

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

R3. Horowitz and Sahani, "Fundamentals ofComputer Algorithms", University Press, ISBN: 978 81 7371 6126, 81 7371 61262

R4. Rajeev Motwani and Prabhakar Raghavan, ―Randomized Algorithms‖, Cambridge University Press, ISBN: 978-0-521-61390-3

R5. Dan Gusfield, ―Algorithms on Strings,Trees and Sequences‖, Cambridge University Press,ISBN:0-521-67035-7