41080 Theory of Computing Science
Warning: The information on this page is indicative. The subject outline for a
particular session, location and mode of offering is the authoritative source
of all information about the subject for that offering. Required texts, recommended texts and references in particular are likely to change. Students will be provided with a subject outline once they enrol in the subject.
Subject handbook information prior to 2024 is available in the Archives.
Credit points: 6 cp
Subject level:
Undergraduate
Result type: Grade and marksRequisite(s): 37181 Discrete Mathematics AND 48024 Programming 2
Description
This subject introduces the theory of computation, including topics from the theories of automata, rewriting, and parsing. Students learn to compute orders of complexity for various practical problems.
An understanding of computational complexity can lead to the design of economical and feasible products and services. For example, for an online taxi service, strategically simplifying the computation can dramatically reduce the cost of solving the very large-scale passenger-driver matching problem.
Similarly, mastering the fundamental theory of computation enables one to construct security schemes that are both convenient for users and tough against attackers. Also, in programming, the knowledge of how high-level statements are translated into operational instructions helps one identify performance bottlenecks to achieve optimal efficiency by appropriate design of the algorithm.
Subject learning objectives (SLOs)
Upon successful completion of this subject students should be able to:
| 1. | Build models for real-world applications and plan computations realisable on computers. (C.1) |
|---|---|
| 2. | Formulate the Turing machine computation model using formal definition and higher-level operation description. (D.1) |
| 3. | Distinguish some decidable/non-decidable problems by proof in the Turing machine computation framework. (D.1) |
| 4. | Analyse algorithm efficiency and improve when possible. 9D.1) |
Course intended learning outcomes (CILOs)
This subject also contributes specifically to the development of the following Course Intended Learning Outcomes (CILOs):
- Design Oriented: FEIT graduates apply problem solving, design and decision-making methodologies to develop components, systems and processes to meet specified requirements. (C.1)
- Technically Proficient: FEIT graduates apply abstraction, mathematics and discipline fundamentals, software, tools and techniques to evaluate, implement and operate systems. (D.1)
Teaching and learning strategies
Each week, material will be delivered via a combination of preparatory pre-work, a collaborative lecture developing and expanding upon the pre-work, and a lab/tutorial exploring the concepts developed in the pre-work and lecture via scaffolded practical activities.
The pre-work will aim to engage the students with the core knowledge, which will then be challenged in the ctive learning sessions via active problem solving, peer learning activities and the like. The lab/tutorial sessions will provide a venue to apply this knowledge in aggregate and to extend it, accompanied by a tight feedback loop with their instructors. The lab/tutorial sessions will also provide a place in which to ensure concepts and skills required for the assignments are encountered and giving room to develop with high stakes nature of assessment. The lab/tutorial sessions will also include weekly opportunities for structured formative assessment and feedback, as separate from the summative assessment constituted in the assignments.
The subject will develop students’ analytical and logical skills, along with their knowledge of the theory of computation, via active and collaborative learning activities exploring the connexions between the theory of computation and practical computer science.
The students’ learning will be assessed via two connected assignments, both of which will build on and extend knowledge and skills developed and scaffolded in the pre-work, lectures and tutorials. The first assignment will present a simplified task focusing on an aspect of the theory of computation with tangible practical applications, such as basic parsing. This assignment will be completed individually. The second assignment will be a small-group assignment, where students will collaboratively enlarge upon the core concepts introduced in the first assignment, working together to solve a more advanced and realistic version of the problem presented in the first assignment, such as constructing a compiler or interpreter for a simple programming language. The second assignment will require students to communicate and to coordinate their efforts to complete the task. Together, the assignments will provide students with a concrete instantiation of the theory of computation in a real-world form.
The students’ understanding of the underlying theory will be assessed via a written assignment, focused on developing correct and coherent solutions to domain relevant problems, rather than examining simple factual recall.
Content (topics)
- Regular languages and automata
- Regular expressions
- Context free languages
- Turing Machines
- Decidability
- Reducability
- Time/Space Complexity
Assessment
Assessment task 1: Practical Individual Project
| Intent: |
|
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1, 2 and 4 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1 and D.1 |
| Type: | Report |
| Groupwork: | Individual |
| Weight: | 30% |
| Length: | No particular length limits. Generally, the report would be about 4 pages. |
Assessment task 2: Practical Group Project
| Intent: | To ensure students master the theory of computation and understand how it is linked with practical computation. The project will be based on assignment 1, but significantly more sophisticated. Completing this project involves reviewing, mastering and applying a large part of the scope covered by this subject. Students need to apply the techniques learned during Week 3-8. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1, 2, 3 and 4 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1 and D.1 |
| Type: | Project |
| Groupwork: | Group, group assessed |
| Weight: | 30% |
| Length: | No particular length limits. Generally, the report would be about 10 pages. |
Assessment task 3: Theory Assignment
| Intent: | The theory assignment assesses the students' understanding of the theoretical concepts underpinning standard models of computation. |
|---|---|
| Objective(s): | This assessment task addresses the following subject learning objectives (SLOs): 1, 2, 3 and 4 This assessment task contributes to the development of the following Course Intended Learning Outcomes (CILOs): C.1 and D.1 |
| Type: | Project |
| Groupwork: | Individual |
| Weight: | 40% |
Minimum requirements
In order to pass the subject, a student must achieve a mark of 50% or more.
Recommended texts
Lewis, H. R., & Papadimitriou, C. H. (1997). Elements of the theory of computation (2nd ed.). Prentice-Hall.
Sipser, M. (2012). Introduction to the theory of computation (3rd ed.). Cengage Learning.
Arora & Barak (2009): Computational Complexity: A Modern Approach. Cambridge University Press.
Wigderson (2019): Mathematics and Computation: A Theory Revolutionizing Technology and Science. Princeton University Press.