OSMANIA UNIVERSITY

 

COURSE MCA II/III-2007

 

 
 
 
 
 
 
 
 
 

 


                 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.

 

 

References:

  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.