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 3 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