CS10310 - AN INTRODUCTION TO THEORETICAL COMPUTER SCIENCE

Module Identifier

CS10310

Module Title

AN INTRODUCTION TO THEORETICAL COMPUTER SCIENCE

Academic Year

2003/2004

Co-ordinator

Dr Mark B Ratcliffe

Semester

Semester 1

Other staff

Dr Edel M Sherratt

Course delivery

Lecture

16 lectures

Other

Workshop. Up to 6

Assessment

Assessment Type	Assessment Length/Details	Proportion
Semester Exam	2 Hours Written exam.	100%
Supplementary Exam	Will take the same form, under the terms of the Department's policy

Further details

http://www.aber.ac.uk/compsci/ModuleInfo/CS10310

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.

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.

Aims

The aims of this module are:

to provide an overview of the basic definitions and results of theoretical computing;
to provide a theoretical foundation for specifying and proving program behaviour;
to introduce software proof techniques.

Content

1. Sets, functions and relations - 4 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. Representing sets as sequences. A proof involving sets and sequences. Proof by contradiction. Cartesian product. Powerset. Proof that a finite set A with n elements has 2n subsets. Set union, intersection, difference. Universal set. Complement of a set. Venn-Euler diagrams.

2. Functions (maps) - 4 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 - 4 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. Induction - 2 Lectures
What is induction? Proof by induction over N. Structural induction. The Principle of Complete Induction. Proofs involving context free grammars

5. Turing Machines - 2 Lectures
What are Turing machines. Beyond context free languages. Example.

Reading Lists

Books
** Should Be Purchased
Raymond Greenlaw and H. James Hoover (1998) Fundamentals of the Theory of Computation: Principles and Practice Morgan Kaufmann Publishers Inc.
Michael Sipser (1997) Introduction to the Theory of Computation International Thomson Publishing
Students should buy one of the above; exactly which is left to your own personal preference

Notes

This module is at CQFW Level 4