Esta página em português Ajuda Autenticar-se

Você está em: Start > INF32153

Campus Map

Options

Algorithms and Abstract Data Types

Code:

INF32153

Sigla:

ATBD

Áreas Científicas
Classificação	Área Científica
OFICIAL	Informática

Ocorrência: 2021/2022 - 2S

Ativa?	Yes
Página Web:	https://moodle.ips.pt/2122/course/view.php?id=93
Unidade Responsável:	Departamento de Sistemas e Informática
Curso/CE Responsável:	Informatics Engineering

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
FC	3	Plano Estudos_FC_Brighstart	1	-	6	75	162
INF	211	Plano de Estudos	1	-	6	75	162

Docência - Responsabilidades

Docente	Responsabilidade
Bruno Miguel Nunes da Silva

Docência - Horas

Theorethical and Practical :	3,00
Practical and Laboratory:	2,00

Type	Docente	Turmas	Horas
Theorethical and Practical	Totais	4	12,00
	Patrícia Alexandra Pires Macedo		6,00
	Bruno Miguel Nunes da Silva		6,00
Practical and Laboratory	Totais	10	20,00
	Bruno Miguel Campos Pereira		2,00
	Miguel Angel Guevara López		6,00
	Patrícia Alexandra Pires Macedo		2,00
	Miguel Mourão Fialho Bugalho		6,00
	Aníbal Paulo Lopes da Ponte		4,00

Língua de trabalho

Portuguese
Obs.: Alguns conteúdos poderão ser fornecidos em inglês, devido à universalidade desta língua na área de IT.

Objetivos

The following goals are set:

- Knowing how to formalize an algorithm an analyse/discuss its algorithmic complexity;

- Knowing the concept of Abstract Data Type (ADT) and distinguish "specification" from "implementation";

- Knowing how to apply ADTs in problem-solving;

- Knowing how to specify new ADTs;

- Given its specification, knowing how to create a concrete implementation of an ADT and discuss/compare different possible implementations using different data structures;

- To apply algorithms and ADTs in solving real-world problemas, while identifying the most appropriate algorithms and ADTs.

Resultados de aprendizagem e competências

The student should acquire knowledge, skills and proficiency in:

- interpretation, analysis, specification and implementation of trivial computing algorithms, e.g., selection, search and sorting algorithms; iterative and recursive algorithms; when analyzing an algorithm emphasis will be given to its temporal complexity;

- specification and manipulation of linear data structures (static and dynamic) and hash tables;

- comprehension, use and implementation of most common abstract data types (collections) , e.g., Stack, Queue, List, Map;

- specification of new ADTs, choosing the appropriate data structure, its implementation and use;

- practical application of programmatic e in real-world problems using procedural programming, pointers and memory management.

Modo de trabalho

Presencial

Pré-requisitos (conhecimentos prévios) e co-requisitos (conhecimentos simultâneos)

Solid understanding of the characteristics and semantics of a programming language, namely:

- Data types and variables;

- Selection and repetition structures;

- Use of functions - return types and formal and actual arguments;

- Use of procedural programming.

Programa

1 - Introduction to the C programming language - procedural and modular; key differences relative to Java;

2 - Algorithms, algorithmic complexity and algorithm formalization in pseudo-code;

3 - Search and selection algorithms;

4 - Basic sorting algorithms (Bubble Sort and Selection Sort)

5 - Recursive vs. iterative algorithms; recursion.

- Exemplification of known recursive algorithms: Quick Sort ordering and Binary search;

6 - Structured data types, pointers and dynamic memmory management; arguments pass-by-value vs. pass-by-reference;

7 - Abstract Data Types in the C programming language; specification vs. implementation;

8 - Specification and usage of common abstract data types: Stack, Queue, List and Map;

9 - Definition and manipulation of linear data structures (static, semi-static and dynamic), i.e., array list and linked list;

10 - Implementation of Stack, Queue, List and Mapa abstract data types using linear data structures;

11 - Hash tables and its usage to implement the ADT Map.

Bibliografia Obrigatória

Bruno Silva; Linguagem C (e-book (unpublished))
Bruno Silva; Tipos Abstratos de Dados na Linguagem C (e-book (unpublished))
António Manuel Adrego da Rocha; Análise da Complexidade de Algoritmos, FCA, 2014. ISBN: 9789727227907

Bibliografia Complementar

António Manuel Adrego da Rocha; Estruturas de Dados e Algoritmos em C, FCA, 2014. ISBN: 9789727227693
Vinu Das; Principles of Data Structures using C and C++, New Age, 2006. ISBN: 978-81-224-2864-3
Fernando Mira da Silva; Apontadores e Estruturas de Dados Dinâmicas em C (e-book (unpublished))

Métodos de ensino e atividades de aprendizagem

TP Classes

Knowledge transfer using expository resources.

Consolidation exercises for concepts.

Provision of asynchronous feedback quizzes.

PL Classes

Application of acquired knowlege in real-world problems, through practical coding assignments.

Others

The curricular unit provides slides, in-house made books, exercises, tutorials and code repositories to aid learning, accessible through Moodle and GitHub platforms.

Software

GCC (Gnu Compiler Collection)
GDB (GNU Debugger)
Doxygen
Valgrind
Visual Studio Code

Tipo de avaliação

Distributed evaluation without final exam

Componentes de Avaliação

Designation	Peso (%)
Teste	50,00
Trabalho laboratorial	50,00
Total:	100,00

Componentes de Ocupação

Designation	Tempo (Horas)
Elaboração de projeto	30,00
Estudo autónomo	45,00
Frequência das aulas	75,00
Total:	150,00

Obtenção de frequência

Evaluation is divided into two independent components:

TP (Theorectical-Pratical) Evaluation - 50%

PL (Practical-Laboratory) Evaluation - 50%

The final score of each component must be >= 9,5 points. Consequently, the overall score must also be >= 9,5 points.

If the student fails at a component, then he only has to repeat the remaining one in the next evaluation epoch.

There are 3 consecutive evaluation epochs, namely:

- "Época de avaliação contínua" (during weekly classes);

- "Época normal", and;

- "Época de recurso".

Preliminar considerations:

Access to each Mini-Test is conditioned to answering 3 quizzes (weekly and multiple-choice) at Moodle. Each quiz is composed by 5 questions, can be answered an ilimited number of times and requires the student to correctly answer 3 out of 5 questions.

In the PL component there is an assiduity criteria that must be met to take into account the graded laboratories. The student must attend 8 laboratories with assignments (tutorial and graded). This criteria is not applied to students who possess the "working-student" statute.

Access to Test and Exams require previous registration at the Moodle platform. Access to the test may be denied if the student does not registrate himself during the established periods.

Graded laboratories are scored by levels [0, 5] and afterwards their arithmetic mean computed and extrapolated to [0, 20] points.

Submission of projects in the Moodle platform is mandatory; only then are they considered "delivered".

The following evaluation elements exist in "Época de avaliação contínua":

3 Mini-Tests

1 Test

5 Graded laboratories

1 Project

The following evaluation elements exist in "Época normal" and "Época recurso":

1 Exam

1 Project

Fórmula de cálculo da classificação final

Components and evaluation elements are represented by the following acronyms:

TP | "Teórico-prática" component

PL | "Prática-laboratorial" component

MT | Mini-Test (20 ~ 30 min - multiple-choice / online)

T | Test

L | Graded Laboratory

P | Project ("avaliação contínua" and "época normal")

EN | Exam of "Época normal"

ER | Exam of "Época de recurso"

PR | Project of "Época de recurso"

Preliminar considerations:

All projects require a presentation and oral discussion; the individual participation of group members is also assessed throught commit analysis in GitHub Classroom; this may result in different individual scores.

Score calculation for "Época de avaliação contínua":

TP = ([20 + 15 + 15]% * MT) + (50% * T)

PL = (20% * L) + (80% * P)

If the assiduity criteria is not met, then PL = 100% * P.

If the student did not attend the 5 graded laboratories, then the rest will be scored with 0 (zero) for the calculation of L.

Score calculation for "Época de avaliação normal":

TP = 100% * EN

PL = 100% * P

Score calculation for "Época de avaliação de recurso":

TP = 100% * ER

PL = 100% * PR

Minimum required scores:

T | 7 points

EN / ER | 9,5 points

P | 9 points

PR | 9,5 points

Melhoria de classificação

The improvement of grades is only allowed in "Época de Recurso" and with a valid registration in the Academic Division.

- The TP component can only be improved through Exam.

- The PL component can only be improved through Project.

Observações

Plagiarism

All projects are submitted to plagiarism detection, through cross-checking.

Any plagiarism situation leads to the immediate anullment of the envolved projects, regardless of source/destination and communicated to the appropiate instances for sanctionatory measures.

Oral discussions

An oral discussion may be requested after any evaluation for validation purposes.

Covid

Application of rights and duties conferred by IPS Presidency ordinance.

Moodle

Access to the Moodle platform is allowed only to enrolled students, by means of a password provided by the teachers.

Ommited cases

Ommited cases are decided by the responsible of the curricular unit.

Recomendar Página Voltar ao Topo