433-330 Theory of Computation

433-253 Algorithms and Data Structures and 433-255 Logic and Computation

The objective of this subject is for students to understand the essence of computing through simple models of computational devices; to understand the limitations of computing, the relative power of formal languages and the inherent complexity of many computational problems of practical importance; to be able to apply these models in practice to solving problems in diverse areas such as string searching, pattern matching, cryptography, and language design; to be familiar with standard tools and notation for formal reasoning about machines and programs; and to improve reasoning and problem-solving skills.

Topics covered include formal languages, grammars and recognisers; models of computation: finite state machines, pushdown automata, Turing machines; computability: the Church-Turing thesis, decidability, reducibility; complexity: the classes P and NP, NP-complete problems, space complexity; and other topics selected from information and coding theory, lambda calculus, recursion theory, approximation algorithms, probabilistic algorithms, cryptography, quantum computing.

Project work (expected to take about 36 hours) during semester and one written examination (not exceeding three hours) at the end of the semester. The project work must be completed satisfactorily to pass the subject. Weighting of assessment components will be advised at the commencement of the subject.