Course: 2022/2023

Discrete mathematics

(16489)

Requirements (Subjects that are assumed to be known)

Calculus I and II, and Linear Algebra

Skills and learning outcomes

Description of contents: programme

1. Arithmetic
1.1 Integers
1.2 Division algorithm
1.3 Largest common divisor: Euclid's algorithm
1.4 Prime numbers and the Fundamental Theorem of Arithmetic
1.5 Diophantine equations
1.6 Congruences: modular arithmetic
2. Elementary set theory
2.1 Basic notions
2.2 Set operations and properties
2.3 Functions
2.4 Relations: equivalence and order
2.5 Cardinality
3. Combinatorics
3.1 Elementary counting rules: sum and product
3.2 Pigeon-hole principle
3.3 Permutations and combinations
3.4 Binomial coefficients
3.5 Principle of inclusion and exclusion
3.6 Derangements
3.7 Generating functions
3.8 Partitions
3.9 Recurrences
4. Introduction to groups
4.1 Law of composition
4.2 Groups and subgroups
4.3 Homomorphisms and isomorphisms
4.4 Cyclic groups
4.5 Cosets, Lagrange's theorem, and quotient groups
4.6 Applications to cryptography
5. Fundamentals of graph theory
5.1 Definitions and examples
5.2 Matrix representations
5.3 Eulerian and Hamiltonian graphs
5.4 Trees
5.5 Optimisation and matching
5.6 Planar graphs
5.7 Directed graphs
5.8 Networks

Learning activities and methodology

AF1: THEORETICAL AND PRACTICAL LECTURES. These are meant to provide the students the basic knowledge of the topic. They will be provided classroom notes as well as reference textbooks to help them follow the lectures and work them through. Exercises and problems will be solved in class, and midterm exams will be performed to test progress.
AF3: PERSONAL WORK AND WORK IN GROUPS.
AF9: FINAL EXAM. Overall evaluation of the students' knowledge, skills, and abilities learn through the course.
MD1: THEORY CLASS. The teacher will lecture, with the help of computer and audiovisual media, about he main topics of the subject. Materials and biblography will be provided to supplement these lectures.
MD2: PRACTICAL CLASS. Practical exercises and problems will be solved, either individually or in groups.
MD3: TUTORSHIPS. The student will received assistance by the teacher about difficult matters of the topic, either individually or in groups.

Assessment System

- % end-of-term-examination 60
- % of continuous assessment (assigments, laboratory, practicals...) 40

Basic Bibliography

- K.H. Rosen. Discrete Mathematics and Its Applications, 7th ed.. McGraw-Hill. 2007
- N. Biggs. Discrete Mathematics, 2nd ed.. Oxford University Press. 2003
- R.P. Grimaldi. Discrete and Combinatorial Mathematics: An Applied Introduction, 5th ed.. Addison Wesley. 2004

Additional Bibliography

- M. E. J. Newman. Networks: An Introduction. Oxford University Press. 2010
- N. C. Carter. Visual Group Theory. Mathematical Association of America, Inc.. 2009
- R. J. Wilson. Introduction to Graph Theory, 4th ed.. Addison-Wesley. 1996
- R. Sedgewick, P. Flajolet. An introduction to the analysis of algorithms, 2nd ed.. Addison-Wesley. 2013

- H. G. Wilf · generatingfunctionology : https://www.math.upenn.edu/~wilf/gfology2.pdf

(*) Access to some electronic resources may be restricted to members of the university community and require validation through Campus Global. If you try to connect from outside of the University you will need to set up a VPN

The course syllabus may change due academic events or other reasons.