Course: 2022/2023

Discrete mathematics

(16489)

Requirements (Subjects that are assumed to be known)

Calculus I and II, and Linear Algebra

CB1: To show enough skills and knowledge in an area that, although grounded on high school and mostly learnt from textbooks, also includes the forefront advances of the field.
CE1: Ability to solve mathematical problems arising in Data Science and Engineering. Skills to apply knowledge on: Algebra, Geometry, Differential and Integral Calculus, Numerical Methods, Numerical Algorithms, Statistics, and Optimization techniques.
CG2: To master basic scientific and technical matters so that the student can learn new methods and new technologies, and adapt to new situations.
CG4: Ability to solve technological, computer, mathematical, and statistical problems that might arise in Data Science and Engineering.
CG5: Ability to solve problems from different subjects that are expressed mathematically, using numerical algorithms and computational techniques.
CT1: Skills to communicate knowledge, either orally or in written reports, both in front a specialized as well as a nonspecialized audience.
CT4: To develop personal abilities such as initiative, responsibility, negotiation, emotional intelligence, etc., as well as to master enough calculation tools so as to be able to adapt to the technical requirements of any professional activity.
RA1: To adquire advanced knowledge and deeply understand both the theoretical and practical aspects of typical Data Science and Engineering methods, even those at the forefront of the discipline.
RA2: To be able to apply their knowledge and know-how -- as well as to provide their own arguments or procedures -- to complex problems arising in professional and specialized domains requiring creative and innovative ideas.

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.