## Theory of Computation COMP3630/COMP6363 |

It will run again in 2018 Semester 1.

Below is the last 2016 version of this course.

### Welcome to the Theory of Computation Course at the ANU !

This course 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, 2016 (15 February to 27 May). See Schedule below

**Lecturers**: Marcus Hutter (Convenor) and Dirk Pattinson and Jan Leike

**Tutor**: Sultan Majeed

**Target:**Undergraduate (COMP3630) and Graduate (COMP6363) students. Others welcome.

**Enrollment**: Undergraduate & Masters: The usual way via ISIS. Honors&Others: Contact lecturer.

**Admin:**Annika Humphreys and Bindi Mamouney

**Class representative:**See here for further information.

**Course Subject:**Computer Science

**Unit Value:**6 units

**Time Table:**See Schedule below for details

**Indicative Assessment:**Assignments (3×10%); Final Exam (70%) [details]

**Indicative Workload:**25h lectures, 12h tutorials, ~3×15h assignm., ~40h self-study, +exam prep.

**Prerequisites:**COMP1140 or COMP2600 with a minimum grade of D (exceptions).

**Textbook:**Hopcroft, Motwani, Ullman [HMU06] (2006) Automata Theory, Languages, and Computation, 3rd edn.

**ANU page:**http://programsandcourses.anu.edu.au/2016/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: Usually Tuesday & Thursday 14ºº-15ºº Psych G8 in Building 38B.
Tutorials: Usually Thursday 12ºº-13ºº / Wednesday 16ºº-17ºº A105 in RSISE Building 115.
18Feb&24Mar in N101 CSIT Bld 108, 3&10Mar&28Apr. in Psych G5 | |

1 | 15Feb - 19Feb | Chp.1 | DP: Introduction & Overview |

2 | 22Feb - 26Feb | Chp.2-4 | DP: Finite Automata and Regular Expressions & Languages |

3 | 29Feb - 4Mar | Chp.5-7 | DP: Context-Free Grammars & Languages and Pushdown Automata |

4 | 7Mar - 11Mar | Chp.8 | JL: Turing Machines |

5 | 14Mar - 17Mar | Chp.9 | JL: Undecidability |

6 | 21Mar - 25Mar | Chp.10 | JL: Intractable Problems |

7 | 28Mar - 1Apr | Chp.10 | JL: The Satisfiability Problem (SAT) [Slides 10b] |

4Apr - 8Apr | --- | break | |

11Apr - 15Apr | --- | break | |

8 | 18Apr - 22Apr | Chp.10 | MH: More NP-Complete Problems [Slides 10c] |

9 | 25Apr - 29Apr | Chp.11 | MH: Additional Classes of Problems (co-NP) [Slides 11a] |

10 | 2May - 6May | Chp.11 | MH: Additional Classes of Problems (PSPACE) [Slides 11b] |

11 | 9May - 13May | Beyond HMU | MH: More Complexity Theory [Slides 12a] |

12 | 16May - 20May | Paper | MH: Physics & Computation [Slides 12b] |

13 | 23May - 27May | Chp.1-11 | MH: Physics & Computation (ctd.) (24May only. No lecture on 26May) |

### Assignments

**Assignment 1**[pdf]- Out: Wed Feb 24. Due: Thu Mar 24. 16:00
**Assignment 2**[pdf]- Out: Wed Mar 16. Due: Wed Apr 20. 16:00
**Assignment 3**[pdf]- Out: Wed Apr 20. Due: Wed May 18. 16: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
- 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

**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 final mark.

**Grading:**Final course marks will be subject to moderation, so may differ from the raw sum of assessment marks.

### 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.

- Hopcroft, Motwani, Ullman (2006) Automata Theory, Languages, and Computation (course textbook)
- M. Sipser (2012) Introduction to the Theory of Computation (fits the course even better)
- S. Aaronson (2005) NP-complete Problems and Physical Reality (presented in the course)
- S. Arora and B. Barak (2009) Computational Complexity: A Modern Approach (way beyond the course)

### Prerequisites

Formal prerequisites are completion of COMP1140 or COMP2600 with a minimum grade of D.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].