AIDS303/AIML303
Design and Analysis of Algorithms
B.Tech (Artificial Intelligence & Machine Learning) • Semester 5
Overview
This course is designed to enable the student to design and analyze algorithms for the problems. This course covers basic strategies of algorithm design: top-down design, divide and conquer, asymptotic costs, applications to sorting and searching, matrix algorithms, shortest-path and spanning tree problems, dynamic programming, greedy algorithms and graph algorithms.
Course Syllabus
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.