COMP3630 Theory of Computation

Later Year Course

Offered By	Research School of Computer Science
Academic Career	Undergraduate
Course Subject	Computer Science
Offered in	First Semester, 2011 and First Semester, 2012
Unit Value	6 units
Course Description	This course covers the theoretical computer science areas of formallanguages 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.
Learning Outcomes	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 understand formal reasoning about languages. Understand the basic concepts of complexity theory.
Indicative Assessment	Assignments (30%); Final Exam (70%)
Areas of Interest	Computer Science
Requisite Statement	COMP1140 or a mark of 70 or more in COMP2600
Prescribed Texts	Hopcropft, J.E., Motwani, R. & Ullman, J.D.Automata Theory, Languages, and Computation 3rd edition, Pearson Education, 2007.
Science Group	C

The information published on the Study at ANU 2011 website applies to the 2011 academic year only. All information provided on this website replaces the information contained in the Study at ANU 2010 website.