Module Guide¶
Below you can view core module information. This guide provides important information about the module and should be read in conjunction with the Module Descriptor found on the Module Information Directory (MID).
Module aim¶
This module aims to give you a practical and theoretical understanding of the foundations of computer science.
It includes formal specification of patterns and languages. It describes different models of computation and the issues of computability and complexity. It also explores algorithmic techniques used to tackle complex problems.
Aims and Summary¶
This module is designed to help you understand the theoretical foundations of Computer Science, and from this an appreciation of the limitations of computation and the important questions that remain open to this day.
The module covers: formal specification of languages; the main models m computation; and what these tell us about issues of computability and complexity.
Intended Module Learning Outcomes¶
Upon completion of the module, you will have achieved the following:
- Demonstrate the ability to use formal notation to specify patterns and languages.
- Specify and be able to simulate various types of automata.
- Demonstrate the ability to explain the connection between algorithms, models of computation, and language classes.
- Classify the computability and complexity of problems.
Learning schedule¶
- Start of the week: Asynchronous lecture videos.
- During the week: Tutorials, 2-hour labs for you to work on the exercises. (Check your timetable for your scheduled session.)
- End of the week: Lab solutions videos.
Weekly schedule¶
| Week | Theme | Lecture | Sipser pages |
|---|---|---|---|
| 1 | Introduction | Problems! | 1--25 |
| 2 | Models of Computation | DFAs & NFA | 31--54 |
| 3 | Models of Computation | NFA equiv. DFA & Regular Expressions | 55--76 |
| 4 | Models of Computation | Limits of the Regular Languages, Grammars | 77--82 |
| 5 | Models of Computation | Context-Free Languages (CFLs) [PDAs/CFGs] | 101--124 |
| 6 | Models of Computation | Turing Machines (TMs) | 165--187 |
| 7 | Decidability | Decidability | 193--211, 215--238 |
| 8 | Complexity | Complexity | 275--298 |
| 9 | Complexity | NP-Completeness | 299--322 |
| 10 | Complexity | Space complexity | 331--337, 348--351 |
| 11 | Revision | ||
| 12 | Revision |
Key resources¶
The textbook is:
Sipser, M. (2012). Introduction to the theory of computation (3rd ed.). Cengage.
If you like reading eBooks then you may find it useful to read it through BibliU.
The full reading list is available at: Reading list
Assessment methods¶
See the Assessment Information page.
Visit the Assessment Information page
Course Reps and Forums¶
Coventry University Students Union runs a system of forums for students to feedback and discuss their courses. Visit their portal to find out who represents your views and when they meet.