**OSMANIA UNIVERSITY**

** **

*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**:

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

**References**:

- Anany Levitin,
“Introduction to the Design and Analysis of Algorithms”, 2003, Pearson
Education.
- Aho, Hopcroft and
Ullman: “The Design and Analysis of Computer Algorithms”, Pearson
Education, 2000.
- Thomas H. Cormen,
Charles E. Leiserson, Ronald L. Rives, C. Stein: “Inroduction to
Algorithms:, 2
^{nd}edition, Prentice Hall of India.