Gwybodaeth Modiwlau
Module Identifier
CS10310
Module Title
INTRODUCTION TO THEORETICAL COMPUTER SCIENCE
Academic Year
2010/2011
Co-ordinator
Semester
Semester 1
Mutually Exclusive
Pre-Requisite
A level or AS level maths.
Course Delivery
| Delivery Type | Delivery length / details |
|---|---|
| Lecture | Up to 22 hours |
Assessment
| Assessment Type | Assessment length / details | Proportion |
|---|---|---|
| Semester Exam | 2 Hours Written exam | 80% |
| Semester Assessment | assignment (approx 10 hours) | 20% |
| Supplementary Exam | 2 Hours Resit failed examination and/or resubmission of failed/non-submitted coursework components or ones of equivalent value. | 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
recognize that there are different categories of 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 - 3 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. 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.
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.
Module Skills
| Skills Type | Skills details |
|---|---|
| Application of Number | Inherent to subject. Assessed in assignment and exam |
| 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. |
| Information Technology | In practicals students will relate concepts to computing languages |
| Personal Development and Career planning | no |
| Problem solving | Inherent to subject. Assessed in assignment and exam. |
| Research skills | no |
| Subject Specific Skills | See contents |
| Team work | no |
Reading List
Consult For Futher InformationLevine, Mason and Brown (1992) Lex and Yacc This book is fun and gives lots of details about these two unix utilities. Not required though O'Reilly Primo search Reference Text
Kinber and Smith (2000) Theory of Computing: a gentle introduction No books are required for this module but this comes the closest to a text. Prntice Hall Primo search
Notes
This module is at CQFW Level 4