Module Identifier  CS10310  
Module Title  INTRODUCTION TO THEORETICAL COMPUTER SCIENCE  
Academic Year  2007/2008  
Coordinator  Dr Lynda A Thomas  
Semester  Semester 1  
Other staff  Dr Edel M Sherratt, Dr Lynda A Thomas, Mr David J Smith  
PreRequisite  A level or AS level maths.  
Mutually Exclusive  CS10410  
Course delivery  Lecture  Up to 22 hours  
Assessment 

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 postconditions for programs. Sets and sequences. Set union, intersection, difference. Universal set. Complement of a set. VennEuler diagrams. Cartesian product. Powerset. Examples of proofs.
2. Languages and Problems  13 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.
3. Advanced Topics  4 Lectures
What are Turing machines? Beyond context free languages. Example. What does Computable mean? The Halting Problem.
Problem solving  Inherent to subject. Assessed in assignment and exam.  
Research skills  no  
Communication  no  
Improving own Learning and Performance  Reflection and selflearning 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 
This module is at CQFW Level 4