Syllabus - AA
510101- Applied Algorithms
Unit I. Analysis of algorithms
Review of algorithmic strategies, Asymptotic analysis: upper and lower complexity bounds. Identifying differences among best, average and worst Case Behaviors. Big O, little O, omega and theta notations, Standard complexity classes. Empirical measurements of performance. Time and space trade-offs in algorithms. Analyzing recursive algorithms using recurrence relations.
Unit II. Fundamental Computing Algorithms
Numerical algorithms, Sequential and binary search algorithms. Quadratic sorting
algorithms and O (n log n) sorting algorithms. Algorithms on graphs and their complexities using Greedy Approach for --- Prim’s and Krushkal’s Algorithm for
minimum spanning tree, Single source shortest path Algorithm, all pair shortest paths in Graph
Unit III. Approximation Algorithms
Introduction, Absolute approximation, Epsilon approximation, Polynomial time Approximation schemes, probabilistically good algorithms.
Unit IV. Geometric Algorithms
Prerequisites – Basic properties of line, intersection of line, line segment, polygon,etc. Line segment properties, detaining segment intersection in time complexity (n log n),Convex full problem – formulation, solving by Graham scan algorithm, Jarvis march algorithm; closest pair of points – problem formulation, solving by divide & conquer method.
Unit V. Linear Programming
Standard and Slack forms, formulation of problems as linear programs, simplex algorithm, duality, initial basic feasible solution. Problem formulation for – single source shortest path, maximum flow problem, Vertex cover problem, Knapsack problem.
Unit VI. Probability Based Analysis
Expectations: Introduction, Moments, Expectations of functions of more than one random variable, transform methods, moments and transforms of distributions,
computation of mean time to failure, inequalities and limit theorems
Reference Books:
1. Kishore S. Trivedi, “Probability & Statistics with Reliability, Queing, and Computer Science Applications” PHI
2. Cormen, Leiserson, Rivest, “Algorithms”, PHI
3. Bressard, “Fundamentals of Algorithms”, PHI
4. Horowitz, Sahni, “Fundamentals of Computer Algorithm”, Galgotia
5. S. Baase, S and A. Van Gelder, "Computer Algorithms: Introduction to Design and
Analysis", 3rd edition. Addison Wesley,2000
6. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms”, Addison Wesley
7. Knuth, “Art of Programming”, Addison Wesley
8. C Papadimitriou and K Steiglitz, “Combinatorial Optimization”, PHI
No comments:
Post a Comment