Pune University Final Year Engineering Syllabus

Can you provide me the syllabus of B.E. Computer Engineering program offered by Faculty of Engineering of Savitribai Phule Pune University?

[pawan]

The syllabus of B.E. Computer Engineering program offered by Faculty of Engineering of Savitribai Phule Pune University is as follows:

410441 - Design and Analysis of Algorithms
Unit
I
Problem solving and Algorithmic Analysis
Problem solving principles: Classification of problem, problem solving
strategies, classification of time complexities (linear, logarithmic etc)
problem subdivision – Divide and Conquer strategy.
Asymptotic notations, lower bound and upper bound: Best case, worst case,
average case analysis, amortized analysis. Performance analysis of basic
programming constructs. Recurrences: Formulation and solving recurrence
equations using Master Theorem.

II
Greedy and Dynamic Programming Algorithmic Strategies Greedy strategy: Principle, control abstraction, time analysis of control abstraction, knapsack problem, scheduling algorithms-Job scheduling and activity selection problem.
Dynamic Programming: Principle, control abstraction, time analysis of control abstraction, binomial coefficients, OBST, 0/1 knapsack, Chain Matrix multiplication.

III
Backtracking and Branch-n-Bound
Backtracking: Principle, control abstraction, time analysis of control abstraction, 8-queen problem, graph coloring problem, sum of subsets problem. Branch-n-Bound: Principle, control abstraction, time analysis of control abstraction, strategies – FIFO, LIFO and LC approaches, TSP, knapsack problem.

IV
Complexity Theory
Overview: Turing machine, polynomial and non-polynomial problems, deterministic and non-deterministic algorithms, P class, NP class & NP complete problems- vertex cover and 3-SAT and NP–hard problem – Hamiltonian cycle. The menagerie of complexity classes of Turing degrees. Concept of randomized and approximation algorithms: Solving TSP by approximation algorithm, Randomized sort algorithms and Approximating Max Clique.

V
Parallel and Concurrent Algorithms
Parallel Algorithms: Sequential and parallel computing, RAM & PRAM models, Amdahl’s Law, Brent’s theorem, parallel algorithm analysis and optimal parallel algorithms, graph problems (shortest paths and Minimum Spanning Tree, Bipartite graphs ) Concurrent Algorithms: Dining philosophers problem


Pune University B.E. Computer Engineering Syllabus