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. Please note that augmented learning may change to online lectures only, depending on the Covid situation.

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.