Course Title : Computer Algorithm
Course Code: : CS311
Total Credits : 03+01=04
Unit 1 Introduction
What is algorithm, Algorithm Specification, Performance Analysis, heap.
Unit 2 Divide and Conquer
The general method, Binary search, Finding the maximum and minimum, Merge sort, Quick sort, and analysis of these algorithms.
Unit 3 The Greedy Method
The general method, Knapsack problem, Job sequencing with deadlines, minimum-cost spanning trees – Prim’s and Kruskal’s Algorithms, Optimal storage on tapes, Single source shortest paths.
Unit 4 Dynamic Programming
The general method, Multistage graphs, All pair shortest paths, Optimal binary search trees, 0/1 knapsack, Reliability design, Traveling Sales person problem.
Unit 5 Backtracking
The general method, 8-queen problem, sum of subsets, Knapsack Problem, Hamiltonian Cycle, and Graph Coloring.
Unit 6 Basic Traversal and Search Techniques and Polynomial Problems
Techniques for Binary Trees, Game Tree; Techniques for Graphs – Breadth First Search & Traversal, Depth First Search & Traversal, AND/OR graphs; Connected components and Spanning Trees; Bi-connected components and depth first search. NP Hard and NP Complete.
Text Books :
1. “Fundamentals of Computer Algorithms”, Horowitz, Sahni and Rajasekaran, Galgotia Publications.
Reference Books :
1. “Fundamentals of Computer Algorithms”, Horowitz and Sahni, Galgotia Publishers.
2. “Design and Analysis of Algorithms”, Aho, Hopfcraft and Ullman, Addison Wesley.
3. “Introduction to Algorithms”, Thomas Cormen, PHI Publication.
4. “Introduction to Design and Analysis of Algorithm”, Goodman, McGraw Hill.