## Department of Mathematics & Computer Science | ||||

Credits: 20 |
Convenor: Dr. Stefan Dantchev |
Semester: 2 |

Prerequisites: |
||

Assessment: |
Coursework: 30% | Three hour exam in June: 70% |

Lectures: |
48 | Problem Classes: |
12+24(voluntarily) |

Tutorials: |
none | Private Study: |
78 |

Labs: |
none | Seminars: |
none |

Project: |
none | Other: |
none |

Surgeries: |
12 | Total: |
150 |

There is no prerequisite knowledge required for this module apart from some topics from GCSE Mathematics.

The main purpose of this course is to teach the basic concepts from Discrete Mathematics and Logic that are needed in the study of Computer Science. While the main purpose is to learn the necessary Mathematics, the course is taught from a Computer Science viewpoint throughout. It is divided into two relatively independent parts.

The first one, Logic, is motivated by Formal Specifications. We start by giving a (somewhat informal) idea of a mathematical argument and then go on to cover several topics from Propositional and Predicate Logic such as the syntax, truth tables, tautologies, semantic tableaux, quantifiers, models, predicate tableaux. We then introduce some topics which are useful in describing computational systems such as sets, relations, functions, and finish with Formal specifications by introducing a subset of a real specification language, VDM .

The second part, Discrete Mathematics, is motivated by Analysis of Algorithms. We start by revising some fundamental concepts such as number systems, polynomials, solving simple equations. We then introduce more advanced topics such as induction (both inductive definitions and inductive proofs), graphs, matrices, equivalence relations (including modular arithmetic), counting. We finish by using all these to analyse some simple sorting and searching algorithms.

This material will be described in the lectures (four per week); there will also be weekly problem classes (for sorting out problems, including difficulties with the assessed work) and a surgery session (for going through the previous worksheet). The course is based on a textbook. Few topics, which are not covered by the textbook, can be found in the handouts we will distribute.

Part 1. Logic and Formal Specification.

- An introduction to reasoning. The notion of proof and examples
of proofs. Direct proofs. Proofs by contradiction and
contraposition.
- Propositional logic. Syntax. Debracketing. Main connectives.
Turning English statements into formal logic.
Truth tables and valuations. Logical equivalence.
Interdefinability of connectives. Valid arguments and
tautologies. Satisfiability.
Semantic tableaux: tableaux rules, open and closed tableaux.
- Predicate logic. Predicates and names. Quantifiers. Models
and counter-examples.
Predicate tableaux: tableaux rules, open and closed tableaux.
- Introduction to formal specifications. The idea of a specification.
Basic constructs: types, attributes, initializations, invariants and
methods. Pre-conditions and post-conditions.
- Sets. Elements, subsets and proper subsets. Operations on sets
(union, intersection, difference). Basic properties of these
operations (including De Morgan's laws). Power sets. Orders of sets.
Use in specifications.
Ordered pairs, Cartesian products. Relations. Functions: partial
and total functions. Use in specifications. Non-determinism and
determinism.
Sequences. Concatenation and other operations. Use in specifications.

Part 2. Discrete Structures and Algorithm Analysis.

- Number systems (integers, rationals, reals). Polynomials
(including addition, subtraction and multiplication of
polynomials). Solving linear and quadratic equations.
- Inductive definitions. Proof by induction. Summation of
arithmetic series.
- Graphs. Paths, trees and branches. Composition of
relations. Matrices (including adjacency matrices of
graphs) and matrix operations.
- Equivalence relations. Partitions and equivalence classes.
Modular arithmetic.
Composition of functions. Injections, surjections and
bijections. The identity map. Inverse of a function.
- Factorials. Exponentials, logarithms and their properties.
Counting: permutations and combinations. Pascal's triangle.
Elementary probability. Simple recurrence relations and
their solution. Summation of geometric series.
- Basic concepts of algorithm analysis applied to some simple
sorting and searching algorithms.

Author: *N. Rahman*, tel: +44 (0)116 252 3902

Last updated: 2003-09-23

MCS Web Maintainer

This document has been approved by the Head of Department.

© University of Leicester.