Skip navigation
The Australian National University
Theory of Computation COMP3630/COMP6363

Theory of Computation COMP3630/COMP6363

Welcome to the Theory of Computation Course at the ANU !

This course (offered in semester 1 of even years) covers the theoretical computer science areas of formal languages and automata, computability and complexity. Topics covered include: regular and context-free languages; finite automata and pushdown automata; Turing machines; Church's thesis; computability - halting problem, solvable and unsolvable problems; space and time complexity; classes P, NP and PSPACE; NP-Completeness. At successful completion of the course, students should have a good knowledge of formal computation and its relationship to languages, be able to classify languages into their types, be able to formally reason about languages, and understand the basic concepts of computability and complexity theory.

Formalities

Offered By: The Research School of Computer Science @ Australian National University
Offered In: First Semester, 2018 (19 February to 25 May). See Schedule below
Lecturers: Marcus Hutter (Convenor) and TBA and TBA
Tutor: Sultan Majeed
Target: Undergraduate (COMP3630) and Graduate (COMP6363) students. Others welcome.
Enrollment: Undergraduate & Masters: The usual way via ISIS. Honors&Others: Contact admin/lecturer.
Admin: Sandra Harrison student.services@cecs.anu.edu.au or studentadmin.cecs@anu.edu.au, 02 6125 4450, Office N202, Level 2 CSIT Bld.108
Class representative: See here for further information
Course Subject: Computer Science
Unit Value: 6 units
Time Table: See Schedule below for details
Indicative Assessment: Initial Hurdle Assessment (pass/fail); Assignments (3×10%); Final Exam (70%) [details]
Indicative Workload: 24h lectures, 12h tutorials, ~3×15h assignm., ~40h self-study, +exam prep.
Prerequisites: [COMP1110 or COMP1140] and [COMP1600 or COMP2600] (exceptions).
Textbooks: [HMU06] and [Sip12] (see resources for details and more)
ANU page: http://programsandcourses.anu.edu.au/2018/course/comp3630
Wattle page: https://wattlecourses.anu.edu.au/course/view.php?id=16178
Gradiance page: http:/www.gradiance.com/
This page: http://cs.anu.edu.au/courses/COMP3630/index.html

Schedule

#Week Book Lecture & Tutorial
tentative[HUM06] Lectures: Wed.14ºº-15ººDA Brown Rm 110/108 LF CRISP Bld.26 and Thu.15ºº-16ººJD101 Math Bld.27. Tutorials: Mon.10ºº-12ºº|12ºº-14ºº|16ºº-18ºº|Wed.12ºº-14ºº|16ºº-18ºº A105 in RSISE Bld.115.
119Feb - 23FebChp.1 BV: Introduction & Overview
226Feb - 2MarChp.2-4 BV: Finite Automata and Regular Expressions & Languages
35Mar - 9MarChp.5-7 BV: Context-Free Grammars & Languages and Pushdown Automata
412Mar - 16MarChp.8 BV: Turing Machines
519Mar - 23MarChp.9 BV: Undecidability
626Mar - 30MarChp.10 BV: Intractable Problems
2Apr - 6Apr--- break
9Apr - 13Apr--- break
716Apr - 20AprChp.10 MH: The Satisfiability Problem (SAT) [Slides 10b]
823Apr - 27AprChp.10 MH: More NP-Complete Problems [Slides 10c]
930Apr - 4MayChp.11 MH: Additional Classes of Problems (co-NP) [Slides 11a]
107May - 11MayChp.11 MH: Additional Classes of Problems (PSPACE) [Slides 11b]
1114May - 18MayBeyond HMU MH: More Complexity Theory [Slides 12a]
1221May - 25MayPaper MH: Physics & Computation [Slides 12b]

Assignments

Assignment 1 [pdf]
Out: Wed Feb 21. Due: Thu Mar 22. 14:00
Assignment 2 [pdf]
Out: Wed Mar 21. Due: Thu Apr 19. 14:00
Assignment 3 [pdf]
Out: Wed Apr 18. Due: Thu May 17. 14:00

Tutorials

For most weeks, we provide weekly tutorial sheets containing questions that you should try in advance of the tutorial sessions.
The tutorial number refers to the week the tutorial be held.
Tutorial sessions are to discuss the problems you faced during solving these exercises.
Solutions will in general not be presented but discussed during these sessions.
  • Tutorial 1 [no tutorial]
  • Tutorial 2 [pdf]
  • Tutorial 3 [pdf]
  • Tutorial 4 [pdf]
  • Tutorial 5 [pdf]
  • Tutorial 6 [pdf]
  • Tutorial 7 [pdf]
  • Tutorial 8 [pdf]
  • Tutorial 9 [pdf]
  • Tutorial 10 [pdf]
  • Tutorial 11 [assignment 1&2]
  • Tutorial 12 [pdf]
  • Tutorial 13 [revision / Q&A / assignment 3] --> Everyone who asks a question will get a piece of candy! ☺

Assessment

Hurdle:Initial Hurdle Assessment (pass/fail) in Week 2 or 3 to ensure enrolled students have the required background.
Assignments: Each Assignment will count 10% towards the final grade. Late submissions will not be accepted.
Exam: Final examination [150min,written,closed-book] counts 70% towards the final grade (past exams).
Know: What to know for the exam: Most of [HUM06]. Material not treated in the course will not be examined but may be helpful.
Pass: To pass the course, students must get at least 40% of the assignment marks and at least 40% of the final exam marks and at least 50% of the total final mark.
Grading: Final course marks will be subject to moderation, so may differ from the raw sum of assessment marks.
Plagiarism: Misconduct will result in failure of the course and disciplinary consequences (no exceptions).

Resources

  • The course closely follows book [HMU06] which contains everything you need to know for the tutorials, assignments, and exam.
  • The alternative book [Sip12] fits the course even better, but is denser and more advanced.
  • If your formal languages and automata theory command is weak or rusty, I recommend [HMU06].
  • If you're fluent in formal languages and automata theory and are more interested in complexity theory, I recommend [Sip12].
  • Older editions will do just as well.
  • Lecture notes will not be made available in general.
  • The course is in general not recorded, since white boards will be used extensively.
  • For those parts lectured from slides, they will be made available.
  • For others, you have to take notes, use the book, or you can check out Jeff Ullman's Slides and Video Lectures.
  • For Gradiance access and other questions regarding tutoring and assignments,
    please post them on Wattle or email tutor Sultan Majeed
  • Download JFLAP. You might have to install a Java virtual machine to run it.
    More resources on JFLAP can be found on the JFLAP homepage.
(Further) reading:

Prerequisites

Formal prerequisites are completion of [COMP1110 or COMP1140] and [COMP1600 or COMP2600].
In particular you need prior experience in programming (any language) and algorithms. It is also expected that you already know about formal languages and grammars (regular and context free), automata (deterministic, non-deterministic, push-down), and their relations, Turing machines, and undecidable problems. This is all taught in comp2600. We will review these concepts but at a very fast pace and focus on the more advanced topics. If you have not taken comp2600 in advance, we may grant you special permission to enrol, if you have or are prepared to acquire the necessary background by other means, e.g. Chp.1-4 of Cormen&al.(2009) Introduction to Algorithms and the basics of Chp.1-9 of [HMU06].

Updated:  04 December 2017 / Responsible Officer:   JavaScript must be enabled to display this email address. / Page Contact:   JavaScript must be enabled to display this email address. / Powered by: Snorkel 1.4