Module/Course Description

Course Title: Computation Theory

Course Code: UU-COM-3001

Programme: Bachelor of Science (BSc) in Computer Science - MW

Credits: 3.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

Return

This site uses cookies and other tracking technologies to assist with navigation and your ability to provide feedback, analyse your use of our products and services, assist with our promotional and marketing efforts, and provide content from third partiesCookie Policy