PMA 1050 / PMA 6853: Discrete Foundations 2004-5
by Dr. P.G. Dixon
IMPORTANT: This is not the current web page for this course.
The current web page is http://www.dcs.shef.ac.uk/~pdg/PMA1050.
The purpose of this page is merely to provide an archive copy of the web page
I had when I was giving the course, but without the questions and solutions,
which may be being used by the current lecturer. Any queries
about the course should be addressed to the current lecturer, Dr. V. V. Bavula:
e-mail V.Bavula with the usual extension @sheffield.ac.uk
This 10-credit half-module explores the theoretical foundations of Computer Science,
answering the question: "What is computation?". It introduces the discrete
mathematical modelling techniques needed to describe software systems,
construct specifications and prove that they are correct. Topics covered
include: sets, functions and relations; propositional logic, truth tables and
rules of inference; simple
proof, refutation proof and inductive proof; finite automata, regular
expressions, Moore and Mealy machines; phrase structure grammars, regular and context-free
Aims of the Course
to establish a link between computational problems and precise formal models
to provide a grounding in set theory and propositional logic
to provide a grounding in natural deduction, refutation and inductive proof
to develop an understanding of abstract automata, grammars and formal languages
to prepare students for advanced theory courses at higher levels
The course is three lectures/problem classes per week in the first semester. Homework will be set
at the last session each week and solutions presented the following week.
- PMA1050: One two-hour examination: candidates will be asked to answer 3 questions out of 4. Pass mark 40%.
- PMA6853: One two-hour examination: candidates will be asked to answer Question 1, and 2 questions out of the remaining 3.
Question 1 will be a deeper question covering a variety of topics from throughout the syllabus. Pass mark 50%.
For both papers, all the material in the lecture notes is examinable except
for the definition of context sensitive grammar and the final section, from the
heading `Pushdown Automata' to the end.
Here are the January 2004 COM1050 paper and solutions,
and the January 2004 COM6853 paper and solutions.
Here is the January 2003 COM1050 exam paper, adjusted for the notation used this
year: solutions are not available.
Here is a hypothetical January 2003 COM6853 exam paper.
This was produced in the format, described above, of this session's
COM6853 exam, using the January 2003 COM1050 paper and questions set during the
Prerequisites and Corequisites
Co-requisite: basic knowledge of programming, from COM1010.
Intended Learning Outcomes
By the end of this course the students should:
- be able to develop and analyse simple discrete models of computer systems;
- be able to use set theory and propositional logic with confidence;
- be able to prove mathematical properties by refutation and by induction;
- understand the properties of automata and their associated languages and grammars.
In addition, 10 sessions ("problem classes") during the course will be devoted to explaining the solutions to homework problems.
- Set theory: [ 2 lectures ]
- Theory of Functions: [ 2 lectures ]
- Methods of Proof: [ 2 lectures ]
- Induction and Recursion: [ 2 lectures ]
- Propositional Logic: [ 2 lectures ]
- Finite Automata: [3 lectures ]
- Kleene's Theorem: [ 1 lecture]
- Mealy Machines: [ 2 lectures ]
- Formal Languages and Grammars: [ 2 lectures ]
- Regular Grammars and Regular Languages: [ 2 lectures ]
- J. Gersting, Mathematical Structures for Computer Science.
- M. Piff, Discrete Mathematics, (Cambridge University Press, 1991).
- D. I. A. Cohen, Introduction to Computer Theory, (Wiley, 1991).
More advanced books for background reading
Some of these books are quite expensive: you are recommended to use them in the Library first and
see how useful you find them before taking a decision on purchasing.
- J. Carroll and D. Long, Theory of finite automata with an introduction to
formal languages (Prentice-Hall, 1989).
- John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory,
Languages and Computation (Addison-Wesley, 1979)
The links in this section are currently disabled.
A copy of the slides used so far in lectures will be made available here.
Hard copy will be distributed.
The question sheets and solutions are posted below. Hard copy will be distributed.
There will be a reading week for this course in week 7. In this week there will
be no formal lectures and no further homework set. There will be optional help
week. Details of these will be
given nearer the time.
Return to P. G. Dixon home page