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

Ativa?	Yes
Página Web:	https://moodle.ips.pt/2324/course/view.php?id=1976
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	178	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
	Patrícia Alexandra Pires Macedo		3,00
	Bruno Miguel Nunes da Silva		6,00
Practical and Laboratory	Totais	8	16,00
	Miguel Mourão Fialho Bugalho		4,00
	Patrícia Alexandra Pires Macedo		6,00
	Rúben Pereira Lourenço		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. Hash tables concepts and use of this data structure in dictionary implementations, e.g., 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

Métodos de ensino e atividades de aprendizagem

**TP SESSIONS**

- Knowledge transfer through exhibition resources.

- Concept consolidation exercises.

- Feedback quizzes available asynchronously.

**PL SESSIONS**

- 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/2324/course/view.php?id=1976>

- GitHub:

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

- <https://github.com/estsetubal-atad-2023-24-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
Elaboração de projeto	30,00
Total:	150,00

Obtenção de frequência

The assessment of the course unit is divided into two components, evaluated independently (i.e., passing each component can be done in different assessment periods):

Component TP - 50%

Component PL - 50%

The grade obtained in each component must be >= 9.5 marks. Consequently, the weighted overall grade must also be >= 9.5 marks.

If you fail only one component, you only need to retake that component in the next assessment period.

There are 3 consecutive assessment periods:

- Continuous Assessment Period;

- Normal Period, and;

- Appeal/Special Period.

**PRELIMINARY CONSIDERATIONS**

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

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

In the continuous assessment period, the following assessment elements exist:

**TP**

3 Tests

**PL**

1 Project

In the normal, appeal, and special periods, the following assessment elements exist:

**TP**

1 Exam

**PL**

1 Project

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

The components and assessment elements are represented by the following abbreviations:

TP | Theoretical-practical Component

PL | Practical-laboratory Component

Tn | Test (n = 1, 2, 3)

PN | Project Normal Period (continuous assessment and normal period)

EN | Normal Period Exam

PR | Appeal Period Project

ER | Appeal Period Exam

**PRELIMINARY CONSIDERATIONS**

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

FINAL = 50% * TP + 50% * PL

The grades calculated for both TP and PL components must be >= 9.5 marks.

All grades of individual assessment elements will be rounded to the nearest tenth, and the final grade will be rounded to the unit.

A student is considered "Approved" if they have FINAL >= 10.

----

The evaluation of the Project in the Normal Period is subdivided into:

- 2 checkpoints (20%) + submission (70%) + individual quiz (10%)

The evaluation of Projects in the Appeal and Special Periods is subdivided into:

- submission (90%) + individual quiz (10%)

All Projects require a subsequent oral presentation and discussion, resulting in the final and individual grade per student. Individual participation through commits made on GitHub Classroom will also be evaluated.

**CONTINUOUS ASSESSMENT PERIOD**

TP = max (T1 * w1 + T2 * w2 + T3 * w3), with <w1,w2,w3> being the best permutation of (30/30/40%)

PL = 100% * PN

Minimum grades:

Tn >= 0 (not applicable)

TP >= 9.5 marks

PL >= 9.5 marks

**NORMAL PERIOD**

TP = 100% * EN

PL = 100% * PN

Minimum grades:

TP >= 9.5 marks

PL >= 9.5 marks

**APPEAL/SPECIAL PERIOD**

TP = 100% * ER

PL = 100% * PR

Minimum grades:

ER >= 9.5 marks

PR >= 9.5 marks

Melhoria de classificação

It is only possible to improve the grade in the appeal period and with valid registration in the Academic Division.

- The TP component can only be improved through an exam.

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

Observações

**PLAGIARISM**

All projects are subjected to plagiarism (copying) detection through the comparison of all submitted projects.

Any detected plagiarism will result in the nullification of the involved projects (regardless of the source/destination) and communication to the Directorate for further disciplinary action.

**ORAL DISCUSSIONS**

In any assessment, an oral discussion may be requested for competency validation.

**MOODLE**

Access to the Moodle platform is only permitted for enrolled students, using passwords provided by the course instructors.

**OMITTED CASES**

Omitted cases will be decided by the Course Unit Coordinator.

Recomendar Página Voltar ao Topo