UNIT – I - Introduction

1.1 Introduction
1.2 Fundamentals of Analysis of Algorithm
1.2.1 Analysis of Framework
1.2.2 Measuring an input size
1.2.3 Units for measuring runtime
1.2.4 Worst case, Best case and Average case
1.2.5 Asymptotic Notations
1.3 An Example
1.4 Analysis of Linear Search
Questions

UNIT – II – Divide and Conquer, Greedy Method

2.1 Divide and Conquer
2.2 General Method – Divide and Conquer
2.2.1 Master theorem
2.2.2 Efficiency of Merge sort
2.3 Binary Search
2.3.1 Efficiency of Binary Search
2.4 Greedy Techniques
2.5 General Method – Greedy Method
2.5.1 Prim‘s Algorithm
2.6 Container Loading
2.6.1 Algorithm for Container Loading
2.7 Knapsack Problem
Questions

UNIT – III – Dynamic Programming

3.1 Introduction

3.2 General Method – Dynamic Programming
3.2.1 Pseudo code for Binomial Coefficient
3.3 Multistage Graphs
3.3.1 Pseudo code for Floyd‘s Algorithm
3.4 Optimal Binary Search trees
3.5 0/1 Knapsack Problem
3.6 Traveling Salesman Problem
Questions

UNIT – IV - Backtracking

4.1 Backtracking
4.1.1 General Method – Backtracking
State-Space tree
4.2 N-queens Problem
4.3 Subset- Sum problem
4.3.1 Pseudo code for Backtracking Algorithms
4.4 Graph Coloring
4.5 Hamiltonian circuit problem
4.6 Knapsack Problem
Questions

UNIT – V – Traversals, Branch & Bound

5.1 Graph Traversals, BFS
5.1.1 BFS Forest
5.1.2 Efficiency
5.1.3 Ordering of Vertices
5.1.4 Application of BFS
5.2 DFS
5.2.1 DFS Forest
5.2.2 DFS Algorithm
5.1.3 Application of DFS
5.3 Connected Component
5.3.1 Biconnected Components
5.4 Spanning Trees
5.4.1 Prim‘s Algorithm
5.4.2 Kruskal‘s Algorithm
5.5 Branch & Bound
5.6 General Methods – FIFO & LC
5.7 Knapsack Problem
5.8 NP Hard & NP Completeness
Questions