C. Design and Analysis of Algorithms

Course Code: MTH10304

C. Design and Analysis of Algorithms

UNIT I : INTRODUCTION

Mathematical preliminaries – Complexity Analysis – Asymptotic Notations – Average and worst case analysis – Stepwise refinement. Sorting : Bubble sort – Bucket sort – Heap sort – Radix sort. Searching : Sequential search – Binary search

UNIT II : DIVIDE AND CONQUER METHOD AND GREEDY METHOD

Divide and Conquer – General method – Quick sort – Finding maximum and minimum – Strassen’s matrix multiplication. Greedy method – General method – Tree vertex splitting problem – Job sequencing with deadlines

UNIT III : DYNAMIC PROGRAMMING Dynamic Programming - General method - Multistage graph – String editing. Backtracking – Basics – 8 Queen problem – Sum of subset problem. Branch and bound – Basics – Travelling Salesperson problem

UNIT IV : GRAPH ALGORITHM

Minimum cost spanning tree algorithms – Shortest path algorithms – Transitive closure – Topological ordering – Bi-connected and strongly connected components – R-connected graph – Even’s Kleitman’s algorithms

UNIT V : NP-HARD AND NP-COMPLETE PROBLEMS

NP complete & NP hard problems – Approximation algorithms – Fast fourier transform and algorithm – Lower Bound Trees – Oracle and Adversary arguments.

TEXT BOOK

1.  Horowitz E, Sahni .S & Rajasekar S– “Fundamentals of Computer Algorithms” – Galgotia Publications – 1998

REFERENCES:

1.  Sara Base – “ Computer Algorithms : Introduction to Design and Analysis” – Addison Wesley – 1998.

2.  Algorithms and Data Structures in C++ - Ammerald-Wiley Publications-2003.