(5018129-3) Theory of Computation

Homepage and Syllabus

Disclaimer

This is the best information available as of Thursday Sept 25, 2025 at 7:00 p.m. KSA time. Updates will appear here as the course progresses.

Meeting Time & Place

  • Section 911: Thursday 4:00 p.m. – 7:00 p.m. (via Blackboard)

Instructor

Dr. Emad Alsuwat
Course Homepage: TheoryofComputation-Fall2025.html
Office: W101 CIT
Office hours: Thursday 8:00 a.m. – 4:00 p.m.
Email: Alsuwat@tu.edu.sa

Course Overview

Central to the theory of computation are the concepts of automata, formal languages, grammars, algorithms, computability, decidability, and complexity. These foundations provide theoretical understanding with direct applications in compiler design, cryptography, and optimization.

Learning Outcomes

  • Understand mathematical foundations of computation (automata, grammars, complexity, decidability).
  • Develop ability to conduct rigorous mathematical proofs for algorithms and computation.

Textbooks

  • Required: M. Sipser, Introduction to the Theory of Computation, 2nd Edition
  • Required: Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages and Computation, 3rd Edition

Grading Policy

Midterm Exam25%
Homework Assignments20%
Participation & Quizzes10%
Final Exam45%

Topics to be Covered

WeekTopic
1Overview
2Formation of Preliminary Concepts
3Regular Languages
4Regular Languages (continued)
5Context-Free Languages
6Midterm Exam
7The Church–Turing Thesis
8Decidability
9Reducibility
10Advanced Topics in Computability

Lecture Notes & Homework

Updates will appear week by week as the course progresses.

Week/Date Topic Slides Assignment Due Date
Week 1
04/09/2025		General Orientation & Overview---
Week 2
11/09/2025		Lecture 1 — Introduction to Automata TheoryLecture 1--
Week 3
18/09/2025		Lecture 1 (continued) — Alphabets, Strings, GrammarsLecture 1--
Week 4
25/09/2025		Lecture 2 — DFA: Definitions, Transition FunctionsLecture 2--
Week 5
2/10/2025		Lecture 2 (continued) — NFA, DFA vs NFALecture 2--
Week 6
9/10/2025		Lecture 3 — Equivalence of DFA & NFALecture 3--
Week 7
16/10/2025		 Regular ExpressionsLecture 4Homework 1Nov 22, 2025
Week 8
23/10/2025		Properties of Regular LanguagesLecture 5--
Week 9
30/10/2025		Equivalence & Minimization of DFAsLecture 6--
Week 10
6/11/2025		Context-Free Languages & GrammarsLecture 7--
Week 11
13/11/2025		Pushdown Automata (PDA)Lecture 8--
Week 12
20/11/2025		Properties of Context-free LanguagesLecture 9--
Week 13
27/11/2025		Turing MachinesLecture 10--
Week 14
4/11/2025		UndecidabilityLecture 11--
Week 15
11/12/2025		Review---
Weeks 16–17
21/12/2025 – 06/01/2026		Final Exams---