Computation TheoryModule Details
Module/Course Description
Course Title: Computation Theory
Course Code: UU-COM-3001
Credits: 12.00
Course Description:
Objectives of the Course:
• be familiar with the basic theoretical principles in Computer Science
• know various types of finite automata
• be familiar with formal definitions of programming languages and their connection with finite automata
• have learnt material on Turing machines and computability
• have a deeper theoretical understanding of algorithmic complexity classes.
Learning Outcomes:
1. Discuss the concept of finite state machines.
2. Explain context-free grammars.
3. Design a deterministic finite-state machine to accept a specified language.
4. Explain how some problems have no algorithmic solution.
5. Provide examples that illustrate the concept of uncomputability.
6. Determine a language’s location in the Chomsky hierarchy (regular sets, context-free, context-sensitive, and recursively enumerable languages).
7. Prove that a language is in a specified class and that it is not in the next lower class.
8. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
9. Explain at least one algorithm for both top-down and bottom-up parsing.
10. Explain the Church-Turing thesis and its significance.
11. Define the classes P and NP.
12. Explain the significance of NP-completeness.
13. Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it.
Prerequisites: UU-ACG-1000, UU-MKT-2000, UU-MAN-2010, UU-BBA-2000, UU-ENG-1000, UU-ENG-1001, UU-ENG-1005, UU-COM-1000, UU-MTH-1000, UU-MTH-1005, UU-MTH-2000, UU-MTH-3000, UU-COM-1100, UU-COM-1101, UU-COM-2004, UU-COM-1103, UU-COM-2000, UU-COM-2001, UU-COM-2002, UU-COM-2003, UU-COM-3000, UU-COM-3002, UU-COM-3003, UU-COM-3004, UU-COM-3005, UU-COM-3008, UU-COM-4001, UU-COM-4002, UU-COM-4003, UU-COM-4004, UU-COM-4008, UU-COM-4009, UU-COM-4010, UU-BA-IND100, UU-FNT-103, UU-BBA-2010-BCS, UU-BBA-1000-BCS
Prerequisites Categories: -
Typical Module duration: 4.0 Week(s)