Course

Unit 1

Introduction: Problem solving — adding 2 n-bit numbers, multiplication as repeated addition. Running time analysis — recall of asymptotic notation, big-oh, theta, big-omega, and introduce little-oh and little-omega. Worst case and average case (12 hrs)

Unit 2

Divide and Conquer Analysis of: Binary Search Merge sort Quick sort Heap Sort Multiplication of Large Integers Closest-Pair and Convex Hull Problems. (10 hrs)

Unit 3

Greedy Technique General Method Analysis of: fractional Knapsack Problem Job Sequencing with Deadlines MST Single Source shortest path. Dynamic Programming General Method Analysis of: Multistage Graphs, all pair shortest path, Matrix chain multiplication,0/1 Knapsack problem, Travelling Salesman Problem (12 hrs)

Unit 4

Backtracking General Method Analysis of: 8 Queens Problem Sum of Subsets Graph Coloring Hamiltonian Cycles Knapsack Problem.Branch and Bound General Method Analysis of: 0/1 Knap sack problem Travelling salesperson problem LC Branch and Bound FIFO Branch and Bound (12 hrs)

Unit 5

String Matching: Boyer Moore KMP Rabin Karp. NP-Hard and NP-Complete Problems: Basic concepts, non-deterministic algorithms, NP-hard and NP-complete classes,Cooks theorem. (10 hrs)

Text Books / References

Text Book

1. Ellitz Horowitz, Sarataj Sahini, Senguthevar Rajasekaran, Computer Algorithms, 2^ndedition, Silicon Press, 2008.
2. Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein, MIT Press, Third Edition, 2009.
3. Michael T. Goodrich & Roberto Tamassia, Data Structures and Algorithms in Python, Wiley, 2021, 6^th

Reference Book:

1. Alfred V Aho, John E Hopcroft, Jeffrey D Ullman. Data Structures & Algorithms, Pearson Publishers, 2002
2. Narasimha Karumanchi, “Data and Algorithms Made Easy”, Career Monk publications, 2023.