Discrete Mathematics and Mathematical Reasoning

This module runs in the first semester. Lecture hours are: The first and introductory lecture will take place on Monday 18 September.

Summary of intended learning outcomes

- Reason mathematically about basic (discrete) structures (such as numbers, sets, graphs, and trees)used in computer science.
- Use of mathematical and logical notation to define and formally reason about mathematical concepts such as sets, relations, functions, and integers, and discrete structures like trees, graphs, and partial orders;
- Evaluate elementary mathematical arguments and identify fallacious reasoning
- Construct inductive hypothesis and carry out simple induction proofs;
- Use graph theoretic models and data structures to model and solve some basic problems in Informatics (e.g., network connectivity, etc.)
- Prove elementary arithmetic and algebraic properties of the integers, and modular arithmetic, explain some of their basic applications in Informatics, e.g., to cryptography.
- Compare the asymptotic growth growth rates of basic functions; derive asymptotic bounds, and limits, for simple series and recurrence relations. Use these to derive bounds on the resource consumption (e.g., running time) of simple iterative and recursive algorithms.
- Calculate the number of possible outcomes of elementary combinatorial processes such as permutations and combinations.
- Be able to construct discrete probability distributions based on simple combinatorial processes, and to calculate the probabilities and expectations of simple events under such discrete distributions.


Weekly tutorial sheet exercises. Discussed in tutorial groups. The last exercise on each tutorial sheet is marked, and students must submit the solution by the due date each week (see here).


The final exam counts for 85%, and the assessed assignments count (marked tutorial sheet questions) count for 15%.
This page is maintained by the course lecturers Kousha Etessami and Colin Stirling.

Home : Teaching : Courses 

Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK
Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk
Please contact our webadmin with any comments or corrections. Logging and Cookies
Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh