Design and Analysis of Algorithm

Basics of Algorithms and Mathematics

What is an algorithm?, Mathematics for Algorithmic Sets, Functions and Relations, Vectors and Matrices, Linear Inequalities and Linear Equations.

2

Teaching Hrs

2

Module Weightage

Analysis of Algorithm

The efficient algorithm, Average, Best and worst case analysis, Amortized analysis , Asymptotic Notations, Analyzing control statement, Loop invariant and the correctness of the algorithm, Sorting Algorithms and analysis: Bubble sort, Selection sort, Insertion sort, Shell sort Heap sort, Sorting in linear time : Bucket sort, Radix sort and Counting sort

8

Teaching Hrs

10

Module Weightage

Divide and Conquer Algorithm

Introduction, Recurrence and different methods to solve recurrence, Multiplying large Integers Problem, Problem Solving using divide and conquer algorithm – Binary Search, Max-Min problem, Sorting (Merge Sort, Quick Sort), Matrix Multiplication, Exponential.

6

Teaching Hrs

15

Module Weightage

Dynamic Programming

Introduction, The Principle of Optimality, Problem Solving using Dynamic Programming – Calculating the Binomial Coefficient, Making Change Problem, Assembly Line-Scheduling, Knapsack problem, All Points Shortest path, Matrix chain multiplication, Longest Common Subsequence.

5

Teaching Hrs

20

Module Weightage

Greedy Algorithm

General Characteristics of greedy algorithms, Problem solving using Greedy Algorithm – Activity selection problem, Elements of Greedy Strategy, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm), Graphs: Shortest paths, The Knapsack Problem, Job Scheduling Problem, Huffman code.

5

Teaching Hrs

20

Module Weightage

Exploring Graphs

An introduction using graphs and games, Undirected Graph, Directed Graph, Traversing Graphs, Depth First Search, Breath First Search, Topological sort, Connected components,

4

Teaching Hrs

10

Module Weightage

Backtracking and Branch and Bound

Introduction, The Eight queens problem , Knapsack problem, Travelling Salesman problem, Minimax principle

3

Teaching Hrs

5

Module Weightage

String Matching

Introduction, The naive string matching algorithm, The Rabin-Karp algorithm, String Matching with finite automata, The Knuth-Morris-Pratt algorithm.

3

Teaching Hrs

8

Module Weightage

Introduction to NP-Completeness

The class P and NP, Polynomial reduction, NP- Completeness Problem, NP-Hard Problems. Travelling Salesman problem, Hamiltonian problem, Approximation algorithms

5

Teaching Hrs

10

Module Weightage