STUDY - Design Methods and Analysis of Algorithms
Elementary Data Structures, Basic Computational Models.
Simple Algorithms. Analyzing Algorithms, Asymptotic Notation, Recurrence relations.
STUDY - Design Methods :
General Consideration, Algorithm design paradigms and representative
problems: Divide and Conquer (Binary search, Merge Sort, Quick Sort, Arithmetic with Large integers,
etc.), Greedy Method (Minimal Spanning Tree, Shortest Paths, Knapsack, etc.), Dynamic Programming
(Chained Matrix Multiplication, Optimal Storage on Tapes, Shortest Paths, Optimal Search Trees, etc.),
Backtracking (8-queens problem, Graph Colouring, Hamiltonian Cycles, etc.), Branch and Bound (0/1
Knapsack problem, Travelling Salesperson, etc.), Approximation (Graph Colouring, Task Scheduling, Bin
Packing, etc.), Probabilistic Algorithms (Numerical Integration, Primality Testing, etc.).
STUDY - Graph Algorithms:
BFS, DFS and its applications.
Polynomial Evaluation and Interpolation, Fast Fourier transforms.
STUDY - Intractable Problems :
Basic Concepts, Nondeterministic Algorithms, NP Completeness, Cook's
Theorem, Examples of NP-Hard and NP-Complete problems. Problem Reduction.
Lower Bound Techniques: Comparison tree, Reduction, Adversary argument.