SCS2107 Complexity and Computability

The course introduces a series of powerful theoretical machines, the idea of non-computable and intractable problems. Finite state machines and regular languages: Deterministic and non-deterministic machines; Equivalence and minimization; Regular expressions and regular grammars; Kleenex’s theorem. Pushdown automata and context-free grammars; Normal forms of grammars; Top-down and bottom-up parsing. Turing machines and computability; Church's thesis; Simple examples of non-computable problems; NP-Computable problems.

Course Objectives

• To Introduce Computability and Complexity Theory, including simple notions in theory of computation, limits of computation, and the complexity theory.

Expected Outcomes
Upon completion of the course the learners:

• Will gain a solid understanding of various types of computational models and their relations to one another.
• Will have a strong sense of the limits that are imposed by the very nature of computation, and the ubiquity of unsolvable problems throughout Computer Science.
• Will understand the notion of computational complexity and especially of the classes of problems known as P, NP, co-NP, NP-complete and NP-Hard.
• Will come away with stronger formal proof skills and a better appreciation of the importance of discrete mathematics to all aspects of Computer Science.