Design & Analysis of Algorithms Syllabus

A Hunt for Reaching Horizon of Science




Introduction, Algorithm Specification, Performance analysis, Space Complexity, Time Complexity, Asymptotic Notation(O,Omega,Theta), Practical Complexities, Performance Measurement, Review of elementary data structure- Heap and Heap Sort, Hashing, Set representation. UNION, FIND.




Divide-and Conquer: The general method, finding maximum 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.





Dynamic Programming And Traversal Technique: Multistage graph, All Pair Shortest Path, Optimal Binary Search trees,0/1 Knapsack, Reliability Design, Traveling Salesman Problem, Bi connected Components and Depth First Search.



Backtracking and Branch and Bounds: 8-Queens Problem, Graph Coloring Hamilton cycle, Knapsack Problem, 0/1 Knapsack Problem, Traveling salesperson problem, Lower-Bound Theory.




NP-Hard and NP-Completeness: Basic concepts, cook’s theorem, NP-hard graph problems and scheduling problem, NP-hard code generation
Logic Programming Concepts, Prolog, Theoretical Foundations, Logic Programming in




problems, Clique Decision problem, Node covering decision, Scheduling problem, NP hard code generation problem.


Suggested Reading:


1.Horowitz E. Sahani S: “Fundamentals of Computer Algorithm”,
Galgotia Publications.
2.Anany Levitin, “Introduction to the Design & Analysis, of Algorithms”, Pearson Education, 2000.

3.Aho, Hopcroft, Ulman, “The Design and Analysis of ComputerAlgorithm”, Pearson Education, 2000.

4.Parag H. Dave, Himanshu B. Dave “Design and Analysis ofAlgorithms” Pearson Education, 2008.