Theoretical Computer Science

• Profs: D. Komm, H.-J. Böckenhauer, J. Hromkovic
• Website: https://courses.algodi.inf.ethz.ch/theoinf-2025/
• Moodle: https://moodle-app2.let.ethz.ch/course/view.php?id=26224
• VVZ: https://www.vorlesungen.ethz.ch/Vorlesungsverzeichnis/lerneinheit.view?lerneinheitId=194428&semkez=2025W&ansicht=ALLE&lang=en
• Admin:
• Material:
• Videos:
  • 2024: https://video.ethz.ch/lectures/d-infk/2024/autumn/252-0057-00L/s/DEEH3mVCcbI
  • 2025: https://video.ethz.ch/lectures/d-infk/2025/autumn/252-0057-00L/s/N_lMuWenGeW

Lecture Notes

• 01 What is Theoretical Computer Science?
• 02 The Language of Computation - Alphabets, Words, and Languages
• 03 Formalizing Algorithmic Problems and Information
• 04 Kolmogorov Complexity and the Nature of Randomness
• 05 Proving the Prime Number Theorem, Introduction to Finite Automata
• 06 Formalizing Finite Automata
• 07 Combining Automata and Proving Non-Regularity
• 08 Proving Non-Regularity

Book (WIP)

• Chapter 0 - Preface
• Chapter 1 - Introduction
• Chapter 2 - Alphabets, Words, Languages, and Problem Representation
• Chapter 3 - Finite Automata
• Chapter 4 - Turing Machines
• Chapter 5 - Computability
• Chapter 6 - Complexity Theory
• Chapter 7 - Algorithmics for Hard Problems
• Chapter 8 - Randomization
• Chapter 9 - Communication and Cryptography
• Chapter 10 - Grammars and Chomsky Hierarchy