Instruction                                                       4    Periods per week

Duration of University Examination             3      Hours

University Examination                                 80    Marks

Sessional                                                         20    Marks















Introduction &     Elementary data structures:



  Order notation,   Analysis of algorithms,  review of elementary data structures-




Heaps and Heap sort,  Hashing,  Sets representation,    UNION-FIND. 













Divide and Conquer:


The general method,   binary search,  finding maximum and minimum,



Merge sort ,   quick sort and   selection.


Greedy method:  Knapsack problem,   Optimal storage on tapes,




 Job sequencing with deadlines, Optimal merge patterns,   Minimum spanning trees  and




      Single source shortest paths.











Dynamic programming and  traversal techniques: Multistage graphs



          All pairs shortest paths,     Optimal binary search trees,


0/1 knapsack,  Reliability design, Traveling salesman problem,

  Biconnected components and depth first search.













Backtracking and branch and bound: 8-Queens problem,


Graph coloring,  Hamiltonian cycles, Knapsack problem, 0/1 Knapsack problem,



Traveling salesman problem, Lower bound theory.












NP-hard and NP-completeness: Basic concepts,

  Cook’s theorem, NP-hard graph problems and scheduling problems,




NP-hard code generation problems.  Decision problem. Node covering problem.







Suggested reading:




  1. Horowitz E., Sahni S: “Fundamentals of Computer Algorithms”, Galgotia publications, 1984.




  1. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, 2003, Pearson Education.



  1. Aho, Hopcroft and Ullman: “The Design and Analysis of Computer Algorithms”, Pearson Education, 2000.





  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: “Inroduction to Algorithms:, 2nd edition, Prentice Hall of India.