Undergraduate Course: Discrete Mathematics and Mathematical Reasoning (INFR08023)
Course Outline
| School | School of Informatics |
College | College of Science and Engineering |
| Credit level (Normal year taken) | SCQF Level 8 (Year 2 Undergraduate) |
Availability | Available to all students |
| SCQF Credits | 20 |
ECTS Credits | 10 |
| Summary | *Please note that this course has been replaced by a 20-credit course "Discrete Mathematics and Probability" (INFR08031) from 2020/21.*
Discrete mathematics and formal mathematical reasoning. |
| Course description |
1) Foundations (Chapters 1 & 2 of [Rosen])
2) Basic number systems, and rudimentary algorithms on numbers and matrices (Chapter 3, [Rosen])
3) Induction and Recursion (Chapter 4 [Rosen])
4) Basic Counting (Chapter 5 [Rosen])
5) Graphs (and binary relations): [Chapter 9, and parts of Chapter 8]]
6) Trees: (Chapter 10 [Rosen])
7) Discrete probability [Chapter 6, plus some supplementary material]
|
Information for Visiting Students
| Pre-requisites | None |
| High Demand Course? |
Yes |
Course Delivery Information
| Not being delivered |
Learning Outcomes
On completion of this course, the student will be able to:
- Use of mathematical and logical notation to define and formally reason about mathematical concepts such as sets, relations, functions, and integers, and discrete structures, including proof by induction
- 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
- 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
|
Reading List
REQUIRED TEXTBOOK:
* Kenneth Rosen, Discrete Mathematics and its Applications, 7th Edition, McGraw-Hill, (due to be published in July), 2012. Alternatively, 6th Edition, 2007.
Additional Reference Material:
* MIT Mathematics for Computer Science Lecture notes (online) |
Contacts
| Course organiser | Prof Colin Stirling
Tel: (0131 6)50 5186
Email: |
Course secretary | Ms Kendal Reid
Tel: (0131 6)51 3249
Email: |
|
|
University Homepage