OSMANIA UNIVERSITY

 

COURSE CS355—MCA 2/3--2007

 

DESIGN AND ANALYSIS OF ALGORITHMS

 

Instruction                                                                               4          Periods per week

Duration of University Examination                                        3          Hours

University Examination                                                                       80         Marks

Sessional                                                                              20           Marks

 

 

UNIT – I

Introduction & Elementary data structures: Order notation, Analysis of algorithms, review of elementary data structures-Heaps and Heap sort, Hashing, Sets representation, UNION-FIND.

 

UNIT-II

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.

 

UNIT-III

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.

 

UNIT-IV

Backtracking and branch and bound: 8-Queens problem, Graph coloring, Hamiltonian cycles, Knapsack problem, 0/1 Knapsack problem, Traveling salesman problem, Lower bound theory.

 

UNIT-V

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.
  2. Aho, Hopcroft and Ullman: “The Design and Analysis of Computer Algorithms”, Pearson Education, 2000.
  3. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rives, C. Stein: “Inroduction to Algorithms:, 2nd edition, Prentice Hall of India.