Design and Analysis of Algorithm syllabus

2019 PATTERN. This is the 2019 pattern syllabus, the latest SPPU has published on its site for Third Year Information Technology. A 2024 pattern syllabus for this year has not been published there yet, so confirm with your college which pattern applies to you.

314445A · Third Year Information Technology, SPPU 2019 pattern. Every unit, the marks scheme, course outcomes and books, copied from the official syllabus PDF.

314445A3 h/week theoryMid-Sem 30 + End-sem 70

06.units

03.credits

Unit-wise syllabus

UNIT I

Introduction

7 hours

Proof Techniques: Contradiction, Mathematical Induction, Direct proofs, Proof by counter example, Proof by contraposition. Analysis of Algorithm: Efficiency- Analysis framework, asymptotic notations – big O, theta and omega. Analysis of Non-recursive and recursive algorithms: Solving Recurrence Equations using Masters theorem and Substitution method. Brute Force method: Introduction to Brute Force method & Exhaustive search, Brute Force solution to 8 queens’ problem. TE (Information Technology) Syllabus (2019 Course) 21 Curriculum for Third Year of Information Technology (2019 Course), Savitribai Phule Pune University

UNIT II

Divide and Conquer and Greedy Method

6 hours

Divide & Conquer: General method, 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, Kruskal’s method for MST (using nlogn complexity), Dijkstra’s Algorithm, Fractional Knapsack problem, Job Sequencing, Max flow problem and Ford-Fulkerson algorithm in transport network

UNIT III

Dynamic Programming

6 hours

General strategy, Principle of optimality, 0/1 knapsack Problem, Coin change-making problem, Bellman- Ford Algorithm, Multistage Graph problem (using Forward computation), Travelling Salesman Problem

UNIT IV

Backtracking

6 hours

General method, Recursive backtracking algorithm, Iterative backtracking method. n-Queen problem, Sum of subsets, Graph coloring, 0/1 Knapsack Problem.

UNIT V

Branch and Bound

6 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 salesperson problem- LC branch and bound

UNIT VI

Computational Complexity

5 hours

Non Deterministic algorithms, The classes: P, NP, NP Complete, NP Hard, Satisfiability problem, Proofs for NP Complete Problems: Clique, Vertex Cover

Marks and credits

Head	Marks	Credit
Mid-Sem (mid-semester exam)	30	3
End-semester exam	70	3

Prerequisite: 1. Data Structures and Algorithms. 2. Discrete Structures. 3. Basic mathematics: Induction, probability theory, logarithms..

Course outcomes

CO1Calculate computational complexity using asymptotic notations for various algorithms.
CO2Apply Divide & Conquer as well as Greedy approach to design algorithms.
CO3Understand and analyze optimization problems using dynamic programming.
CO4Illustrate different problems using Backtracking.
CO5Compare different methods of Branch and Bound strategy.
CO6Classify P, NP, NP-complete, NP-Hard problems.

Books

Text books

Horowitz and Sahani, Fundamentals of computer Algorithms, Galgotia, ISBN 81-7371-612-9.
Anany Levitin, Introduction to the Design & Analysis of Algorithm, Pearson, ISBN 81- 7758-835-4.

Reference books

Jon Kleinberg, Algorithm Design, Pearson, ISBN : 0-321-29535-8
S. Sridhar, Design and Analysis of Algorithms, Oxford, ISBN 10 : 0-19-809369-1.
Thomas H Cormen and Charles E.L Leiserson, Introduction to Algorithm, PHI, ISBN: 9788120340077
Gilles Brassard, Paul Bratle, Fundamentals of Algorithms, Pearson, ISBN 978-81-317-1244-3.
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.
Steven S Skiena, The Algorithm Design Manual, Springer, ISBN 978-81-8489-865-1.
George T. Heineman, Gary Pollice, Stanley Selkow, Algorithms in a Nutshell, A Desktop Quick Reference, O’Reilly, ISBN: 9789352133611.
Michael T. Goodrich, Roberto Tamassia, Algorithm Design: Foundations, Analysis and Internet
Examples, Wiley India, ISBN: 9788126509867
Rod Stephens, Essential Algorithms: A Practical Approach to Computer Algorithms, Wiley India, ISBN:9788126546138

FAQ

How many units are in Design and Analysis of Algorithm?

Design and Analysis of Algorithm (314445A) has 6 units: Unit I Introduction (7 h); Unit II Divide and Conquer and Greedy Method (6 h); Unit III Dynamic Programming (6 h); Unit IV Backtracking (6 h); Unit V Branch and Bound (6 h); Unit VI Computational Complexity (5 h).

What is the marks scheme for Design and Analysis of Algorithm?

The official Information Technology 2019 pattern syllabus lists mid-semester (Mid-Sem) for 30 marks and the end-semester exam for 70 marks, for 3 credits.

What should I know before Design and Analysis of Algorithm?

Prerequisite listed in the syllabus: 1. Data Structures and Algorithms. 2. Discrete Structures. 3. Basic mathematics: Induction, probability theory, logarithms..