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

1 | 19Feb - 23Feb | Chp.2 | BV: Introduction & Overview & Aptitude Test & Finite Automata [Slides 2] |

2 | 26Feb - 2Mar | Chp.3-4 | BV: Regular Expressions & Languages [Slides 3,Slides 4] |

3 | 5Mar - 9Mar | Chp.5-7 | BV: Context-Free Grammars & Languages and Pushdown Automata [Slides 5,Slides 6,Slides 7] |

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

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

6 | 26Mar - 30Mar | Chp.10 | BV: Intractable Problems [Slides 10a,Slides 10a] |

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

- Hopcroft, Motwani, Ullman (2006) Automata Theory, Languages, and Computation (course textbook, cheap source)
- M. Sipser (2012) Introduction to the Theory of Computation (fits the course even better, cheap source)
- 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 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).