Analysis and Design of Algorithms

Objectives: Main objective of the course is to provide an understanding of the techniques used in analysis of algorithms. Students will be able to evaluate a given algorithm in terms of its correctness and efficiency and choose appropriate algorithm for a specific application.

Contents: Algorithms characteristics, introduction to algorithm analysis; Types of analysis: empirical, analytical analysis of algorithms; Asymptotic behavior of algorithms; Simple recurrence relations and their solution; Analysis of searching algorithms; analysis of sorting algorithm; analysis of hashing techniques; Analysis of tree algorithms; analysis of graph algorithms: graph traversals, finding minimal spanning tree(Prim's & Kruskal's algorithms), shortest path finding algorithms (Dijkstra's algorithm, Floyd-Warshall algorithm); analysis of string matching algorithms; Complexity theory: intractability, polynomial time algorithms, decision and optimization problems, NP-Complete problems.