MCA12

Design And Analysis of Algorithm
Year / Semester: 
3rd Semester

Unit 1 : Introduction to Algorithms
Algorithm, analysis, time complexity and space complexity, O-notation, Omega notation and Theta notation, Heaps and Heap sort, Sets and disjoint set, union and find algorithms. Sorting in linear time.

Unit 2 : Divide and Conquer
Divide and Conquer: General Strategy, Exponentiation. Binary Search, Quick Sort and Merge Sort

Unit 3 : Greedy Method
General Strategy, Knapsack problem, Job sequencing with Deadlines, Optimal merge patterns, Minimal Spanning Trees and Dijkstra’s algorithm.

Unit 4 : Dynamic Programming
General Strategy, Multistage graphs, OBST, 0/1 Knapsack, Traveling Salesperson Problem, Flow Shop Scheduling

Unit 5 : Backtracking
Backtracking: General Strategy, 8 Queen’s problem, Graph Coloring, Hamiltonian Cycles,    0/1 Knapsack

Unit 6 : Branch and Bound
General Strategy, 0/1 Knapsack, Traveling Salesperson Problem

Unit 7 : NP-Hard and NP-Complete Problems
Basic concepts, non-deterministics algorithms, NP-HARD and NP-COMPLETE classes, COOKS theorem

Suggested Readings: 

1. Horowitz Sahani, “ Fundamentals of Computer Algorithms”, Golgotia
2. Coremen Leiserson etal, “ Introduction to Algorithms”, PHI
3. Brassard Bratley, “Fundamental of Algorithms”, PHI
4. M T Goodrich etal, “Algorithms Design”, John Wiley
4. A V Aho etal, “The Design and analysis of Algorithms”, Pearson Education