Educational videos of Design and Analysis of Algorithms

Download/Source url :

http://www.youtube.com/watch?v=5Y8Lfsreeck&feature=player_embedded

By Prof.Abhiram Ranade, Department of Computer Science Engineering,IIT Bombay.



DESIGN AND ANALYSIS OF ALGORITHMS SYLLABUS :

Source :http://jntuk.edu.in

UNIT I :
Introduction: Algorithm,Psuedo code for expressing algorithms,Performance Analysis-Space complexity,
Time complexity, Asymptotic Notation- Big oh notation, Omega notation, Theta notation and Little oh
notation,Probabilistic analysis, Amortized analysis.


UNIT II :
Disjoint Sets- disjoint set operations, union and find algorithms, spanning trees, connected components
and biconnected components.


UNIT III :
Divide and conquer: General method , applications-Binary search, Quick sort, Merge sort, Strassen’s
matrix multiplication.


UNIT IV :
Greedy method: General method, applications-Job sequencing with dead lines, 0/1 knapsack problem,
Minimum cost spanning trees, Single source shortest path problem.


UNIT V :
Dynamic Programming: General method, applications-Matrix chain multiplication, Optimal binary search
trees, 0/1 knapsack problem, All pairs shortest path problem,Travelling sales person problem, Reliability
design.


UNIT VI :
Backtracking: General method, applications-n-queen problem, sum of subsets problem, graph coloring,
Hamiltonian cycles.


UNIT VII :
Branch and Bound: General method, applications - Travelling sales person problem,0/1 knapsack
problem- LC Branch and Bound solution, FIFO Branch and Bound solution.


UNIT VIII :
NP-Hard and NP-Complete problems: Basic concepts, non deterministic algorithms, NP - Hard and
NPComplete classes, Cook’s theorem.


TEXT BOOKS :
1. Fundamentals of Computer Algorithms, Ellis Horowitz,Satraj Sahni and
Rajasekharam,Galgotia publications pvt. Ltd.
2. Algorithm Design: Foundations, Analysis and Internet examples,
M.T.Goodrich and R.Tomassia,John wiley and sons.


REFERENCES :
1. Introduction to Algorithms, secondedition,T.H.Cormen,C.E.Leiserson,
R.L.Rivest,and C.Stein,PHI Pvt. Ltd./ Pearson Education
2. Introduction to Design and Analysis of Algorithms A strategic approach,
R.C.T.Lee, S.S.Tseng, R.C.Chang and T.Tsai, Mc Graw Hill.
3. Data structures and Algorithm Analysis in C++, Allen Weiss, Second
edition, Pearson education.
4. Design and Analysis of algorithms, Aho, Ullman and Hopcroft,Pearson
education.
5. Algorithms – Richard Johnson baugh and Marcus Schaefer, Pearson
Education

6:50 PM