Teaching mode in 2021

This course will be offered via augmented learning type 2 or 3, for lectures and tutorials. Assessments will be online via sunLearn or git submissions, depending on class size. Where feasible, invigilated sitdown assessments may be used.

Lecturers

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


Teams meeting times

  • Mon 14h00 to 16h45, virtual Teams tutorial: COMPULSORY
  • Tues 09h00 to 10h00: lecture f2f and Teams, A407
  • Wed 11h00 to 12h00: lecture f2f and Teams, A407
  • Fri 12h00 to 13h00: lecture f2f and Teams, A407


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:
    • Chapter 3 - The Church–Turing Thesis
    • Chapter 4 - Decidability
    • Chapter 7 - Time Complexity
  • From freely available web resources:
  • 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.