Algorithm Design and Analysis- II (CSC504)
11 units: Introduction, Some Advanced Data Structures, Disjoint Set Forests, Graph Algorithms, Randomized Algorithm · L-T-P 3-1-0.
Detailed syllabus
Unit 1: Introduction (1 hours)
Introduction.
Unit 2: Some Advanced Data Structures (9 hours)
Augmented Data Structures, Count-min-Sketch, Tries and Suffix Trees, KD-Tree, Range Minimum Queries, Splay Trees, Fusion Trees and Euler Tour Trees.
Unit 3: Disjoint Set Forests (2 hours)
Disjoint Set Forests, Overview of Fibonacci heap and Binomial heap.
Unit 4: Graph Algorithms (7 hours)
Depth First Search, Breadth First Search, Dijkstra's Single Source Shortest Path, All Pair Shortest Path, Bellman Ford, Minimum Spanning Tree (Prim's and Kruskal's algorithm), Strongly Connected Components.
Unit 5: Randomized Algorithm (3 hours)
Las Vegas and Monte Carlo; Randomized Quick Sort algorithm and Min Cut problem.
Unit 6: Reducibility between problems and NP-completeness (6 hours)
Different class of Problems (P, NP, NP-Hard, NP-Complete), Discussion of different NP-complete problems like satisfiability, clique, vertex cover, independent set, Hamiltonian cycle, set cover, dominating set problem.
Unit 7: Approximation Algorithm (6 hours)
Approximation ratio for maximization problem and minimization problem, Constant ratio approximation algorithms for metric travelling salesperson problem (TSP) and vertex cover problem, log n ratio approximation algorithm for Set Cover problem.
Unit 8: Backtracking Method (2 hours)
Backtracking Method, Branch and Bound Method.
Unit 9: Learning Algorithm (1 hours)
Overview of Multiplicative Weight Update with its analysis.
Unit 10: Maximum Flow (3 hours)
Flow Networks and the Ford-Fulkerson method. Application of flow network: bipartite matching.
Unit 11: String Matching Algorithms (2 hours)
Rabin-Karp and Knuth-Morris-Pratt.
Source: official document