Design & Analysis of Algorithms Syllabus

A Hunt for Reaching Horizon of Science

Syllabus

UNIT-I

 

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.

 

UNIT-II

 

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.

 

 

UNIT-III

 

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.

UNIT-IV

 

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

 

UNIT-V

 

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
Perspective

 

 

 

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.