Unit 1

Father of Algorithm, What is Algorithm, Need of an algorithm, Algorithm Vs Program, Good Algorithm, Analysis of Algorithm, Comparison of running time, Asymptotic notation, Recurrence relation, Subtitution method, Iterative method, Recurrence Tree Method, Master Theorem, Extended Master Theorem.

Unit 2

Sorting:- Type of Sorting, Bubble Sort, Selection Sort, Insertion Sort, Binary Insertion Sort, Shell Sort, Quick Sort, Merge Sort, Heap, Heap Sort.Sorting in Linear Time:- Counting Sort, Radix Sort, Bucket Sort.

Unit 3

Advance Data Structure:- Binary Search Tree, AVL Tree, Red-Black Tree, B-Tree, B+ Tree, Binomial Tree, Binomial Heap, Fibonacci Heap, Trie, Skip List.

Unit 4

Divide & Conquer:- Matrix Multiplication, Strassen’s Multiplication, Convex Hull, Searching: Linear Search, Sentinel linear search, Binary Search, Ternary Search, Jump Search, Interpolation Search, Exponential Search, Fibonacci Search, The Ubiquitous Binary Search

Unit 5

Greedy Method:- Optimal Reliability Allocation, Activity Selection Problem, Huffman Code, Job Sequencing problem, Coin Change problem, Fractional Knapsack, Minimum Spanning Tree:- Prim’s Algorithm, Kruskal’s Algorithm, Single Source Shortest Path:- Dijkstra’s and Bellman Ford Algorithm, Trees & Graph – BFS, DFS. Topological Sort.

Unit 6

Dynamic Programming:- All Pair Shortest Path – Warshal’s and Floyd’s Algorithms, 0/1 Knapsack Problem, Subset Sum Problem, LCS, Matrix Chain Multiplication, Resource Allocation Problem. Backtracking, Branch & Bound, Travelling Salesman Problem, Graph Coloring, N-Queen Problem, Hamiltonian Cycles.

Unit 7

Algebric Computation, Fast Fourier Transform, String Matching, Theory of NP-Completeness, Approximation Algorithm, Randomized Algorithm.