Algorithms in Discrete Mathematics
Keywords |
Classification |
Keyword |
OFICIAL |
Mathematics |
Instance: 2020/2021 - 1S
Cycles of Study/Courses
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, namely the SageMath software.
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 without 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 |
106,00 |
Frequência das aulas |
56,00 |
Total: |
162,00 |
Eligibility for exams
Students must attend at least one of the 3 tests comprising the distributed assessment.
Calculation formula of final grade
1. On the Normal Exam period (Época Normal), the total mark is the sum of the marks on each of 3 tests:
Test 1: This test is marked for a total of 6 points and it will take place during class period, at a date agreed upon with the students.
Test 2: This test is marked for a total of 4 points and it will take place during class period, at a date agreed upon with the students.
Test 3: This test is marked for a total of 10 points and it will take place on the date set for the exam of the Normal Exam period.
2. On the Makeup Exam Period (Época de Recurso) the total mark is obtained on an exam set for a total of 20 points.
The exam will be divided into 3 parts, allowing the students who have not yet been approved in this class to use the score they have previously obtained on one or more of the 3 tests from the Normal Exam period (Época Normal) in the corresponding part of this exam. In any of the parts, the grade which will be considered is the maximum of the grade obtained on the exam and the grade possibly obtained on the corresponding test in the Normal Exam period (Época Normal).
During the semester, at times duly announced in calss or through Moodle, the students may be given the oportunity to work on small, optional assignments to potentially suplement their grade on one of the tests. None of these assignments can be worth more than 1 point and the total amount of points which can be used to suplement the test grades cannot exceed 3.
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.
Jury:
Samuel António de Sousa Dias Lopes
Pedro Ventura Alves da Silva