CSE 396 Introduction to the Theory of Computation (Spring 2025)

[Return to course list]

[Page Status: Draft, Under construction]

Site Map

• Course Info (This page) : Basic summary of course content
• Syllabus : Detailed course content, including grading policy, academic integrity policy, accessibility resources, etc.
• Schedule : This is where you find course materials (lecture notes / slides / assignments) and deadlines (assignments / projects / exams).

Announcements

• [04/15] HW7 released in UBLearns; Due 04/25.
• [04/08] Reminder: In-class midterm at 04/10.
• [03/27] HW6 released in UBLearns; Due 04/14.
• [03/14] HW5 released in UBLearns; Due 03/28.
• [03/07] HW4 released in UBLearns; Due 03/14.
• [02/27] Reminder: In-class midterm at 03/04.
• [02/20] HW3 released in UBLearns; Due 03/06.
• [02/19] HW2 ddl extended by one day: Due 02/21, 23:59. No 24-hr late submission accepted.
• [02/11] HW2 released in UBLearns; Due 02/20.
• [01/30] HW1 released in UBLearns; Due 02/11.
• [01/28] Lectures will be moved to Cooke 121 starting from Tue, 02/04.
• [01/23] First class. Recitation starts in the next week (01/30)

Logistics

Communication Policy

(Other than office hours) All questions/requests to the instructor, TAs, and Graders should be sent using Piazza (New Post and select Instructors only if this is a private post), and not via emails (which can be used as a secondary means if Piazza post didn't work).

UB Learns should be used for checking the grades (and doing quizzes) – all other materials such as syllabus, announcements, homeworks, and Q&As, are handled by Piazza only.

Teaching Team

Course Description

This will be a mostly mathematical course. The first main objective of the course is to convey those major concepts and results in the theory of computation that guide our thinking about the power of computers and the problems we can solve with them. This includes the entire historical origin of the field in the work of Alan M. Turing, Kurt Gödel, and Cook-Levin. Finite automata, regular expressions, boolean circuits, and idealized programs (if not the Turing machine, think of the Java Virtual Machine) are tools of everyday computing practice. Computational complexity theory asks the fundamental question of how much time, memory, and other computational resources computers need to solve certain problems, and today is relied upon for Internet security.

A second main objective is not as "concrete" as the above-listed syllabus material, but is just as important. Computers are by-nature entirely formal entities---they do precisely what is prescribed in programming languages that are ultimately formal and mathematical. Not just to reason about them, but even to communicate effectively in the field and on the job, one must be able to state assertions precisely and design prototypes concisely. This requires fluency in the underlying mathematical language used to describe problems, computations, and objectives. This course gives valuable training in formal modes of reasoning, analysis, and presentation.

A tentative list of topics are

• What is computation:

  • Models of computation: Boolean circuits, finite automatas, and Turing machines.

• What is and is not computable:

  • (Turing's) Uncomputability; Godel's Incompleteness Theorem

• What is efficient computation.

  • Why does "efficient" means polynomial running time
  • NP-completeness theory.
  • The most fundamental problem in computer science: P vs NP.

• The outreach of the theory of computation

  • Probabilistic Computation: how tossing coins can (or cannot?) help you compute.
  • Cryptography: Things hard to compute can also be useful
  • Quantum Computing: Harnessing the power of quantum mechanics
  • ...

Course Credits: 4

Learning Outcome

At the end of this course, each student should be able to apply mathematical foundations, algorithmic principles, and CS theory to model and design systems with comprehension of the tradeoffs involved in design choices.

Pre-requisites

Students need to have some basic knowledge of

• Programming (CSE115): you won't be writing code in this class, but you should at least have some understanding of what a computer program is.
• Discrete math (CSE191 or 250): objects like sets and graphs; concepts like proposition logic and recursion
• Algorithm analysis (CSE250 or 331): in particular, asymptotic analysis, big-$O$ notation.
• Linear Algebra basics (MTH 309LR): NOT a pre-requisite; Only needed when we are covering the quantum computation topic; I will teach necessary background in the class, but will be helpful if you already know it.
• Students should be comfortable with mathematical proofs (e.g., the idea of contradiction and induction). To test if you are well-prepared for the course, you can take a look at the Mathematical Backgroud.

Recommend resources

Textbooks

The primary textbook we will use is

• [Barak] Introduction to Theoretical Computer Science by Boaz Barak. The book is freely available online.

Other recommended readings

• [Sipser] Michael Sipser. Introduction to the Theory of Computation. 2nd ed.

  • A classic, starting from automatas and leads to the P vs NP problem. Extremely well-written with very clear explanations and proofs, and can serve as a good accompaniment for about half of this course

• [Widgerson] Avi Widgerson. Mathematics and Computation. Princeton University Press. (2019). Available online.

  • A broad overview of the connections between mathematics and the theory of computation, covering some of the topics of CSE396 as well many advanced topics. It can be a great read for students that want to go beyond and explore the theory of computation in more depth.

• [MM] Cristopher Moore and Stephan Mertens. The Nature of Computation. Oxford University Press (2011)

  • A huge book, over 900 pages. Contains lots of info on computation from a physicist's perspective. A great book to sample from and have by your side as a reference.

• [Aaronson1]. Scott Aaronson. Quantum Computing Since Democritus. Cambridge University Press (2013)

• [LPV] László Lovász, József Pelikán, and Katalin Vesztergombi. Discrete Mathematics: Elementary and Beyond. Springer (2003)

  • Nice little book covering most mathematical tools that will be used in our course, with some (extremely beautiful) applications to algorithmic and combinatorial problems, but all on an elementary level.

• [LLM] Eric Lehman, F. Thomson Leighton, Albert R Meye. Mathematics for Computer Science. Also freely available online.

  • Another huge book. Covers all math background needed for this course (and maybe most algorithm courses). Good as a reference.

• [Aaronson] Scott Aaronson's website

  • Lots of interesting writtings (essays, lecture notes, comments) on all stuffs related to computational complexity (mostly quantum-related)