Go to:
Logótipo
You are in:: Start > M2007

Algorithms in Discrete Mathematics

Code: M2007     Acronym: M2007     Level: 200

Keywords
Classification Keyword
OFICIAL Mathematics

Instance: 2024/2025 - 1S Ícone do Moodle

Active? Yes
Responsible unit: Department of Mathematics
Course/CS Responsible: Bachelor in Mathematics

Cycles of Study/Courses

Acronym No. of Students Study Plan Curricular Years Credits UCN Credits ECTS Contact hours Total Time
L:B 0 Official Study Plan 3 - 6 48 162
L:CC 3 study plan from 2021/22 2 - 6 48 162
3
L:F 0 Official Study Plan 2 - 6 48 162
3
L:G 0 study plan from 2017/18 2 - 6 48 162
3
L:M 64 Official Study Plan 2 - 6 48 162
3
L:MA 57 Official Study Plan 2 - 6 48 162
L:Q 0 study plan from 2016/17 3 - 6 48 162

Teaching Staff - Responsibilities

Teacher Responsibility
Pedro Ventura Alves da Silva

Teaching - Hours

Theoretical classes: 1,85
Theoretical and practical : 1,85
Type Teacher Classes Hour
Theoretical classes Totals 1 1,846
Pedro Ventura Alves da Silva 1,846
Theoretical and practical Totals 2 3,692
Pedro Ventura Alves da Silva 3,692

Teaching language

Suitable for English-speaking students

Objectives





The student should know and be able to apply the concepts and basic results covered in the course. It is intended that this unit contribute to the development of skills in the fields of discrete mathematics and algorithms.





Learning outcomes and competences

It is intended that by the end of this course the student can:
• Complete and give structure to some previously acquired basic knowledge;

• Solve problems through structured elementary methods;
• Understand and apply basic and universal concepts, that are basic for several tools of various sciences, in a context close to the applications;
• Use (and create, whenever possible) algorithmic solutions to various problems.
• Be able to use computational tools to solve problems.

Working method

Presencial

Program





1. Revision of some basic principles of combinatorics: counting, listing, ordering, sets and multisets, counting functions of certain types (one-to-one, onto, increasing, decreasing), partitions, etc.; the combinatorics of permutations.

2. Decision trees and recursion: basic definitions, order, rank, depth-first and breadth first; recursive algorithms, sorting, Gray codes; recurrence relations, characteristic equation, Fibonacci and Catalan sequences, derrangements.

3. Introduction to graph theory: definitions and examples, isomorphism, random graphs; digraphs and flows; Euler circuits and hamiltonian cycles; trees, Prim and Kruskal algorithms, depth-first and breadth first.

4. Introduction to the analysis of algorithms. [Time permitting.]





Mandatory literature

Bender Edward A. 1942-; Mathematics for algorithm and systems analysis

Complementary Bibliography

Bondy J. A.; Graph theory with applications. ISBN: 0-333-17791-6
Cormen Thomas H.; Introduction to algorithms. ISBN: 9780262031417 hbk
Sedgewick Robert 1946-; An introduction to the analysis of algorithms. ISBN: 978-0-201-40009-0

Teaching methods and learning activities





Lectures and classes: The contents of the syllabus are presented in the lectures, where examples are given to illustrate the concepts. There are also practical lessons, where exercises and related problems are solved. All resources are available for students at the unit’s web page.





Software

SageMath

keywords

Physical sciences > Mathematics > Algorithms
Physical sciences > Mathematics > Combinatorial analysis

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation Weight (%)
Teste 100,00
Total: 100,00

Amount of time allocated to each course unit

designation Time (hours)
Estudo autónomo 114,00
Frequência das aulas 48,00
Total: 162,00

Eligibility for exams

Without requirements.

Calculation formula of final grade




The syllabus will be divided into two parts. each one evaluated by a test worth 10 points.


The second test is held simultaneously with the first season exam. In the same occasion, it is possible to repeat the first test, and the marks obrtained prevail for those students wishing it.








First season exam:

1. The final mark is the sum of the marks obtained in each test, except possibly in the following case:
2. Marks above 18 require an extra proof (oral or written).

Second season exam:

1. In the second season exam, students may repeat both tests or just one of them (except when they are just trying to improve their mark).

2.The mark of one (but only one) of the tests may be replaced a posteriori by the mark obtained in the respective test of the first season, in the version which favours most the student (except when they were approved before).


3. The final mark of the second season is the sum of the marks obtained in both tests, rounded to integers, except possibly in the following cases:


4. Students having obtained a mark equal or above 8,0 and below 9,5 have access to a complementary proof to decide if they are approved (with 10 points) or if they fail (with 8 or 9 points).


5. Marks above 18 require an extra proof (oral or written).




Special assessment (TE, DA, ...)

Any type of special student evaluation may take one of the following forms: exclusively an oral examination; an oral examination plus a written examination, the student being required to pass both of them; only a written examination. The option for one of them is the sole responsibility of the professors in charge of the course unit.

Observations

Article 13 of General Regulations for Student Evaluation at the levels of First Cycle, Integrated Masters, and Second Cycle at U.Porto, approved on May 19, 2010 (cf. http://www.fc.up.pt/fcup/documentos/documentos.php?ap=3&ano=2011): "Fraud committed during an exam, in any form, implies the annulment of the exam and the communication to the statutorily competent organ for possible disciplinary action."

Any student may be required to take an oral examination should there be any doubts concerning his/her performance on the assessment pieces.
Recommend this page Top
Copyright 1996-2025 © Faculdade de Ciências da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z  I Guest Book
Page created on: 2025-06-14 at 21:48:54 | Acceptable Use Policy | Data Protection Policy | Complaint Portal