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 languages.

Aims of the Course

Course organization

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.

Assessment

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.

Past Papers

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 course. 

Prerequisites and Corequisites

Co-requisite: basic knowledge of programming, from COM1010.

Intended Learning Outcomes

By the end of this course the students should:

Course content

In addition, 10 sessions ("problem classes") during the course will be devoted to explaining the solutions to homework problems.

Recommended Books

  1. J. Gersting, Mathematical Structures for Computer Science.
  2. M. Piff, Discrete Mathematics, (Cambridge University Press, 1991).
  3. D. I. A. Cohen, Introduction to Computer Theory, (Wiley, 1991).

More advanced books for background reading

  1. J. Carroll and D. Long, Theory of finite automata with an introduction to formal languages (Prentice-Hall, 1989).
  2. John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation (Addison-Wesley, 1979)
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.

Online Resources

Lecture slides

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.


Reading Week 

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 sessions that week.  Details of these will be given nearer the time.

 


Return to P. G. Dixon home page