Teaching mode in 2022

This course will be offered face to face only, for lectures and tutorials. Assessments will be invigilated on campus assessments. Note that tutorials are compulsory assessments.


Third term: Prof L van Zijl
Office: A520, General Engineering Building,
Email: lvzijl -at- cs.sun.ac.za

Fourth term: Brink van der Merwe
Email: abvdm -at- cs.sun.ac.za

Meeting times

  • Mon 14h00 to 16h00: Tutorial, NARGA A
  • Tues 09h00 to 10h00: Lecture in A404, except 13 Sept, when it will be A503B
  • Wed 11h00 to 12h00: Lecture in A404
  • Fri 12h00 to 13h00: Lecture in A404

Prescribed text

Introduction to the Theory of Computation, 3rd ed, Sipser

Supplementary texts

  • Introduction to the Theory of Computation, by Masheshwari and Smid
    This book is freely available, and may be downloaded here.
  • Book of proof, by Richard Hammack. This book is freely available, and may be downloaded here.

Third term content

From Sipser:
  • Chapter 1 - Regular languages
  • Chapter 2 - Context-free languages

Fourth term content

  • From Sipser:
    • More on chapters 1 and 2.
    • Chapter 3 - The Church–Turing Thesis
    • Chapter 4 - Decidability
    • Chapter 7 - Time Complexity
  • From freely available web resources such as:
  • The following software packages will be used during the course.
  • The fourth term will contribute 50% towards the mark for this course. Half of this mark will be from the exam and the remainder from the project. Announcements for term 4 will be on teams. Please contract the instructor if you are not part of the teams channel for cs345/711.