Computer Science 1a Teaching Materials:

Here are my Lecture Notes on Discrete Mathematics.

**Health warning:**

These notes started off as *my* notes - for lecturing *from* -
when I was lecturing DM at Queen Mary, and in making them available to
my supervisees I offer no guarantees. Word has reached me that
Cambridge 1a CS students refer to these notes, so I have tidied them
up a bit. Notification of typos, etc, suggestions for improvement,
etc, will be received with thanks and attract the usual rewards.

**If I am supervising you for 1A Discrete Maths I want you to read
these notes and attempt all the exercises**.

You might find Jean Gallier's lecture notes on first-year discrete maths for CS students helpful.

Here are my Regular Languages and Finite Automata materials (originally written for Queen Mary) in pdf format. I am greatly endebted to Chloë Brown for creating a version in html . This version is preferable in various ways to the pdf version, since the answers to the exercises are not immediately visible in the way they are in the .pdf version, but can be seen only when you click on the link. Thank you, Chloë Brown!! Here is a file of answers to the coursework questions at the end .

Here is a file containing lots of exercises. You should certainly attempt at least some of them. Some of them have answers prepared by my supervisees, and displayed below. Here are

Simrun Basuita's answer to question 3 of the section on structured proof;

James Baker's answer to question 6 in that section; and

James Baker's answer to question 7 in that section.

A discussion answer to the question about two-to-the-power-153 mod 153 from Prof Fiore's materials.

Here is a discussion of workout 26 on Prof. Fiore's notes.

Here are some exercises on predicate calculus and here is the same file with some answers

Some discussion answers to (very!) old tripos questions (some of these are

Worked answer to 1995 Paper 5 question 4X (Maths tripos);

Worked answer to 2002 Paper question 8 part (a) (ii);

Worked answer to 2007 Paper 2 question 5;

Worked answer to 2009 Paper 1 question 4;

Worked answer to 2010 Paper 1 question 4 (``Societies involving fighting'');

Worked answer to 2011 Paper 2 question 5;

Worked answer to 2013 Paper 2 question 5.

Worked answer to 2013 paper 2 question 6; (or rather it will be as soon as i have finished the answer!!

Worked answer to 2015 paper 2 question 7

Worked answer to 2015 paper 2 question 9.

Worked answer to 2018 paper 2 question 9.

Worked answer to 2018 paper 2 question 10.

I think you will find these exercises on matrix representation of binary relations very useful. They are elementary, and you need - eventually! - to be able to do them all without breaking sweat. Don't feel any need to do the whole lot, but try a random sample to make sure you're OK.

An exercise on structural induction.

You presumably know what a Necker cube is. Cook up a bundle of literals that say things like...whether or not [in the 3D reconstruction] a line segment lies in the plane of the paper or in a plane normal to it. Oh yes, and something about what happens when two lines cross. The idea will be that you will have a big fat formula with lots of literals in it and there will be precisely two valuations that make the formula true, corresponding to the two possible orientations of the cube in the reconstruction. I have a discussion answer which I will show you if you attempt the exercise.

Here is Gary Jackson's html-ised illustrated discussion of the handshaking riddle.

Here is a worked example of a proof by course-of-values induction, prepared by Frank King, and included with his permission.

Here is a file that contains everything you need to know about countability. It also has some instructive exercises. You can skip the appendix if you like but you should definitely read everything before it.

Here is a discussion of some of the exercises in the 2012-3 lecture notes for DMI and DMII.

Sam Staton has a discussion of one of these questions. His answer is different from mine (and slightly better).

JAPE (``Just Another Proof Editor'') is a gadget that is no longer examinable, but it can be very useful as long as you don't become addicted to it. It was developed in part by Richard Bornat, then at QMW, and here is his introduction....it may be useful (the exercises I supply invite you to use it). In any case it anticipates the 1b course:

Here are my supervision notes for assorted CS topics (and not just 1a). They are messages to myself, and come with no guarantees. The chapters on ML and discrete mathematics might be helpful.

This is a model tripos question for .... well, i'm not sure. It just might be a teeny bit hard for 1a discrete maths but is probably too easy for 1b.

If you are interested in Linear Logic then Andreas Blass's notes on Linear Logic is as good a place to start as any.

Materials for 1b Computer Science.

Materials for Part III Mathematics .

Materials for Logic-For-Linguists.

Materials for Part II Mathematics .

Materials for Part IV Mathematics .

Materials for the M.Phil. in Computer Science .