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 formal languages into their types, be able to formally reason about languages, and understand the basic concepts of computability and complexity theory.

16Apr18: Exam will be Thu.14.Jun.09:30-12:00 in JD101 Math Bld#27.

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 Badri Vellambi
Tutors: Sultan Majeed and David Quarel
Target: Undergraduate (COMP3630) and Graduate (COMP6363) students. Others welcome.
Enrollment: Undergraduate & Masters: The usual way via ISIS. Honors&Others: Contact admin/lecturer.
Admin: Bindi Mamouney student.services@cecs.anu.edu.au or studentadmin.cecs@anu.edu.au, 02 6125 4450, Office N202, Level 2 CSIT Bld.108
Class representative: Alexander Cox. See here for further information
Course Subject: Computer Science
Unit Value: 6 units
Time Table: See Schedule below for details
Indicative Assessment: Initial Background Check ; Hurdle Tutorials; Assignments (3×10%); Final Exam (70%) [details]
Indicative Workload: 24h lectures, 11h 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=23693
Gradiance page: http:/www.gradiance.com/ (class token)
This page: http://cs.anu.edu.au/courses/COMP3630/index.html

Schedule

#Week Book Lecture & Tutorial
tentative[HUM06] Lectures: Wed.14ºº-15ºº LT3 (5.17) SoM Bld#100 (except wk1) and Thu.15ºº-16ººJD101 Math Bld#27. Tutorials (1-2h): Mon.10ºº-12ºº|12ºº-14ºº|Wed.|16ºº-18ºº A105 in BAB Bld.115.
119Feb - 23FebChp.2 BV: Introduction & Overview & Aptitude Test & Finite Automata [Slides 2]
226Feb - 2MarChp.3-4 BV: Regular Expressions & Languages [Slides 3,Slides 4]
35Mar - 9MarChp.5-7 BV: Context-Free Grammars & Languages and Pushdown Automata [Slides 5,Slides 6,Slides 7]
412Mar - 16MarChp.8 BV: Turing Machines [Slides 8]
519Mar - 23MarChp.9 BV: Undecidability [Slides 9]
626Mar - 30MarChp.10 BV: Intractable Problems [Slides 10a,Slides 10a]
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: Wed Mar 21.
Assignment 2 [pdf]
Out: Wed Mar 21. Due: Wed Apr 18.
Assignment 3 [pdf]
Out: Wed Apr 18. Due: Wed May 16.

Tutorials

For most weeks, we provide weekly tutorial sheets containing questions that you should try to solve in advance of the tutorial sessions.
The tutorial number refers to the week the tutorial is held in.
The Gradiance part of the tutorial is compulsory (always due Mondays 10:00), but you have 20 trials!
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 | revision | Q&A | assignment 3]

Assessment

Test: Initial Background/Aptitude Test in first lecture to allow students lacking required background to choose a different course.
Hurdle: You have to achieve 80% of the marks in the Gradiance section in 6 of the first 7 tutorials.
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 marks in each assignment 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 David Quarel or 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 comp1600. We will review these concepts but at a very fast pace and focus on the more advanced topics. If you have not taken comp1600 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]. Chp.1 of Li&Vitanyi (2008) is also a great review of theoretical CS concepts (also recommended for the Advanced AI course).

Updated:  18 May 2018 / 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