CS60023 Spring 2024-25 Approximation and Online Algorithms LTP 3-0-0, 3 credits, CSE 108, Ground Floor, CSE department.

CS60047 Autumn 2023-24 Advanced Graph Theory LTP 3-1-0, 4 credits

CS60064 Spring 2022-23 Computational Geometry LTP 3-0-0, 3 credits==> http://cse.iitkgp.ac.in/%7Espp/CS60064-2023.html

2022-23

CS60047 ADVANCED GRAPH THEORY L-T-P: 3-1-0, Credits: 4==>

Classes in CSE 108 (ground floor) at 10 am on Wednesdays, 9 am on Thursdays and 11 am on Fridays, Autumn semester 2022-23

http://cse.iitkgp.ac.in/~spp/CS60047_aut2022.html

Syllabus as in departmental webpage:

Basic Concepts: Graphs and digraphs, incidence and adjacency matrices, isomorphism, the automorphism group;

Trees: Equivalent definitions of trees and forests, Cayley’s formula, the Matrix-Tree theorem, minimum spanning trees;

Connectivity: Cut vertices, cut edges, bonds, the cycle space and the bond space, blocks, Menger’s theorem;

Paths and Cycles: Euler tours, Hamilton paths and cycles, theorems of Dirac, Ore, Bondy and Chvatal, girth, circumference, the Chinese Postman Problem, the Traveling Salesman problem, diameter and maximum degree, shortest paths;

Matchings: Berge’s Theorem, perfect matchings, Hall’s theorem, Tutte’s theorem, Konig’s theorem, Petersen’s theorem, algorithms for matching and weighted matching (in both bipartitie and general graphs), factors of graphs (decompositions of the complete graph), Tutte’s f-factor theorem; Extremal problems: Independent sets and covering numbers, Turan’s theorem, Ramsey theorems;

Colorings: Brooks theorem, the greedy algorithm, the Welsh-Powell bound, critical graphs, chromatic polynomials, girth and chromatic number, Vizing’s theorem;

Graphs on surfaces: Planar graphs, duality, Euler’s formula, Kuratowski’s theorem, toroidal graphs, 2-cell embeddings, graphs on other surfaces;

Directed graphs: Tournaments, directed paths and cycles, connectivity and strongly connected digraphs, branchings; Networks and flows: Flow cuts, max flow min cut theorem, perfect square;

Selected topics: Dominating sets, the reconstruction problem, intersection graphs, perfect graphs, random graphs.

References

Douglas B. West, Introduction to Graph Theory, Prentice Hall of India.

Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science. Prentice-Hall.

Frank Harary, Graph Theory, Narosa.

R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall.

The course will have two examinations, mid-semester and end-semester, tutorials (assignments), one or two tests, and a study term-paper.

Additional references will be provided in class and on the course pages.

http://cse.iitkgp.ac.in/~spp/CS60047_aut2022.html

2021-2022–

PROGAMMING AND DATA STRUCTURES ( CS10003 )	L-T-P :	Credit : 3
Sections: 9 and 10    Session : 2021-2022   Semester : SPRING

PROGAMMING AND DATA STRUCTURES LABORATORY( CS19003 )	L-T-P : 0-0-3	Credit : 2
Section : 1    Session : 2021-2022   Semester : SPRING

PROGAMMING AND DATA STRUCTURES LABORATORY( CS19003 )	L-T-P : 0-0-3	Credit : 2
Section : 11    Session : 2021-2022   Semester : AUTUMN

2017-2020–Computational Complexity, course number CS41103 LTP 3-1-0, 4 credits in Autumn 2021

CS41103 COMPUTATIONAL COMPLEXITY

L-T-P: 3-1-0,   Credits: 4

Computational Models (machine models, logic); Problems, computability, Algorithms, Resources, and Complexity; Turing machines (time and space bounds, nondeterminism); Logic (Boolean logic, circuits, first and second order logic); Complexity classes (hierarchy theorem, reachability, P, NP, Co-NP); Reduction and completeness; Randomized computation; Approximability; Cryptography and protocols; Parallel Computation; Polynomial Hierarchy; Logarithmic space; Polynomial space; Exponential time and space.

References

1. Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Longman.
2. Michael Sipser, Introduction to the Theory of Computation, PWS Publishing.
3. John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata, Languages and Computation, Addison-Wesley, 1979.
4. J. Balcazar, J. Diaz, and J. Gabarro, Structural Complexity, Volumes I and II, Springer.

================================================================================================

2017-2018, 2009, 2003 — Computational Geometry

2016 — Programming and Data Structures

2014-2016, 2008-2010 — Algorithms II

2007, 2014 — Special Topics in Algorithms

2004-2008 — Quantum Computing and Quantum Information Processing

2003, 2006 — Computational Complexity