2CSE503: Algorithm Analysis & Design

Learning Outcomes: 
After learning the course the students should be able to
Derive and solve recurrences describing the performance of divide-and-conquer algorithms.
Find optimal solution by applying various methods.
Apply pattern matching algorithms to find particular pattern.
Differentiate polynomial and non-polynomial problems
Explain the major graph algorithms and their analyses. Employ graphs to model engineering problems, when appropriate.
Analyze the asymptotic performance of algorithms.
Syllabus: 
Unit NoTopics
Elementary Algorithms

Problems & instances, efficiency of algorithms, average & worst case analyses, elementary operation, reasons for analyzing efficiency

Asymptotic Notation

Big „oh‟ notation, other asymptotic notation, conditional asymptotic notation, asymptotic notation with several parameters, operations on asymptotic notation

Models of Computation

Random Access Machines, computational complexity of RAM programs, a stored program model, abstractions of RAM - straight-line programs, Turing Machines, relationship between Turing Machines and RAM.

Analysis of Algorithms

Analyzing control structures, barometer instructions, examples of their use, average-case analysis, amortized analysis

Solving Recurrences

Intelligent guesswork, homogeneous recurrences,  inhomogeneous recurrences, change of variable, range transformations, asymptotic recurrences, substitution method, iteration method, recurrence trees, master method & master theorem

Divide and Conquer

Characteristics, the general template, applications: binary search, merge sort,quick sort, matrix multiplication, counting inversion

Greedy Algorithms

General characteristics of greedy algorithms and examples, applications: Kruskal‟s and Prim‟s algorithms, shortest path problem, knapsack problem, scheduling problem

Dynamic Programming

General characteristics and examples, principle of optimality, applications: binomial coefficients, making change, knapsack problem, Floyd‟s algorithm, chained matrix multiplication. Approach using recursion, memory functions

Graph Algorithms

Depth-first search, breadth-first search, topological ordering & sorting, backtracking, application of backtracking: knapsack problem. Branch & bound, application: the assignment problem, general considerations

Computational Complexity

Introduction, information-theoretic arguments: complexity and sorting, complexity and algorithmic, introduction to NP completeness, the classes P and NP, polynomial reductions, NP complete problems

Reference Books: 
Name: 
Fundamentals of Algorithmic
Author: 
Brassard
Bratley
Publication: 
Prentice Hall of India
Name: 
Introduction to Algorithms by Cormen
Author: 
Leiserson
Rivest
Publication: 
Prentice Hall of India
Name: 
Fundamentals of computer algorithms
Author: 
Ellis Horowitz
Sartaj Sahni
Publication: 
Computer Science Press
Syllabus PDF: 
AttachmentSize
PDF icon 5th Algorithm Analysis & Design.pdf110.31 KB
branch: 
CBA
BDA
MA
Course: 
2014
Stream: 
B.Tech