(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
02/10/2025		Lecture 2 (continued) — NFA, DFA vs NFALecture 2--
Week 5
09/10/2025		Lecture 3 — Equivalence of DFA & NFALecture 3--
Week 5
09/10/2025		 More Exercises Equivalence of DFA & NFALecture 4--
Week 8
23/10/2025		----
Week 9
30/10/2025		Midterm Exam---
Week 10
06/11/2025		No Class (Holiday)---
Week 11
13/11/2025		----
Week 12
20/11/2025		----
Week 13
27/11/2025		----
Week 14
04/12/2025		----
Week 15
11/12/2025		----
Weeks 16–17
21/12/2025 – 06/01/2026		Final Exams---