This course focuses on the study of advanced data structures and algorithms for solving problems efficiently and their theoretical behavior. The course also includes study of network flow algorithms, NP completeness and backtracking.
At the end of the course, students should be able to:
Advanced Data Structures: Skip Lists, Red-Black trees, Splay Trees, Mergeable heaps (Fibonacci heaps), DS for sets – Union-Find Data Structure, Dynamic Tables, Dictionaries, Data structures for strings – Tries, Suffix trees.
Divide and Conquer: Counting Inversions, Closest pair of points, Integer Multiplication.
Greedy Algorithm: Interval Scheduling, Huffman Code, Correctness and Analysis.
Dynamic Programming: Segmented Least Squares, Shortest Paths, Negative Cycles in Graphs.
Network Flows: Max-flow problem, Ford Fulkerson Algorithm, Maximum flows and Minimum Cuts in a network, Bipartite Matching.
NP Completeness: Polynomial time reductions, Efficient Certification and Definition of NP, NP Complete problems, Sequencing problems, Partitioning problems, co-NP and asymmetry of NP. Backtracking: Constructing All Subsets, Constructing All Permutations, Constructing All Paths in a Graph.