Syllabus  |   Lectures  |   Downloads  |   FAQ  |   Ask a question  |  
Course Co-ordinated by IIT Kanpur
Coordinators
 

 

Download Syllabus in PDF format



Untitled Document
 

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.

 
 

Data-structures.


  1. Cormen, Leiserson, Rivest, "Introduction to Algorithms", McGraw Hill.

  2. Aho, Hopcroft, Ullman, " The Design and Analysis of Computer Algorithms", Addison Wesley.



Important: Please enable javascript in your browser and download Adobe Flash player to view this site
Site Maintained by Web Studio, IIT Madras. Contact Webmaster: nptel@iitm.ac.in