Syllabus - ES2-2 Computer Algorithms

ES2-2 Computer Algorithms

( 5 Hours – 5 Credits)

Unit I

            Algorithms : Importance of developing efficient algorithms – Analysis – order Branch and Bound:Illustrating with 0/1 Knapsack. 

Unit II

            Divide and Conquer : Binary Search – Merge sort – divide and conquer approach – Quick Sort – Arithmetic with large numbers – When not to use divide and conquer. 

Unit III

            Dynamic Programming : Binomial coefficients – Floyds algorithm for shortest paths- Dynamic programming and optimization problems – chained matrix multiplication – Optimal binary search tree – The traveling salesperson problem. 

Unit IV

            Greedy Approach : Minimum spanning trees – Dijkstra’s algorithm for single source shortest path – scheduling – Huffman code. 

Unit V

            Backtracking: The Backtracking techniques – n Queens Problem – Monte carlo algorithm to estimate the efficiency of a backtracking algorithm –Sum of Subsets – Graph Colouring – Hamiltinian circuits. 

Text Book

            Foundations of Algorithms Using C++ Pseudocode,  Third edition,  Richard Neapolitan,  Kumarss Naimipour.  Narosa publication,  2004. 

Unit I              Chapters          1          (1.  1, 1.  2, 1.  3, 1.  4)

Unit II             Chapters          2          (2.  1, 2.  4, 2.  6)

Unit I              Chapters          3          (3.  1, 3.  2, 3.  3, 3.  4, 3.  5, 3.  6)

Unit I              Chapters          4          (4.  1, 4.  2, 4.  3, 4.  4)

Unit I              Chapters          5          (5.  1, 5.  2, 5.  3, 5.  4, 5.  5, 5.  6)

REFERENCE BOOK

            Fundamentals of computer algorithms ,  Ellis Horowitz and sartaj sahni ,  Galgotia book house Reprint 2005.