WITH EFFECT FROM THE ACADEMIC YEAR 2016 - 2017

CS 356

DESIGN AND ANALYSIS OF ALGORITHMS

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 Computer Algorithm", Pearson Education, 2000.

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