COMP4141 Theory of Computation: Course Information for Session 1 2017

(The present document is available online at

Course Objectives

After successfully completing this course, you will appreciate the fundamental questions of computer science:

You will also be aware of some concrete answers to these and related great questions of computer science, the reasons why some questions in this area will remain unanswered forever, and that some answers are still being sought.

Course Overview by Keywords

Computability: formal languages and problems, Turing Machines (TMs), computability, decidability, universal TMs, Church-Turing thesis, halting problem, reduction and undecidability proofs, examples; Complexity: run time, space, complexity classes, non-determinism and NP, polynomial reductions and NP completeness, optimisation problems and approximation, randomisation; Languages and Automata: regular expressions and languages, finite automata, determinisation, context-free grammars and languages (CFLs), Chomsky normal form, word problems, pumping lemma, push-down automata, decidability problems for CFLs. If time permits, also a brief overview of semantics and correctness: while programs, assertions and program correctness, Hoare logic, loops and loop invariants, relative completeness of Hoare logic (and its role in a proof of Gödel's incompleteness result).

Graduate Attributes

This course address the following elements of the UNSW graduate attributes:

Prerequisites and Follow-Ons

Prequisites: Officially, COMP1927 or MATH2301. Students should note, however that the content of the course involves use of discrete mathematics. Students are assumed to be comfortable with the structure of mathematical arguments and the basics of set theory, and you will struggle without such a background. You will be expected to prove correctness of your problem solutions in this course. An intuitive understanding of programming and algorithms is also important when taking this course. The course is not recommended for postgraduate students who have not yet taken COMP9020 or have equivalent background in discrete mathematics, or who have not taken at least one session of computer science courses. If you have any doubt whether you have an adequate background, consult the instructor.

After mastering this subject, students may want to follow on with other subjects that have a theoretical slant. These include:

(Not all of these subjects are available in any given year.)

Text Book

The required textbook for this course is M Sipser, Introduction to the Theory of Computation, any edition.

Additional notes are made available on the course website.

Other useful references for the material covered are:


Ron van der Meydenlecturer-in-charge Office 217G, CSE (K17)9385
Manas Patratutor

Class Times

Lectures are held

Lectures will run from weeks 1-12, and will pause for the session break after week 7.

Tutorials are held

Tutorials will run weeks 2-13.


Time will be allocated during lectures and tutorial for ad hoc questions concerning the course contents. (Any difficulties that you have in understanding the content are likely to be shared by other students, who may also benefit from the answers given.)

For issue not resolved in class, the lecturer will be available immediately after lectures, but may schedule an appointment for issues requiring extended discussion. You may also schedule an appointment by email request.


Tutorials start in week two. Part of the allocated tutorial time will be devoted towards solving problems and discussing solutions related to lecture topics, while the remaining time will be used to discuss topics relevant to assignments.

Students will be required in class to present their solutions to tutorial and/or homework problems under the guidance of the tutor.

Assessment Summary

The final mark is determined as the sum of the marks for the assessable components of the course:

Hurdle requirement: your total (midterm+final) exam mark must be a pass (at least 35/70) in order to pass the course.

You can inspect the current state of your mark record by using the command 4141 classrun -sturec. Check your record frequently and make sure you contact us promptly if you do not agree with it.

All marks must be finalised by the end of stuvac. If you think there is a problem with any of your marks then you need to advise us by emailing your tutor within two weeks of the mark being released, and, in all cases before the end of stuvac. No marks will be changed after the end of stuvac.

Homework Submission

Homework must be submitted in handwritten format in blue or black ink. It must be clearly legible: use (upper and lower case) block letters if your cursive handwriting style is not legible. Computer printed work will not be accepted, unless you can provide disability grounds for being unable to submit in this format. There are several reasons for this rule:

Late Penalties

Homework will generally be due at the start of the Thus lecture. Late submissions will not be accepted. An allowance for minor illness or misadventure has already been built in by taking the homework grade to be the best 8 out of 10. Each homework will consist of multiple parts and partial solutions will be accepted. If you have any reasonable grounds for failure to submit homework that is not protected by this policy, you should submit an official request for special consideration.

Plagiarism, special considerations, supplementary exams

You are responsible for being familiar with the CSE policies concerning special consideration and supplementary examinations . Be sure to note the dates for midterm and final exams and CSE supplementary exams advertised early in the session. You are responsible for being available on the examination dates and on the CSE supplementary exam date in the case you are granted a supplementary exam. Requests for exams on an alternate date on the grounds that you are not available to take the exam due to travel WILL be rejected. Students are therefore very strongly advised not to book travel that conflicts with any potential exam dates, including the supplementary exam date.

Unless clearly indicated otherwise (see below) submitted work is expected to be your individual effort. Recall that you are bound by the UNSW Plagiarism Policy.

We make one concession for joint work in this course: you are allowed to do the weekly homework either in pairs or individually. Your partner for any homework is your choice, and need not be the same on every homework. In submitting your homework as a group, you are agreeing you have contributed equally, and both members of a group will receive the total mark given to the homework. Groups of one will be marked the same as groups of two. If you are not satisfied with the contributions of your partner, you are free to switch partners or submit individually for the next homework.

You are allowed in this course to confer with other students to clarify the statement of a problem and discuss general approaches to the solution of related problems, but the solution submitted should be solely the work of the individual or members of the group.

Keeping Informed and Staying in Touch

Important information concerning this course may be communicated via the following media. Students are responsible for regularly checking these channels for communications.

Course Evaluation and Development

The course has had changes of lecturer in 2013 and again in 2014. The overall material covered is similar, and the text remains the same, but there may be some changes of emphasis and style each year. In particular, we are dispensed with peer evaluation in 2014 and will aim to provide prompt feedback on assignments by discussing solutions in the tutorial immediately following the due date. (The cost of this is the introduction of a hard deadline and no allowance of late submissions.) Students have requested written homework and tutorial solutions. For tutorial solutions, you are responsible to attend tutorials -- we will trail distribution of best homework solutions in 2017.