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

1 | 19Feb - 23Feb | Chp.1 | BV: Introduction & Overview |

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

3 | 5Mar - 9Mar | Chp.5-7 | BV: Context-Free Grammars & Languages and Pushdown Automata |

4 | 12Mar - 16Mar | Chp.8 | BV: Turing Machines |

5 | 19Mar - 23Mar | Chp.9 | BV: Undecidability |

6 | 26Mar - 30Mar | Chp.10 | BV: Intractable Problems |

2Apr - 6Apr | --- | break | |

9Apr - 13Apr | --- | break | |

7 | 16Apr - 20Apr | Chp.10 | MH: The Satisfiability Problem (SAT) [Slides 10b] |

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

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

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

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

12 | 21May - 25May | Paper | 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.

- 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 [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].