Savitribai Phule Pune University, Maharashtra (SPPU), Information Technology Semester 6, Design and Analysis of Algorithms Syllabus

314452 : DESIGN AND ANALYSIS OF ALGORITHMS

CREDITS - 04

UNIT – I INTRODUCTION 08 Hours
Brute Force method: Introduction to Brute Force method & Exhaustive search, Brute Force solution to 8 queens’ problem.
Proof Techniques: Minimum 2 examples of each: Contradiction, Mathematical Induction, Direct proofs, Proof by counterexample, Proof by contraposition.
Analysis of Algorithm: Efficiency- Analysis framework, asymptotic notations – big O, theta and omega.
Amortized Analysis: Aggregate, Accounting & Potential method with the example of stack operations. Analysis of Non-recursive and recursive algorithms: Solving Recurrence Equations (Homogeneous and nonhomogeneous).

UNIT – II DIVIDE AND CONQUER AND GREEDYMETHOD 08 Hours
Divide & Conquer: General method, Control abstraction, Merge sort, Quick Sort – Worst, Best and average case. Binary search, Finding Max-Min, Large integer Multiplication (for all above algorithms analysis to be done with recurrence).
Greedy Method: General method and characteristics, Prim’s method for MST , Kruskal’s method for MST (using nlogn complexity), Dijkstra’s Algorithm, Optimal storage on tapes, Fractional Knapsack problem, Job Sequencing.
 

UNIT - III DYNAMIC PROGRAMMING 08 Hours
General strategy, Principle of optimality, 0/1 knapsack Problem, Bellman-Ford Algorithm , Multistage Graph problem, Optimal Binary Search Trees, Travelling Salesman Problem.

UNIT – IV BACKTRACKING 08 Hours
General method, Recursive backtracking algorithm, Iterative backtracking method. 8-Queen problem, Sum of subsets, Graph coloring, Hamiltonian Cycle , 0/1 Knapsack Problem.
 

UNIT – V BRANCH AND BOUND 08 Hours
The method, Control abstractions for Least Cost Search, Bounding, FIFO branch and bound, LC branch and bound, 0/1 Knapsack problem – LC branch and bound and FIFO branch and bound solution, Traveling sales person problem
 

UNIT – VI COMPUTATIONAL COMPLEXITY AND PARALLEL ALGORITHMS 08 Hours
Computational Complexity: Non Deterministic algorithms, The classes: P, NP, NP Complete, NP Hard, Satisfiability problem, Proofs for NP Complete Problems: Clique, Vertex Cover.
Parallel Algorithms: Introduction, models for parallel computing, computing with complete binary tree, Pointer doubling algorithm.
 

Text Books
1. Horowitz and Sahani, Fundamentals of computer Algorithms, Galgotia, ISBN 81-7371-612-9.
2. S. Sridhar, Design and Analysis of Algorithms, Oxford, ISBN 10 : 0-19-809369-1.
 

Reference Books
1. Thomas H Cormen and Charles E.L Leiserson, Introduction to Algorithm, PHI, ISBN:81-203-2141-3.
2. R. C. T. Lee, SS Tseng, R C Chang, Y T Tsai, Introduction to Design and Analysis of Algorithms, A Strategic approach, Tata McGraw Hill, ISBN-13: 978-1-25-902582-2. ISBN-10: 1-25-902582-9.
3. Anany Levitin, Introduction to the Design & Analysis of Algorithm, Pearson, ISBN 81- 7758-835-4.
4. Steven S Skiena, The Algorithm Design Manual, Springer, ISBN 978-81-8489-865-1.
5. George T. Heineman, Gary Pollice, Stanley Selkow, Algorithms in a Nutshell, A Desktop Quick Reference, O’Reilly, ISBN: 9789352133611.
6. Gilles Brassard, Paul Bratle, Fundamentals of Algorithms, Pearson, ISBN 978-81-317-1244-3.
7. Michael T. Goodrich, Roberto Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, Wiley India, ISBN: 9788126509867
8. Rod Stephens, Essential Algorithms: A Practical Approach to Computer Algorithms, Wiley India, ISBN: 9788126546138