Algorithm Analysis & Design

Learning Outcomes:
After learning the course the students should be able to
• Analyse the asymptotic performance of algorithms.
• 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.
Syllabus:
Unit NoTopics
1
Introduction to Algorithms and Asymptotic Natations

Requirement of algorithms, Why to analyse algorithms, Problems & instances, efficiency of algorithms, time and space complexity,  average & worst case analyses, Big ‘oh’ notation, other asymptotic notation, conditional asymptotic notation, asymptotic notation with several parameters, operations on asymptotic notation

2

Analysis of Algorithms

Types of algorithms: Iterative v/s Recursive, analysing control structures, barometer instructions, examples of their use, average-case analysis, amortized analysis, Basic sorting algorithms and analysis: Bubble sort, Insertion sort, Selection sort, Heap sort and priority queue.

3
Solving Recurrences

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

4
Divide and Conquer

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

5
Greedy Algotithms

General characteristics of greedy algorithms and examples, applications: Kruskal’s and Prim’s algorithms, introduction to shortest path problem variants, single source shortest path problem, knapsack problem, scheduling problem.

6
Dynamic Programming

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

7
Graph Algorithams

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

8
Introduction to Computiational Complexity

P and NP problems, NP Hard and NP Completeness, SAT problem, Traveling Salesman Problem.

Text Books:
Name :
Introduction to Algorithms
Author:
by Cormen, Leiserson, Rivest
Publication:
Prentice Hall of India
Reference Books:
Name:
Fundamentals of Algorithms
Author:
by Brassard &Bratley
Publication:
Prentice Hall of India
Name:
Fundamentals of computer algorithms
Author:
Ellis Horowitz
SartajSahni
Publication:
Computer Science Press
Name:
Design and Analysis of Algorithms
Publication:
Pearson.
Syllabus PDF:
AttachmentSize
193.32 KB
branch:
CBA
BDA
MA
Course:
2018
Stream:
B.Tech