Module Identifier CS10310  
Module Title INTRODUCTION TO THEORETICAL COMPUTER SCIENCE  
Academic Year 2006/2007  
Co-ordinator Dr Edel M Sherratt  
Semester Semester 1  
Other staff Dr Edel M Sherratt, Dr Lynda A Thomas  
Pre-Requisite A level or AS level maths.  
Mutually Exclusive CS10410  
Course delivery Lecture    
  Seminars / Tutorials   Up to 5 one hour workshops  
  Practical   Up to 5 two hour practicals that relate the theory to programming languages  
Assessment
Assessment TypeAssessment Length/DetailsProportion
Semester Exam2 Hours Written exam  80%
Semester Assessment assignment (approx 10 hours)  20%
Supplementary Exam2 Hours Written exam  100%

Learning outcomes

On successful completion of this module students should be able to:
state basic definitions and results of the theory of computing;

provide formal definitions of programming language constructs

relate theory to the elements of a modern programming language

classify problems in computing

Brief description

This module introduces basic concepts and results of theoretical computer science. It is intended for students with a background in computing who wish to deepen their understanding of programming concepts and the theoretical underpinning of computer science.

Content

1. Sets, functions and relations - 2 Lectures

Motivation - relationship with programs. What are sets and how do we describe them. When to use enumeration and when to use predicates. The set of truth values. Cardinality. Subsets. Using sets to specify pre- and post-conditions for programs. Sets and sequences. Set union, intersection, difference. Universal set. Complement of a set. Venn-Euler diagrams. Cartesian product. Powerset. Examples of proofs.

2. Functions (maps) - 2 Lectures

What are functions and how do we represent them - pictorially, using definitions, injection, bijection, surjection. Functions and the meaning of assignment. Variables. States and operations that cause a change of state. Functions. Relations and logical conditions.

3. Languages and Problems - 10 Lectures

Motivation: computation entails using language to describe and solve problems.
Symbols, alphabets. Strings. String concatenation. Alphabets and strings.
Languages. Language union, intersection, difference and symmetric difference. Language concatenation. Kleene star.
Regular expressions and regular languages. Deterministic finite automata. Nondeterministic Finite Automata. Languages that are not regular. The Pumping Lemma (simple and general forms). Proving that a language is/is not regular. Closure properties of regular language. Using the closure properties to prove that a language is not regular.
Context free languages. Context free grammars. Derivations of context free grammars. Context free grammars and regular grammars. Pushdown automata. Languages that are not context free. Context free languages are not closed under intersection. Context free languages are not closed under complementation. Context free languages are closed under union.

4. Turing Machines - 6 Lectures

What are Turing machines? Beyond context free languages. Example. What does Computable mean? The Halting Problem.

Module Skills

Problem_solving Inherent to subject. Assessed in assignment and exam.  
Research skills no  
Communication no  
Improving own Learning and Performance Reflection and self-learning will be encouraged during all sessions. In addition the assignment will allow students to reflect on their learning to date.  
Team work no  
Information Technology In practicals students will relate concepts to computing languages  
Application of Number Inherent to subject. Assessed in assignment and exam  
Personal Development and Career planning no  
Subject Specific Skills See contents  

Notes

This module is at CQFW Level 4