Credits: 3 (3-0-0)
Description
Introduction, data structures for combinatorial optimization: heaps, union-find, Fibonacci heaps, dynamic trees, dynamic graph structure; Asymptotic analysis; Divide & conquer and graph algorithms: Graph search: Breadth first, depth first, topological sorting, Fast Fourier Transform, Matrix Multiplication, Shortest path algorithms; Additional Data Structures: Suffix trees & string matching, Splay trees & amortized analysis; Advanced algorithmic design techniques: Dynamic programming (edit distance, chains of matrix multiplication, etc.), Network flow and its use for solving problems; Linear and integer programming, NP-completeness, Randomized algorithms (hashing & global minimum cut), Approximation Algorithms; Object oriented Software design, Design of Dependable Software.