Design and Analysis of Algorithms

UNIT I 

Introduction to Algorithms: Time Complexity and Space Complexity, Asymptotic analysis, Growth rates, some common bounds (constant, logarithmic, linear, polynomial, exponential), 

Complexity Analysis techniques: Master theorem, Substitution Method, Iteration Method, Time complexity of Recursive algorithms. art of problem-solving and decision making, role of data structure in algorithm design, Basic algorithmic structures of problem-solving and optimization algorithms, constraints, solution space, and feasible reasons, and representation of solution space. 

Sorting and searching algorithms: Selection sort, bubble sort, insertion sort, Sorting in linear time, count sort, Linear search.

UNIT II

Divide and Conquer Algorithms: Overview of Divide and Conquer algorithms, Quick sort, Merge sort, Heap sort, Binary search, Matrix Multiplication, Convex hull and Searching, Closest Pair of Points.

Greedy Algorithms: Greedy methods with examples, Huffman Coding, Knapsack, Minimum cost Spanning trees – Prim’s and Kruskal’s algorithms, Single source shortest paths – Dijkstra’s and Bellman Ford algorithms.

UNIT III

Dynamic programming: Dynamic programming with examples such as Knapsack, shortest path in graph All pair shortest paths –Warshal’s and Floyd’s algorithms, Resource allocation problem. 

Backtracking, Branch and Bound with examples such as Traveling Salesman Problem, longest common sequence, n-Queen Problem.

UNIT IV

Graph Algorithms: Graphs and their Representations, Graph Traversal Techniques: Breadth First Search (BFS) and Depth First Search (DFS), Applications of BFS and DFS, Bipartite graphs. Graph Coloring, Hamiltonian Cycles and Sum of subsets. 

Computational complexity: Problem classes: P, NP, NP-complete, NP-hard. Reduction. The satisfiability problem, vertex cover, independent set and clique problems Cook’s theorem. Examples of NP-complete problems.

Textbooks:

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein, “Introduction to Algorithms”,PHI ,4th ed.
2. Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++”, Third Edition, Pearson Education, 2006

Reference Books:

1. Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, “Fundamentals of Computer Algorithms”, Second Edition, Universities Press, 2011.
2. Anany Levitin. “Introduction to the Design and Analysis of Algorithms”, Pearson.