Mathematics for computer scientists

These notes are by RWK for this half-module. The home page is HERE.

Revision notes

As promised, here are the final revision notes. See also the main HOMEPAGE.

The revision lectures covered the most important parts of the latter part of the course. Unfortunately it was only possible to have two such lectures. Watch this space or email for a third (but don't expect it - I think it probably won't happen). You can always email me or come to see me to discuss any other points to do with the course.

The main points discussed in the revision lectures were...

• Don't give up! You can get good marks by saying something sensible, even if you can't answer the whole question.
• Write something, and write legibly!
• Learn and use definitions (e.g. of the various axioms for an equivalence relation) in your proofs.
• Use the basic structure of induction proofs to help you complete the proofs more easily.
• Use common sense on counting problems.
• Give reasons to your answers so that even if your answer is wrong you still obtain partial credit.

Some material couldn't be covered in the revision lectures. That does not mean to say it wasn't important! Revise it all carefully!. The main topics covered in the course includes...

• Numbers (naturals, the set "IN" is ALWAYS {1,2,3,4,...}); integers; rationals; reals (including decimal expansion fractions and square roots).
• Sets, set notation, algebra of sets.
• Functions (domain, codomain, range, onto, 1--1, etc).
• Relations, especially equivalence and order relations.
• Induction.
• Counting, including inclusion-exclusion.
• Binomial coefficients and the Binomial Theorem.
• Graphs (see below).

Graphs were not covered in the revision lectures, but could come up in the exam. You should check the notes available elsewhere on these web pages, especially the OHPs from my lectures and the PDF notes. These contain ALL that you need to learn. You should be confident with the idea of a graph as a set of vertices and edges, the examples of the complete graphs K_n and the cycle graphs C_n. (All graphs you will encounter will be "simple" as defned in the notes.) You should be happy with the idea of cycles in a graph, whether a graph is connected or not and the idea of a tree as a connected graph with no cycles.

The language of graphs may be used in counting problems. A typical example is given in the last OHP slide where the number of C₄'s in K₅ was counted. Some further counting problems of this type are in Exercises 6.2, 6.4, and 6.5 in the textbook. Once again, think carefully and use common sense! The questions will not be hard or unreasonable.

Finally... GOOD LUCK!

Richard

These pages are written by Richard Kaye please email me about any inaccuracies you may find in these pages.