(The present document is available online at http://www.cse.unsw.edu.au/~cs4141/17s1/admin/outline.html).
After successfully completing this course, you will appreciate the fundamental questions of computer science:
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).
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:
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:
Name | Role | location | phone | |
---|---|---|---|---|
Ron van der Meyden | lecturer-in-charge | Office 217G, CSE (K17) | 9385 6922 | meyden@cse.unsw.edu.au |
Manas Patra | tutor | manas.patra@gmail.com |
Lectures are held
Tutorials are held
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.
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 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.
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.