• Home
• About Me
• Teaching
• Research
• Publications
• Other Activities
• Codes

Teaching                                                                                                              Calendar

Currently Teaching

• MCA 301: Design and Analysis of Algorithms

• MCS 312: Special Topics in Theoretical Computer Science

Subjects Taught Previously

Undergraduate Level

• 1989 - 2002: Systems Analysis and Design, Computer System Architecture, Programming languages from COBOL, Pascal to C, Discrete Structures, Data Structures, Algorithms, Theory of Computation/ Automata Theory, Statistical Techniques

Postgraduate Level

• 2002 - till date: Systems Programming, Data Communication and Computer Networks, Design and Analysis of Algorithms, Algorithms in Bioinformatics, NP Completeness and Approximation Algorithms.

• MCS 101: Design and Analysis of Algorithms

MCS 101: Design and Analysis of Algorithms Syllabus Review of algorithm design techniques like Iterative Techniques and Divide & Conquer through Sorting, Searching and Selection problems. Review of Lower Bounding techniques: decision trees, adversary. String Processing: KMP, Boyre-Moore, Rabin Karp algorithms. Introduction to randomized algorithms: random numbers, randomized quick sort, randomly built binary search tree. Number Theoretic Algorithms: GCD, addition and multiplication of two large numbers, polynomial arithmetic, Fast-Fourier transforms. Advanced Techniques to analyze algorithms: Use and study advanced data structures unionfind ( Disjoint Set Structure), Fibonacci heaps. Graph algorithms: Matching and Flows. Parallel algorithms: Basic techniques for sorting, searching and merging in parallel. Geometric algorithms: Point location, Convex hulls and Voronoi diagrams. Complexity Theory: Classes P, NP, NP-Hard, NP Complete. Approximation Algorithms: Introduction through examples. References T.H. Cormen, C.E.Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms, McGraw-Hill, 2002. Sara Baase, Computer Algorithms: Introduction to Design and Analysis, Addison Wesley, 1999. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995. Teofilo F.Gonzalez, Handbook of NP-Completeness: Theory and Applications Chapman & Hall, 2009. Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag, France, 2006. S. Rajasekharan and John Reif, Handbook of Parallel Computing: Models, algorithms and applications, Chapman and Hall/CRC, 2007. Gareth A. Jones and Josephine M. Jones, Elementary Number Theory, Springer, 1998. F P Preparata and M I Shamos, Computational Geometry: An Introduction Springer, 1993. Lecture Notes of 2011 Lecture 1 - Introduction Lecture 2 - Review Lecture 3 - Review Lecture 4 - Adversary Lecture 5 - Correctness of Algorithms Lecture 6 - Expected Running Times and Randomized Algorithms Lecture 7 - String Matching Lecture 8 - Number Theoretic Problems Lecture 9 - Parallel Algorithms Lecture 10 - Network Flows Lecture 11 - NP-Completeness Lecture 12 - Approximation Algorithms Lecture 13 - Dynamic Programming Lecture 14 - Analysis of Graph Algorithms Grades Useful Links Karps's 21 NP-Complete Problems CS722 Karps's 21 NP-Complete Problems CS172 Some Lecture Notes of Previous Years Introduction Lecture 1 - Mathematical Induction: Review Growth Functions Lecture 2 - Solving Recurrences The Master Theorem Lecture 3 - Proving Correctness of Algorithms Lecture 4 - Comparison Sorting Lecture 5 - Lower Bounds Linear-Time Sorting Algorithms Lecture 6 - Selection Adversary Lecture 7 - Analysis Red-Black Trees Lecture 8 - NP-Completeness Previous Years Minors Minor I'10 Minor II'10 Minor I'09 Minor II'09 Minor I'07 Minor II'07 Minor I'06 Minor II'06 Minor I'05 Minor II'05

• MCA 204: Data Communication and Computer Networks