Publication in the Diário da República: Despacho n.º 6191/2020 - 09/06/2020
2 ECTS; 1º Ano, Anual, 34,0 TP , Cód. 602430.
Lecturer
- Maria Manuela Morgado Fernandes Oliveira (1)(2)
(1) Docente Responsável
(2) Docente que lecciona
Prerequisites
Not applicable
Objectives
Knowledge and mastery of introductory aspects of computer science, namely data storage, data structures and control structures, functions, but also knowledge of algorithms in the areas of Ordering and Research, Graphs and Digraphs. Perception of the already existing applications of classic algorithms essential in software development for the most diverse areas. Guarantee access to inclusive, quality and equitable education and promote opportunities for lifelong learning for all. (Sustainable Development Goal 4, according to the 2030 Agenda for Sustainable Development, adopted by the United Nations General Assembly in September 2015)
Program
Introductory aspects: Brief introduction to Python in Windows environment; data, data structures and control structures; vectors and matrices; recursive and non-recursive functions. Sorting and searching algorithms: Bubblesort, sorting by selection, sorting by insertion, Shellsort, Mergesort and Quicksort. Linear search and binary search. Graph algorithms: definition and fundamental properties of graphs; data structures for graph representation, storage and manipulation; construction of paths and cycles in graphs; related graphs; trees; extension to digraphs and networks. Applications: DFS algorithm for the construction of a tree generating a connected graph; algorithm for the construction of an eulerian cycle; the problem of determining a minimum cost generator tree: Kruskal and Prim algorithms; the problem of determining a minimum cost path in a network: Dijkstra and Floyd-Marshall algorithms; Maximum flow problem in a network: Ford-Fulkerson algorithm. Extensions: basic notions about heuristics; application to the traveling salesman problem.
Evaluation Methodology
Continuous Assessment: Realization of a test (written and computational), work in the classroom and an interim project. The project is computational work and is worth 20 values. The test is rated from 0 to 20 points. The works are priced from 0 to 20 values. The final grade will be given by the weighted average of the three previous items, 50% for the written test, 30% for the final project and 20% for the work in the classroom.
Assessment by Exam: Students admitted to the exam or those approved who wish to improve their grade, can take an exam in normal season. This exam is divided into two aspects: written and computational and covers all the subjects taught. Students who fail in the normal season or who intend to improve their grade can also take an appeal exam, as described. The grades of the works may or may not be carried out for examination, according to the student's choice. Also giving the chance to improve, once, the work until the date of the exam, maintaining the grade of the test.
Bibliography
- Aho, Hopcroft, Ullman, A. (1974). The Design and Analysis of Computer Algorithms. (pp. 1-470). Massachusetts: Addison-Wesley
- Fernandes, M. (0). Apontamentos da disciplina. Acedido em 12 de setembro de 2018 em www.e-learning.ipt.pt
- Rosen, K. (2012). Discrete Mathematics and its Applications. (pp. 641-803). New York: McGraw-Hill
- Wirth, N. (1976). Algorithms + Data Structures = Programs. (pp. 1-212). New Jersey: Prentice-Hall
Teaching Method
Classes take place predominantly in a computational environment using the Python programming language. It is proposed to recognize the applicability of some classic algorithms, their theoretical understanding and proceed to their implementation.
Software used in class
Anaconda, using Sypder to develop algorithms in Python, in Windows environment.
