433-330 Theory of Computation

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

The objectives of this subject are 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.

• ability to apply knowledge of basic science and engineering fundamentals

• ability to undertake problem identification, formulation and solution

Project work during semester, expected to take about 36 hours (24%); and a 3-hour end-of-semester written open-book examination (76%). To pass the subject, students must obtain at least 50% overall, 12/24 in project work, and 38/76 in the written examination.