CS 637: Mathematics-II

Theory of Computation and Graph Theory

👨‍🏫 Instructor: Dr. Debasish Pattanayak
📅 Semester: Spring 2026
🏛️ Lecture Hall: L31
📢
Upcoming Lecture: Lecture 2 - "Propositional Logic: Syntax, Semantics, and Models" (Jan 12, 2026, 2:30–3:30 PM, Hall L31).

📖 Course Overview

This course provides a rigorous foundation in the mathematics of computation, covering fundamental topics in logic, computability theory, complexity theory, and graph theory. Students will develop skills in formal reasoning, proof techniques, and algorithmic analysis essential for advanced computer science.

Course Progress: Lecture 1 of 28 completed (3.5%)

🎯 Learning Objectives

🧮 Logic & Proofs

  • Master propositional and predicate logic
  • Apply formal proof techniques
  • Understand soundness and completeness

💻 Computation Theory

  • Understand Turing machines and variants
  • Analyze decidability and undecidability
  • Explore the Church-Turing thesis

⚡ Complexity Theory

  • Classify problems by complexity
  • Master NP-completeness concepts
  • Apply polynomial-time reductions

🔗 Graph Theory

  • Analyze graph structures and algorithms
  • Understand spectral graph properties
  • Apply probabilistic graph methods

⏰ Class Schedule

📝 Lectures

  • Monday: 2:30 – 3:30 PM
  • Tuesday: 8:30 – 9:30 AM
  • Location: Lecture Hall L31

💡 Tutorials

  • Thursday: 4:30 – 5:30 PM (Weekly)
  • Problem-solving and discussion
  • Quizzes

🏢 Office Hours

Instructor Office Hours:

  • Wednesday: 3:00 – 4:30 PM
  • Or by appointment via email

📊 Grading Scheme

20%
Mid-Semester Exam
Feb 26 - Mar 5, 2026
40%
End-Semester Exam
May 4 - 11, 2026
40%
Tutorials
14 tutorials total

📚 Textbooks & Resources

Recommended Textbooks

  • Introduction to the Theory of Computation by Michael Sipser (3rd Edition)
  • Computational Complexity: A Modern Approach by Arora & Barak
  • Introduction to Graph Theory by Douglas B. West
  • Discrete Mathematics and Its Applications by Kenneth Rosen

Online Resources

  • Lecture notes and slides available on course portal
  • Tutorial problem sets posted weekly
  • Additional reading materials on course website

📅 Lecture-wise Schedule

● Upcoming Lecture marked in the schedule below

# Date Day Time Type Module Topic
1 Jan 6, 2026 Tue 8:30–9:30 Lecture Logic and Proofs What is a Proof?
T1 Jan 8, 2026 Thu 4:30–5:30 Tutorial — Tutorial 1: Problems from Logic and Proofs
2 Jan 12, 2026 Mon 2:30–3:30 Lecture Logic and Proofs What is an implication?
3 Jan 13, 2026 Tue 8:30–9:30 Lecture Logic and Proofs How to write a proof?
T2 Jan 15, 2026 Thu 4:30–5:30 Tutorial — Tutorial 2: Problems from Logic and Proofs
4 Jan 19, 2026 Mon 2:30–3:30 Lecture Models of Computation What is a Language?
5 Jan 20, 2026 Tue 8:30–9:30 Lecture Models of Computation What is a Turing Machine?
Q1 Jan 22, 2026 Thu 4:30–5:30 Quiz — Quiz 1: Problems from Models of Computation
6 Jan 27, 2026 Tue 8:30–9:30 Lecture Models of Computation What is Turing Computable?
T3 Jan 29, 2026 Thu 4:30–5:30 Tutorial — Tutorial 3: Turing machine design
7 Feb 2, 2026 Mon 2:30–3:30 Lecture Models of Computation What is a Reachable Configuration?
8 Feb 3, 2026 Tue 8:30–9:30 Lecture Models of Computation What is Universal Computation?
Q2 Feb 5, 2026 Thu 4:30–5:30 Quiz — Quiz 2: Turing machine matchings
9 Feb 9, 2026 Mon 2:30–3:30 Lecture Models of Computation To Halt or Not to Halt?
10 Feb 10, 2026 Tue 8:30–9:30 Lecture Models of Computation Rice's Theorem and Undecidable Language Properties
Q3 Feb 12, 2026 Thu 4:30–5:30 Quiz — Quiz 3: Turing Machine Design and Rice's Theorem
11 Feb 16, 2026 Mon 2:30–3:30 Lecture Complexity Theory Complexity on Turing Machines and Variants
12 Feb 17, 2026 Tue 8:30–9:30 Lecture Complexity Theory Evolution of Complexity Classes (P and NP)
Recap Feb 19, 2026 Thu 4:30–5:30 Tutorial — Recap: Problems from Complexity Theory
Recap Feb 23, 2026 Mon 2:30–3:30 Lecture Undecidability Recap: Rice's Theorem and Structural Undecidability
Recap Feb 24, 2026 Mon 2:30–3:30 Lecture Complexity Theory Recap: Measuring Time and Space Complexity
— Feb 26, 2026 Thu — No Class — Mid-Semester Examination
— Mar 2, 2026 Mon — No Class — Mid-Semester Examination
— Mar 3, 2026 Tue — No Class — Mid-Semester Examination
— Mar 5, 2026 Thu — No Class — Mid-Semester Examination
13 Mar 10, 2026 Tue 8:30–9:30 Lecture Complexity Theory Boolean Functions, DTIME, and 3SAT to INDSET
T4 Mar 12, 2026 Thu 4:30–5:30 Tutorial — Tutorial 4: Problems from Complexity Theory
14 Mar 16, 2026 Mon 2:30–3:30 Lecture Complexity Theory Problem Solving Lecture
15 Mar 17, 2026 Tue 8:30–9:30 Lecture Complexity Theory 3SAT to Hamiltonian Cycle Reduction
T5 Mar 19, 2026 Thu 4:30–5:30 Tutorial — Tutorial 5: NP-Completeness Reductions
16 Mar 23, 2026 Mon 2:30–3:30 Lecture Complexity Theory Search Reducible to Decision, EXP, NEXP, and coNP
17 Mar 24, 2026 Tue 8:30–9:30 Lecture Complexity Theory Space Complexity Classes L, NL, PSPACE, and NPSPACE
Q4 Mar 26, 2026 Thu 4:30–5:30 Quiz — Quiz 4: Reductions
18 Mar 30, 2026 Mon 2:30–3:30 Lecture Graph Theory for Computation Graph Theory Foundations and Representations
T6 Apr 2, 2026 Thu 4:30–5:30 Tutorial — Tutorial 6: Problems from Graph Theory for Computation
19 Apr 6, 2026 Mon 2:30–3:30 Lecture Graph Theory for Computation Degree Sequences, Adjacency Spectra, and Reachability
20 Apr 7, 2026 Tue 8:30–9:30 Lecture Graph Theory for Computation Structural Graph Proofs on Paths, Cycles, and Trees
21 Apr 9, 2026 Thu 4:30–5:30 Lecture Graph Theory for Computation 2-Regular Graphs, Dirac's Theorem, and Matchings
Q5 Apr 13, 2026 Mon 2:30–3:30 Quiz — Quiz 5
— Apr 14, 2026 Tue — No Class — Holiday (No Class)
22 Apr 16, 2026 Thu 8:30–9:30 Lecture Graph Theory for Computation Matchings and Bipartite Graphs
23 Apr 20, 2026 Mon 2:30–3:30 Lecture Graph Theory for Computation Planar Graphs and Structural Constraints
24 Apr 21, 2026 Tue 8:30–9:30 Lecture Probabilistic & Spectral Graphs Random Walks, Hitting Times, and Basic Properties
T7 Apr 23, 2026 Thu 4:30–5:30 Tutorial — Tutorial 7: Problems from Graph Theory for Computation
- May 8, 2026 -- 2:30-5:30 No Class End Semester Exam Everything taught in the course