CBCGS [2017 - current]

CBGS [2013 - 2016]

Old [2000 - 2012]

## Topics with syllabus and resources

100.00 Introduction to Analysis of Algorithm

- Decision and analysis fundamentals
- Performance analysis , space and time complexity
- Growth of function – Big –Oh ,Omega , Theta notation
- Mathematical background for algorithm analysis
- Analysis of selection sort , insertion sort
- Randomized algorithms
- Recursive algorithms
- The substitution method
- Recursion tree method
- Master method

200.00 Divide and Conquer

- General method
- Binary search
- Finding minimum and maximum
- Merge sort analysis
- Quick sort analysis
- Strassen’s matrix multiplication
- The problem of multiplying long integers
- Constructing Tennis tournament

300.00 Greedy Method

- General Method
- Knapsack problem
- Job sequencing with deadlines
- Minimum cost spanning trees-Kruskal and prim’s algorithm
- Optimal storage on tapes
- Single source shortest path

400.00 Dynamic Programming

- General Method
- Multistage graphs
- All pair shortest path
- Single source shortest path
- Optimal binary search tree
- 0/1 knapsack
- Travelling salesman problem
- Flow shop scheduling

500.00 Backtracking

- General Method
- 8 queen problem (N-queen problem)
- Sum of subsets
- Graph coloring

600.00 String Matching Algorithms

- The naïve string matching Algorithms
- The Rabin Karp algorithm
- String matching with finite automata
- The knuth-Morris-Pratt algorithm
- Longest common subsequence algorithm

700.00 Branch and Bound

- General method
- 15 puzzle problem
- Travelling salesman problem