Teaching Calendar

Currently Teaching

MCS 312: Special Topics in Theoretical Computer Science
(NP Completeness and Approximation Algorithms)
Syllabus

Introduction to NP Completeness and Approximation.
Problems from first principle: Satisfiability SAT, 3SAT.
Graphs: Clique, Covering, Graph Partitioning, Subgraph problem, Graph Isomorphism, Graph Coloring, Hamiltonian Cycle Problem, TSP.
Network Design Problems: Steiner tree, Spanning Trees, Cuts and Connectivity, Routing and Flow Problems.
Sets and Partitions: Set partition and Covering, Subset sum.
NP-hard problems: Clustering Problems like k-means clustering, co-clustering, connected kmeans clustering. More new problems as they are added to the class of NPC or NPH.
Approximation algorithms for the above problems.

References

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences), 1979.
Teofilo F. Gonzalez, Handbook of NP-Completeness: Theory and Applications, 2009.
Vijay V. Vazirani, Springer-Verlag, Approximation Algorithms, France, 2006.
Teofilo F. Gonzalez, Handbook of Approximation Algorithms and Metaheuristics (Chapman & Hall/Crc Computer and Information Science Series), 2007.
Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali, Linear Programming and Network Flows by 2004.
Part of the course will be covered by research papers.

Lecture Notes of 2012

Introduction to NP

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
MCA 204: Data Communication and Computer Networks