This course assumes the knowledge of data-structures.

It also assumes the
knowledge big-O notation and the concept of time and space complexity of an algorithm.

The
course also will not introduce divide and conquer, dynamic programming, and greedy paradigms.

The course will discuss eff cient algorithms from a large number of domains.

__Contents__

Graph
algorithm: search algorithms, computation of strongly connected components, shortest distance
algorithms, minimum spanning tree algorithms.

Network-flow algorithm: Ford-Fulkerson method;
pref ow-push algorithm;

Geometric algorithm: convex-hull computation, line-segment intersection
computation, closest-pair computation;

String matching: Rabin Karp algorithm, Knuth-Morris-Pratt
algorithm, Boyer-Moore algorithm;

Matrix algorithms: Strassen’s multiplication algorithm, LU
decomposition, inverse computation; Polynomial computation algorithms: multiplication using
DFT, division;

Number theoretic algorithms: division, solution of modular linear equation,
primality testing.