Design and Analysis of Algorithms (DAA) OU Syllabus

3.8
(49)

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 operations.

UNIT–II
Divide-and-Conquer Method: The general method, Binary search, Finding maximum and minimum, Merge sort, Quick sort and Selection sort.
Greedy Method: Knapsack problem, Optimal storage on tapes, Job sequencing with deadlines, Optimal merge pattern, Minimum spanning trees, Single source shortest path.

UNIT-III
Dynamic programming method and traversal techniques: Multi-stage graphs, All pairs shortest paths, Optimal binary search tress, 0/1 Knapsack problem, Reliability design, Traveling salesman problem, Game trees, Biconnected components and Depth first search.

UNIT-IV
Backtracking and branch-and-bound methods Hamiltonian cycles, Knapsack problem and problem.
Lower-bound Theory methods: N-queens problem, Graph coloring, 0/1 Knapsack problem, Traveling sales person

UNIT–V
NP-hard and NP-complete problems: Basic concepts, Non-deterministic algorithms, NP-hard graph problems and scheduling problems, NP-hard code generation problem, Decision problem, Node cover problem

Suggested Reading:
1. Horowitz E, SahniS, Fundamentals of Computer Algorithms, 2nd Edition, Universities Press, 2007
2. AhoA.V.HopcroftJ.E,UllmanJ.D, TheDesignandAnalysisofComputerAlgorithms, Addison Wesley, 1974
3. Michael T. Goodrich, Roberto Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley & Sons,2002

How useful was this post?

Click on a star to rate it!

Average rating 3.8 / 5. Vote count: 49

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Leave a Comment

Scroll to Top