Design and Analysis of Algorithms ( 17CI08 )

Pre-requisites : Knowledge of Programming, Discrete Mathematics and Data Structures.

Course Educational Objectives:

Students undergoing this course are expected to:

Identify the fundamental concepts of various algorithm design techniques. Make the students

familiar to conduct performance evaluation of algorithms. Expertise the students with the various

existing algorithm design techniques. Motivate the students to design new algorithms for various

problems.

Course Outcomes: At the end of the course, the student shall be able to:

CO1: Identify the basic properties and analysis methods of algorithms and design divide and conquer paradigm for solving a few example problems and analyze them.

CO2: Design Greedy algorithms for knapsack problem, minimum cost spanning tree,single source shortest path problem and analyze them.

CO3: Apply dynamic programming paradigm to solve travelling sales person problem,0/1 knapsack problem,Optimal binary search tree.

CO4: Apply Backtracking search methods on state space trees for few example problems.

CO5: Analyse branch and Bound search methods through problems such as 0/1 knapsack problem,Travelling sales personn problem.

UNIT - I

Introduction: Algorithm definition, Specifications, Performance Analysis- Time Complexity, Space Complexity. Asymptotic Notations-Big-Oh, Omega, Theta. Divide and Conquer: General Method, Binary Search, Finding Maximum and Minimum, Merge Sort, Quick sort.

UNIT - II

The Greedy Method – General Method, Knapsack Problem, Job sequencing with deadlines, Minimum-cost spanning trees, Optimal storage on tapes, Optimal merge pattern, Single source shortest paths.

UNIT - III

Dynamic Programming - General method, Multistage graph, All pairs shortest path, Single Source Shortest path, Optimal Binary search trees, 0/1 Knapsack, Reliability design, the traveling salesman problem.

UNIT - IV

Back tracking - The General Method, The 8-Queens Problem, Sum of subsets, Graph Colouring, Hamiltonian cycles.

UNIT-V

Branch and Bound – General method, Travelling salesperson Problem, 0/1 Knapsack problem - LC Branch and Bound solution, FIFO Branch and Bound solution.

TEXT BOOKS

Ellis Horowitz, Sartaj Sahni, ―Fundamentals of Computer Algorithms”, Galgotia Publications

REFERENCES

1. Mark Allen Weiss, ―Data Structures and Algorithm Analysis in C++‖, Pearson, 3/e ,2007.

2. Aho, Hopcroft & Ullman, ―The Design and Analysis of Computer Algorithms”, Addison Wesley publications.

3. Thomas H.Corman et al, ―Introduction to Algorithms”, PHI.

4. Anany Levitin, ―Introduction to the Design and Analysis of Algorithms‖, PEA

5. P. H. Dave, H. B. Dave, ―Design and Analysis of Algorithms‖, Pearson Education, 2008.