Sr. No.

Content

Total 
Weightage 

Basics of Algorithms and Mathematics:

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

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

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.

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.

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.

Exploring Graphs:

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

Backtracking and Branch and Bound:

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

String Matching:

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

Introduction to NP-Completeness:

The class P and NP, Polynomial reduction, NP- Completeness Problem,
NP-Hard Problems. Travelling Salesman problem, Hamiltonian problem,
Approximation algorithms, Randomized algorithms, Class of
problems beyond NP – P SPACE