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: 2022/2023 - 2S

Ativa?	Yes
Página Web:	https://moodle.ips.pt/2223/course/view.php?id=1858
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	2	Plano Estudos_FC_Brighstart	1	-	6	75	162
INF	189	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	3	9,00
	Bruno Miguel Nunes da Silva		3,00
	Patrícia Alexandra Pires Macedo		6,00
Practical and Laboratory	Totais	8	16,00
	Aníbal Paulo Lopes da Ponte		6,00
	Bruno Miguel Nunes da Silva		4,00
	Miguel Mourão Fialho Bugalho		6,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 objectives are outlined:

- Knowing how to formalize algorithms and analyze/discuss their temporal algorithmic complexity;

- Know 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 derive a concrete implementation for an ADT and knowing how to discuss/compare different implementations, varying the data structure;

- Apply algorithms and ADTs in solving real problems, identifying the most appropriate algorithms and ADTs.

Resultados de aprendizagem e competências

That the student acquires and consolidates knowledge, skills and competences in:

- Interpretation, analysis, specification and implementation of trivial computing algorithms, eg, selection, search, sorting algorithms; iterative and recursive algorithms; in the analysis component, emphasis will be given to the temporal complexity of the algorithms;

- Specification and manipulation of linear data structures (static and dynamic) and scatter tables;

- Understanding, use and implementation of the most common abstract data types (collection type), eg, Stack, Queue, List, Map;

- Specification of new ADTs, choice of an appropriate data structure and its implementation and use;

- Practical application of the syllabus in real problems using the procedural and imperative programming paradigm, including domain pointers and dynamic memory management.

Modo de trabalho

Presencial

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

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

- Data types and variables;

- Selection and repetition structures;

- Using functions - formal and current return types and arguments.

- Use of procedural programming.

Programa

1. Introduction to the C language - procedural and modular; differences from the Java language.

2. Algorithms, algorithmic complexity and formalization of algorithms in pseudo-code;

3. Search and selection algorithms;

4. Simple sorting algorithms O(n²) - Bubble Sort and Selection Sort;

5. Recursive vs. Iterative Algorithms; recursion;

- Exemplification of known recursive algorithms: Quick Sort sorting algorithm and binary search.

6. Structured data types, pointers and dynamic memory management; passing arguments by copy vs. pass by reference.

7. Abstract Data Types in the C Language; specification vs. Implementation;

8. Specification and use of the most common abstract data types (collection type): Stack, Queue, List and Map.

9. Definition and manipulation of static, semi-static and dynamic linear data structures, ie, arrays and linked lists;

10. Implementation of abstract data types Stack, Queue, List and Map using linear data structures;

11. Scatter tables and use of this data structure in an ADT Map implementation.

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

Métodos de ensino e atividades de aprendizagem

TP CLASSES

- Knowledge transfer through exhibition resources.

- Concept consolidation exercises.

- Feedback quizzes available asynchronously.

PL CLASSES

- Application of acquired knowledge to real problems through practical coding work.

OTHERS

- The UC provides slides, its own books, exercise sheets, tutorials and code repositories to support learning, accessible through the Moodle and GitHub platforms.

- Moodle:

- <https://moodle.ips.pt/2223/course/view.php?id=1858>

- GitHub:

- <https://github.com/estsetubal-atad>

- <https://github.com/estsetubal-atad-2022-23-labs>

Software

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

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)
Estudo autónomo	45,00
Frequência das aulas	75,00
Trabalho laboratorial	30,00
Total:	150,00

Obtenção de frequência

The UC assessment is divided into two independent components:

TP - 50% PL - 50%

The resulting grade for each component must be \>= 9.5 points. Consequently, the weighted overall grade must also be \>= 9.5 points.

If you fail only one component, you only have to repeat that component in the next evaluation season.

There are 3 consecutive evaluation epochs:

- Epoch of continuous assessment (during class weeks);

- Época Normal, and;

- Época de Recurso.

PREVIOUS CONSIDERATIONS

Access to each mini-test is conditioned to answering 3 quizzes (one per week and multiple choice), available on Moodle. Each quiz contains 5 questions, can be answered an unlimited number of times and needs 3 questions correct to be considered "answered".

In the PL component there is a weighting criterion for attendance at 10 laboratory classes with a statement (tutorial or evaluated) that will be used on the grade of the evaluated laboratories (AL = attendance/10). This criterion does not apply to students with student-worker status, where AL = 1.

Access to the Test and Exams requires prior registration on the Moodle platform. Students who are not registered within the previously established deadlines may be denied access to the respective test.

The evaluated laboratories are classified into levels \[0, 5\] and then their arithmetic mean is calculated, extrapolated to \[0, 20\] values.

Projects must be submitted on the Moodle platform within the established deadlines; only then are they considered "answered".

At the time of continuous assessment there are the following assessment elements:

TP 3 Mini-Tests + 1 Test

PL 4 Laboratories (graded) + 1 Project

In Época Normal and Recurso epochs there are the following evaluation elements:

TP 1 Exam

PL 1 Project

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

The evaluation components and elements are represented by the following acronyms:

TP | Theoretical-Practical Component

PL | Practical-laboratory Component

MT | Mini-Test

T | Test

L | Laboratory (graded)

AL | Attendance criterion for laboratories

P | Project (Continouos and Época Normal)

EN | Época Normal exam

ER | Época de Recurso exam

PR | Época de Recurso Project

PREVIOUS CONSIDERATIONS

The final classification, in any assessment period, is calculated by:

`FINAL = 50% * TP + 50% * PL`

Calculated grades for both TP and PL components must be `>= 9,5` values.

All grades for individual assessment elements will be rounded to one decimal place, and the final grade will be rounded to the nearest unit.

It is considered "Approved" the student who has `FINAL >= 10` .

------------------------------------------------------------------------

All Projects require a presentation and subsequent oral discussion, which may result in the alteration of the initial grade. Individual participation will also be evaluated through commits made through the GitHub Classroom.

------------------------------------------------------------------------

The assessed laboratories are "optional" in nature, but from the moment the student undergoes the assessment, it is automatically considered that he has opted for continuous assessment in the PL component, resulting in the calculation of the respective grade for that component.

CONTINUOUS EVALUATION SEASON

`TP = ([20 + 15 + 15]% * MT) + (50% * T)` `PL = (20% * L * AL) + (80% * P)`

In the case of not submitting to the evaluated laboratories (L), then: `PL = 100% * P` .

If the student has not attended all 4 evaluated laboratories, the remaining ones will be marked with 0 (zero) for the purposes of calculating L.

Minimum grades:

`MT >= 0` (does not have) `T >= 7,5` values `P >= 9` values `L >= 0` (does not have)

ÉPOCA NORMAL

`TP = 100% * EN` `PL = 100% * P`

Minimum grades:

`EN >= 9,5` values `PL >= 9,5` values

ÉPOCA DE RECURSO

`TP = 100% * ER` `PL = 100% * PR`

Minimum grades:

`ER >= 9,5` values `PR >= 9,5` values

Melhoria de classificação

Grade improvement is only possible at the time of appeal and upon valid enrollment in the Academic Division.

- The TP component can only be improved through examination.

- The PL component can only be improved through a project, prepared individually.

Observações

PLAGIARISM

All projects are submitted to plagiarism check (copies) through the crossing of all submitted projects.

Any situation of plagiarism detected will lead to the cancellation of the projects involved (source/destination does not matter) and communication to the Board for sanctioning follow-up.

ORAL DISCUSSIONS

In any assessment, an oral discussion may be requested to validate skills.

MOODLE

Access to the Moodle platform is only allowed to registered students, through a password provided by the UC professors.

OMISSIONS

Omissions will be decided by the head of the curricular unit.

Recomendar Página Voltar ao Topo