Module Identifier | CS10310 | ||||||||||||||
Module Title | INTRODUCTION TO THEORETICAL COMPUTER SCIENCE | ||||||||||||||
Academic Year | 2007/2008 | ||||||||||||||
Co-ordinator | Dr Lynda A Thomas | ||||||||||||||
Semester | Semester 1 | ||||||||||||||
Other staff | Dr Edel M Sherratt, Dr Lynda A Thomas, Mr David J Smith | ||||||||||||||
Pre-Requisite | 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 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. 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 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 |
This module is at CQFW Level 4