COMP4141 Theory of Computation: Course Information for Session 1 2016

(The present document is available online at http://www.cse.unsw.edu.au/~cs4141/16s1/admin/outline.html).

Course Objectives

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

• What problems can be solved by a computation?
• How hard is it to compute solutions?
• How can we express computation?

Course Overview by Keywords

Computability: formal languages and problems, Turing Machines (TMs), computability, (semi-)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

• understanding of their discipline in its interdisciplinary context :
  The theoretical perspective we study in this course will provide you with a powerful conceptual toolbox with which to view the discipline and its connections to other areas. It goes to the core of what computation is, and many of the ideas we deal with come up any time that one designs a new programming language or program analysis tool, is required to understand whether an algorithm solving a problem is as efficient as it can be, or needs to model a system for rigorous verification.
• rigorous in their analysis, critique and reflection:
  This course is all about rigour in the description and analysis of the nature of computation. We need to be very precise in order to be able to prove things about what can and cannot be computed.
• able to apply their knowledge and skills to solving problems:
  The theory of computation presents many challenging problems on which to hone your problem solving skills.
• capable of effective communication:
  You will learn not just how to solve problems, but also how to pursuade others of the correctness of your solution. This will require you to learn to present your reasoning about the solution in a clear but precise way.

Prerequisites and Follow-Ons

Prequisites: Officially, COMP1927 or MATH2301. Students should note, however that the content of the course involves use of discrete mathematics. While we briefly review these topics, students with prior exposure to the structure of mathematical arguments and the basics of set theory will have a strong advantage, and you may struggle without such a background.

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

• COMP4121 Advanced and Parallel Algorithms
• COMP3151 Foundations of Concurrency
• COMP3153 Algorithmic Verification
• COMP4161 Advanced Topics in Software Verification
• COMP4181 Language-based Software Safety
• COMP3152 Comparative Concurrency Semantics
• COMP4442 Advanced Computer Security

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:

• H.R. Lewis and C.H. Papadimitriou, ELements of the Theory of Computation
• J.E. Hopcroft and J.D. Ullman, Introduction to the Theory of Computation

Staff

Class Times

Lectures are held

• Mon 12:00 - 13:00 Mathews 310 (K-F23-310)
• Wed 16:00 - 18:00 Mathews 310 (K-F23-310)

Tutorials will run weeks 2-13.

Consultations

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

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:

• 30% homework problems; best 10 out of 12 sets worth 3 marks each
• 70% exams:
  • a mid-session exam (1 hour in week 6) worth up to 20 marks
  • a final exam (3 hours) worth up to 50 marks

Hurdle requirement: your 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 cs4141@cse.unsw.edu.au 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

• You will almost certainly need to engage in pencil and paper reasoning anyway to solve the homework problems.
• Solutions will often involve diagrams and uncommon symbols that you will struggle to present well in the most commonly used tools such as Word. We don't want you to waste time on this.
• This is not a course in the use of mathematical typesetting tools such as LaTex. We swear by this for our own published work and lecture notes, and highly recommend it to you if you ever need to produce a documement with mathematical text, but we want you to focus on the intellectual content of this course rather than on learning how to use such a tool.
• Writing things out by hand is an excellent pathway into the brain for learning.

Late Penalties

Howework will be due at the start of the Tues lecture. Homework solutions may be discussed in the tutorial immediately following, so late submissions will not be accepted. Note that an allowance for misadventure has already been built in by taking the homework grade to be the best 10 out of 12.

Plagiarism, special considerations, supplementary exams

Unless clearly indicated otherwise (see below) submitted work is expected to be your individual effort. Recall that you are bound by the Yellow Form. Particularly relevant are the sections on Originality of Assignment Submissions, Special Consideration — Illness & Misadventure, and the CSE Supplementary Assessment Policy.

CSE uses its addendum to 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. Homework problems will be marked as group work, i.e. groups of one will be marked the same as groups of two. Both group members are expected to contribute equally. In submitting your homework as a group, you are agreeing you have contributed equally unless we receive an agreed-to statement from both group members identifying differing levels of contribution. In the absence of such a statement, both members will receive the same mark.

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 the work of the members of the group.

Keeping Informed and Staying in Touch

• Course Web Site: Important notices related to this course will be displayed on the course home page http://www.cse.unsw.edu.au/~cs4141. It is your responsibility to check this page regularly.
• Email: Urgent information may also be sent to your CSE email account. Requests of a confidential nature should be sent to the course account, cs4141. General questions likely to be of interest to other students should be raised in class.

Course Evaluation and Development