Theory of Computation (CS4232)

Lecturer
The lecturer is Frank Stephan from the Departments of Mathematics and Computer Science of the National University of Singapore.
Frank Stephan's addresses are:

  (1) Department of Mathematics, National University of Singapore
      10 Lower Kent Ridge Road, Block S17, Singapore 119076
      Office: S17#07-04, Telephone +65-6516-2759

  (2) School of Computing, National University of Singpore
      13 Computing Drive, Block COM2, Singapore 117417
      Office: COM2#03-11, Telephone +65-6516-4246

The telefax in the office of the Department of Mathematics is +65-67795452

The email address is fstephan@comp.nus.edu.sg


Textbooks
The course follows the lecture notes. Nevertheless, feel free to increase the knowledge by reading textbooks on the theory of computation. The most famous textbook is Introduction to Automata Theory, Languages and Computation by John Hopcroft, Rajeev Motwani and Jeffrey D. Ullman (Third Edition, Pearson, 2013, ISBN 1292039051). This textbook has its own Wikipedia Page. Its authors maintain the webpage http://infolab.stanford.edu/~ullman/ialc.html for this book. However, you can also use any other textbook.

Lecture Notes
The lecture notes are available from the following links: ps-file, pdf-file by ps to pdf and pdf-file by pdflatex. The lecture notes reflect the content of the lecture more precisely than any textbook; so it is strongly recommended to read them and to see textbooks only as an add-on.

Time and Place
Tuesday from 12:00 hrs to 14:00 hrs in COM1#02-04.

Tutorial
Friday from 15:00 hrs to 16:00 hrs in COM1#02-09;
Friday from 16:00 hrs to 17:00 hrs in COM1#02-07;
Friday from 17:00 hrs to 18:00 hrs in COM1#02-07.

Check this link for further updates of locations and timings.

Assessment
There will be two short midterm examinations (20 marks each) in the second half of Lecture 6 (which will be on Tue 17 September 2019 in week 6) and Lecture 11 (which will be on Tuesday 29 October 2019 in week 11).
Furthermore, students can score up to 10 marks with homework presentations in tutorials and write-ups: 2 marks for each homework written up in the Forum, these homeworks have to reserved in order to allow every student to do the quota; up to 8 marks in total. Furthermore, presenting homeworks best every week in tutorial - as there are three tutorial groups, each student should have a chance to present every week or every second week; five presentations give 1 mark and 8 presentations give 2 marks; 2 marks is the maximum mark.
The final examination will count 50 marks. The overall number of marks obtainable is 100. The exercises are taken from the lecture notes and also copied into the slides.

Slides for AY 2019/2020.
Lecture 1: ps-file and pdf-file.
Lecture 2: ps-file and pdf-file.
Lecture 3: ps-file and pdf-file.
Some sample dfas for some easy tasks with the possibility to input state sequences to be checked.
Lecture 4: ps-file and pdf-file.
Lecture 5: ps-file and pdf-file.
Lecture 6: ps-file and pdf-file. Midtermtest One.
Solutions of Test (from AY 2015/2016): ps-file and pdf-file.
Solutions of Test (from AY 2017/2018): ps-file and pdf-file.
Solutions of Test (from AY 2019/2020): ps-file and pdf-file.
Lecture 7: ps-file and pdf-file.
Lecture 8: ps-file and pdf-file.
Lecture 9: ps-file and pdf-file.
Lecture 10: ps-file and pdf-file.
Lecture 11: ps-file and pdf-file. Midtermtest Two.
Solutions of Test (from AY 2015/2016): ps-file and pdf-file.
Solutions of Test (from AY 2017/2018): ps-file and pdf-file.
Solutions of Test (from AY 2019/2020): ps-file and pdf-file.
Lecture 12: ps-file and pdf-file.
Lecture 13: ps-file and pdf-file.
Additional Exercises: ps-file and pdf-file.
Solutions of Final Examination (from AY 2015/2016): ps-file and pdf-file.
Solutions of Final Examination (from AY 2017/2018): ps-file and pdf-file.
Solutions of Final Examination (from AY 2019/2020): ps-file and pdf-file.