CSC4010: Introduction to Theoretical Computer Science

Fall 2026 · CUHK-Shenzhen

This page is being prepared for the Fall 2026 offering. Items marked TBA will be updated before the relevant course activity.

Course Information

Lectures	Time and room TBA
Course format	3 units; undergraduate lecture course offered by the School of Data Science.
Tutorial	One tutorial each week, led by the instructor. Time and room TBA
Instructor	Aditi Dudeja
Office hours	TBA (office: Room 504b, Daoyuan Building)
Teaching staff	TBA
Expected background	Comfort with mathematical proofs, discrete mathematics, asymptotic notation, and basic algorithm analysis. No prior course in computability or complexity theory is assumed.
Textbook	There is no required textbook. Lecture slides, notes, and required readings will be posted on this page or on the university learning platform.
Course outline	Official course description. The detailed course outline on the university system is authoritative for assessment and policy information.
Communication	Announcements will be posted on the university learning platform. For course-related email, please begin the subject line with [CSC4010].

Topics

This course studies two fundamental questions: What can be computed? and, among computable problems, what can be computed efficiently? We will formalize computation using mathematical models and use reductions, diagonalization, and hierarchy arguments to prove both possibility and impossibility results.

The following list is tentative and may be adjusted as the term progresses.

Languages and models	Decision problems, languages, encodings, RAMs, Turing machines, and Boolean circuits.
Computability	Decidable and recognizable languages, variants of Turing machines, self-reference and the Recursion Theorem, undecidability, and reductions.
Time complexity	Polynomial time, the class P, time hierarchy, the class NP, certificates and verifiers, polynomial-time reductions, NP-hardness, NP-completeness, and the Cook–Levin Theorem.
Space complexity	PSPACE, hierarchy theorems for time and space, Savitch’s Theorem, logarithmic space, sublogarithmic space, and small-space models of computation.
Restricted computation	Constant-space computation and finite automata, together with a comparison to context-free grammars and pushdown automata.
Modern viewpoints	Fine-grained complexity and introductory cryptographic applications of computational hardness and lower bounds.

The university course listing describes CSC4010 as an introduction to the theory of computation: the study of which problems computational devices can solve and how efficiently they can solve them, using precise abstract models.

Learning Outcomes

By the end of the course, students should be able to:

Model computational problems as languages and reason precisely about algorithms and machines.
Design and analyze Turing machines and explain why standard variants have equivalent computational power.
Prove undecidability and complexity results using reductions, diagonalization, self-reference, and hierarchy theorems.
Work fluently with central classes including P, NP, PSPACE, and logarithmic space, and explain the relationships proved in the course.
Recognize how classical lower-bound ideas lead to modern conditional lower bounds and cryptographic applications.
Write clear, rigorous proofs in theoretical computer science.

Grading

The course will use proof-based homework assignments, a midterm examination, and a final examination. The exact weights and the detailed collaboration policy will appear in the official course outline.

Homework assignments	TBA
Midterm examination	TBA
Final examination	TBA

Unless an assignment explicitly says otherwise, submitted solutions must be written in each student’s own words and must clearly justify every nontrivial claim. The official course outline governs collaboration, late work, regrading, and academic-integrity rules.

Course Calendar

The calendar is tentative. Dates, lecture materials, assignment releases, and assessment information will be added as the term progresses.

#	Date	Topic	Materials	Assessments
1	TBA	Course introduction: languages, problems, algorithms, encodings, and computational models	to be posted
2	TBA	Turing machines	to be posted
3	TBA	Decidable languages and variants of Turing machines	to be posted
4	TBA	Self-reference and the Recursion Theorem	to be posted
5	TBA	Undecidability and the Halting Problem	to be posted
6	TBA	Reductions: how to prove problems undecidable	to be posted
7	TBA	Time complexity and the class P	to be posted
8	TBA	Time Hierarchy Theorem	to be posted
9	TBA	The class NP: certificates and verifiers	to be posted
10	TBA	Polynomial-time reductions, NP-hardness, and NP-completeness	to be posted
11	TBA	Cook–Levin Theorem: SAT is NP-complete	to be posted
12	TBA	Space complexity and PSPACE	to be posted
13	TBA	Hierarchy theorems for time and space	to be posted
14	TBA	Savitch’s Theorem	to be posted
15	TBA	Logarithmic space	to be posted
16	TBA	Sublogarithmic space	to be posted
17	TBA	Constant-space computation: finite automata; comparison with context-free grammars and pushdown automata	to be posted
18	TBA	Fine-grained complexity I	to be posted
19	TBA	Fine-grained complexity II	to be posted
20	TBA	Cryptographic applications of lower bounds I	to be posted
21	TBA	Cryptographic applications of lower bounds II	to be posted
*	TBA	Additional topics, review, and assessment meetings	to be announced	to be announced

Resources

There is no required textbook. The following books, notes, and surveys are optional references that approach the material from complementary viewpoints.

Bibliography

This short list collects some foundational references connected to the lectures. It will be expanded during the term.

T36	Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, 1936.
C71	Stephen Cook, The Complexity of Theorem-Proving Procedures, STOC 1971.
S70	Walter Savitch, Relationships Between Nondeterministic and Deterministic Tape Complexities, JCSS 1970.
IPZ01	Russell Impagliazzo, Ramamohan Paturi, and Francis Zane, Which Problems Have Strongly Exponential Complexity?, JCSS 2001.
GGM86	Oded Goldreich, Shafi Goldwasser, and Silvio Micali, How to Construct Random Functions, JACM 1986.

Similar Courses

Here are several courses with closely related material and useful lecture notes or slides:

CS 365: Models of Computation, Winter 2026, Eric Blais, University of Waterloo.
Introduction to Complexity Theory, Autumn 2025, William Hoza, University of Chicago.
6.045J: Automata, Computability, and Complexity, Spring 2011, Scott Aaronson, MIT OpenCourseWare.
CS 121: Introduction to Theoretical Computer Science, Boaz Barak, Harvard University.

Last updated: August 13, 2026.

S12	Michael Sipser, Introduction to the Theory of Computation, 3rd edition.
B	Boaz Barak, Introduction to Theoretical Computer Science (freely available online).
AB09	Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach.
VW18	Virginia Vassilevska Williams, On Some Fine-Grained Questions in Algorithms and Complexity.
G01/04	Oded Goldreich, Foundations of Cryptography, Volumes I and II.