Computer Science and Engineering
Introduction: Basic strategies of Algorithm design, Time and space analysis of algorithms, Average, best and worst case analysis and analysis techniques, different notations.
Divide and conquer: Linear/Binary search, sorting methods strassen’s matrix multiplication method.
Greedy method: Activity selection, Huffman coding, Knapsack problem, job scheduling with deadlines, spanning trees, prim and kruskal’s algorithms, single-source shortest paths.
Dynamic programming: multistage graphs, travelling salesman problem, All pairs shortest paths. Matrix chain multiplication, longest common subsequences and optional polygon triangulation problems.
Backtracking: 8 queens problem, sum of subsets, graph colouring problem, Hamilton cycles.
Graph algorithms: depth first search, breadth first search, strongly connected, cut-set algorithms.
Network flow algorithms: Max flow, min cut algorithms, sink-source.
Branch and bound: Lest cost search, 15-puzzle problem, Knapsack problem, Travelling salesman problem.
NP vs. P: The spaces P and NP, the NP-complete problems, Cook’s theorem, NP-Hard problems.
1. H Cormen, E. Leiserson and L. Rives : Introduction to Algorithms
2. E. Horowitz and S. Sahni : Fundamentals of Computer Algorithms.
3. Goodman : Introduction to Design and Analysis of Algorithms
4. Robert Sedgewick : Algorithms.