Discrete Mathematics

Discrete mathematics is now a day a substantial part of the theoretical and practical knowledge of future computer engineers, both abstract and instrumental. Abstract as it feeds on the roots of applied abstract algebra, and instrumental in the use of algorithmic and procedural aspects of that in relation to the real world: work planning, program design, use of counting techniques, control and detection of errors in the transmission of information, security of computer systems, software engineering, etc.

With this subject, it is intended:

- to contribute to the education of future graduates in engineering, enabling robust and appropriate training in discrete mathematics skills.
- to promote the use of different representations (symbolic, graphical, matrix) and a variety of methods of reasoning (induction, recursion, deduction) as a means to promote the integration of concepts and procedures derived from the contents of the material.
- to become familiar with the mathematics involved in algorithmic thinking (specification, verification and complexity).
- to encourage attitudes of criticism when confronted with different types of solutions, search, effort and perseverance in the face of difficulties and communication using the appropriate terminology.

In the labs, we will be using SageMath, a free, open-source CAS, to begin programming different algorithms related to the matter.

1. Algorithms and numbers
Algorithms: complexity. The Integers and division. Euclid's algorithm. Congruence. Representation of numbers. Arithmetic with big integers. Applications. Public key Cryptography.

Teaching
Hours lecture / interactive / practices: 8 / 3 / 6

Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 5 / 2 / 5 / 0.75

2. Basic counting techniques
Addition and multiplication principles. The pigeonhole principle. Permutations and combinations. The binomial theorem. The inclusion-exclusion principle.

Teaching
Hours lecture / interactive / practices: 5 / 2 / 3

Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 5 / 3 / 4 / 0.5

3. Recursion
Recursive definitions. Recursive algorithms. Program verification. Advanced enumeration techniques: recurrence relations. Solving recurrence relations. Generating functions.

Teaching
Hours lecture / interactive / practices: 5 / 2 / 2.5

Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 4 / 2/ 3 / 0.75

4. Graphs
Types of graphs. Representation of graphs. Connectedness. Euler and Hamilton paths. Dijkstra's shortest path algorithm. Planar graphs. Graph colouring. Trees. Spanning trees and shortest paths.

Teaching
Hours lecture / interactive / practices: 5 / 2 / 2.5

Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 4 / 2 / 2 / 0.5

5. Boolean algebras
Boolean functions and switching functions. Disjunctive and conjunctive normal forms. Logic gates. Circuit minimisation.

Teaching
Hours lecture / interactive / practices: 2 / 1 / 1

Independent / supervised learning activities
Hours study / problem solving / computer practice / tutorial: 2 / 1 / 1 / 0.5

BASIC:
Aguado, F., Gago, F. et al., Problemas resueltos de Combinatoria. Laboratorio con SageMath, Paraninfo, 2018.
Rosen, K. H., Matemática Discreta y sus Aplicaciones, McGraw-Hill (5ª ed.) 2004.
Vieites, A.M., Aguado, F. et al., Teoría de Grafos: Ejercicios resueltos y propuestos. Laboratorio con Sage, Paraninfo, 2014.


COMPLEMENTARY:
Bard, G. V., SageMath for Undergraduates. http://www.gregorybard.com/SAGE.html
García Merayo, F., Matemática discreta, Paraninfo, Thomson Learning, 2001.
García Merayo, F., Hernández, G., Nevot, A., Problemas resueltos de Matemática discreta, 2ª edición ampliada, Paraninfo, 2018.
Grimaldi, R. P., Matemáticas Discreta y Combinatoria, Addison-Wesley Iberoamericana, 1997.
Johnsonbaugh, R., Matemáticas Discretas, Pearson Prentice Hall (6ª ed.) 2005.
Levasseur, K. et al., Discrete Mathematics for Computer Science, 2020.
https://icsatkcc.github.io/Discrete-Math-for-Computer-Science/dmcs.html
Lipschutz, S., Lipson, M., 2000 Solved Problems in Discrete Mathematics, Schaum, Mc-Graw-Hill, 1992.

http://doc.sagemath.org/

TRANSVERSAL/GENERIC
Within TR1, TR2 and TR3:
Problem-solving capacity. Analysis and synthesis capacity. Organizing and planning capacity. Information managing capacity (collect and analyse the information). Problem-solving. Decision making. Critical reasoning. Adaptability to new situations. Putting knowledge into practice. Ability to do independent and collaborative work. Creativity.

SPECIFIC
On top of its contribution to CG5, CG8, CG9 and CG10,
- Cognitive (to know):
Within RI6:
Acquisition of the basic concepts of the subject: algorithms, the integers, counting methods, theory of graphs and Boole algebras. To know applications of discrete mathematics to computation.

- Procedures/instrumental (to know-how):
Within FB1 and FB3:
To manage modular arithmetic and apply it in different number representation systems, computation with big integers and public-key cryptography. To know how to apply the basic techniques to count in diverse problems. To know some recursive algorithms and to apply them in concrete situations. Apply graph theory in areas relating to computation. To manage the software Sage and apply the learning algorithms to solve the problems treated in the course.

- Attitudinal (to be):
Rigour and clarity, oral and written expression. Logical reasoning and identification of errors in procedures. Adaptability. Abstraction. Organization and planning skills. Criticism when confronted with several types of solutions. Analysis capacity in problem-solving.

We will devote the expository class time to presenting the essential elements that make up this subject (FB3, CG8). The interactive classes, conducted in small groups, will be used to solve exercises (TR1, TR3, FB1, FB3, CG8, CG9, CG10) and to do computer work (TR1, TR3, FB1, FB3, CG5, CG8, CG9, RI6). Also, study topics and problems will be handed out for the students to solve (TR1, TR2, TR3, CG8, CG9, CG10) and to submit/present the results in the tutorial classes in very small groups (TR2, CG9), where also support will be provided.

There will be open two online courses: one in the Virtual Campus in which, in addition to having various support materials, we will keep a daily record of what is treated in each class session, along with the programming of activities (TR1, TR3, CG9), some of which will be carried out in groups (TR2), and another one at CoCalc that will serve as support and control for lab interactive classes.

There is a call with two opportunities.

A method of continuous evaluation will be followed, through directed academic activities, taking into account the work done, both individually (TR1, TR3, CG8, CG9, CG10) and in groups (TR2), and especially the one done with the computer (FB1 , FB3, RI6, CG5), in which students must demonstrate their knowledge of the subject; and a final exam (TR1, FB1, FB3, RI6, CG9).

First opportunity (January / February)

• Final theoretical-practical exam: 45%
• Final exam of practices in the computer: 30%
• Continuous assessment (virtual course, problems, and computer practices carried out individually). Repeating students must complete all the activities convened through the virtual campus: 25%

In order to pass the subject, it will be essential to carry out the practical work, take the exams and obtain a total of 5 points on average, with a minimum of 40% both in the final theoretical-practical exam and in the final exam of practices in the computer.

Second chance (June / July)

The evaluation of the students will be based on a final exam with the following percentages:

• Final theoretical-practical exam: 50%
• Final exam of practices in the computer: 30%
• Continuous evaluation: 20%

Those who take one of the final exams or participate in at least 75% of the continuous assessment activities will be considered presented.

In the case of fraudulent behaviour in assignments, tests, or exams, the provisions of the "Regulations for the evaluation of the academic performance of students and grades review" will apply, in particular, those in Article 16:
Committing fraud in any assignment or test required in the evaluation of the subject will imply the qualification of fail in the corresponding call, regardless of the disciplinary process that may be followed against the offender.

Class meeting:
25 hours of theory classes
10 hours of problems in small groups (seminars)
15 hours of work in small groups (laboratories)
3 hours of tutoring in very small groups
3 hours final written exam
2 hours final exam on the computer

Independent work:
45 hours of self-study related to classes (20 hours for theory, for problems 10, 15 computer practice)
25 hours to work on the proposed bulletins of problems
15 hours to program computer solutions to problems set
7 hours of evaluation activities on the virtual campus

Total workload: 150 hours

Regular attendance and participation in class and lab are expected. Moreover, each student should work out, by him/herself or with others, every single question left out in the lectures.

The student must understand the proofs of theory relating them to the techniques of resolution of practical problems (application of the properties of Boolean algebras to minimisation of circuits, use of Euclid's algorithm, use of basic techniques to count and distribute objects, to program several recursive algorithms, application of graph theory to represent data or network design).

Efforts must be made to apply the reasoning of the theoretical proofs to the resolution of problems and implement these methods of solution in the established package of symbolic computation.

Students are advised to take advantage of the tutorials to delimit the work to be done in the assignments and in the practices, to work out the exams along with the classes and to exploit the possibilities of the online course (self-evaluation tools, commented online exams, frameworks of the several home assignments, past courses exams with solutions, etc.).