Algorithms and Data Structures

General characterization

Prerequisites

Mandatory prerequisite:

- Programação de Microprocessadores

Bibliography

Mark Allen Weiss.
Data Structures and Algorithm Analysis in C (second edition).
Addison-Wesley, 1997.
ISBN 0-201-49840-5 (Hard cover)

On the C Programming Language

Brian Kernighan and Dennis Ritchie
The C Programming Language (second edition).
Prentice-Hall, 1988.
ISBN 0-13-110362-8 (Paperback)

Pedro Guerreiro.
Elementos de Programação com C (3ª edição).
FCA - Editora de Informática, 2005.

Luis Damas.
Linguagem C (12ª edição).
FCA - Editora de Informática, 2005.

Teaching method

There are one lecture and a lab session each week.

In the lectures, all course contents are presented using concrete practical examples. In the laboratory, students design, analyse and implement programs for specific problems by applying the knowledge gained.

Students will be evaluated by practical works and a test.

Evaluation method

Elements of assessment

The evaluation elements are as follows, with the weights in the final grade indicated:

• T1- Test 1 - 25%
• T2- Test 2 - 45%
• PR- Project - 30%
• ER - Appeal exam - 70%

Each of these elements is graded up to 20 points, with the score rounded to two decimal places.

Tests and exams are written, closed-book, and done individually in person. Electronic devices are not allowed.

The project is carried out by groups of two students of the same practical class. There will be discussions on the project.

The project calendar can be found on the course web page and in the "events" of CLIP.

Grade of the theoretical-practical component

The grade for the theoretical-practical component (CompTP) has a weight of 70% of the final grade and can reach a maximum value of 20 points.

The CompTP score is defined in three different ways, depending on the situation:

• CompTP= (0.25*T1+0.45*T2)/0.70    (in case of pure continuous evaluation)
• CompTP= ER                                      (for students not approved in the continuous evaluation)
• CompTP = max((0.25*T1+0.45*T2)/0.70, ER)   (continuous assessment + attempt to improve grade)

Grade of the laboratory component and "frequência"

The grade for the laboratory component (CompLab) has a weight of 30% of the final grade and can reach a maximum value of 20 points.

The CompLab grade is simply defined as the project grade:

• CompLab = PR

To obtain "frequência", it is necessary that CompLab >= 9.5.

Furthermore, in the case of students enrolled in the 1st year, participation in at least 50% of practical classes is required.

Final grade and approval

Students'' final grade is calculated as follows (being rounded to the nearest integer):

• FINAL = 0.7 * CompTP + 0.3 * CompLab

Approval in the course is determined by the following condition:

• APPROVAL = CompTP >= 9.5 e CompLab >= 9.5

Validity of attendance obtained this year

The "frequência" obtained in the current academic year will be valid in the next academic year, at least.

"Frequências" from previous years

The "frequência" obtained in the previous academic year is valid in the current academic year (and this grade is also allowed to be improved by doing the current year''s project). Older "frequências" are not valid.

Fraud

Fraud/plagiarism issues are handled in accordance with the Regulamento de Avaliação de Conhecimentos da FCT NOVA. For example, any type of fraud in any assessment element makes it impossible to pass the course in the current academic year, and there may be other consequences.

In the final project, students can talk with their peers about general aspects of the work. But they cannot share code (even if it''s "a few lines") under any circumstances, orally or in writing. Writing code has to be an internal task for each group. For example, you are not allowed to display code on the screen, dictate code, send files with code, or place them in places accessible to third parties.

In this introductory course, the use of AI tools in the project is discouraged. But if they are occasionally used in the project, the corresponding code snippets must explicitly refer to this. Omitting this information is considered plagiarism and fraud.

During an assessment, a student may not have any electronic devices capable of accessing the internet or with Bluetooth connectivity (e.g., smartphones, smartwatches, smartglasses, tablets, laptops) with them, even if they are turned off. Violation of this rule results in immediate failure of the curricular unit by exclusion and will be reported to the Scientific Committee of the respective program.

Subject matter

1. Modeling programs, using abstract data types
• Method for the analysis and design of a solution
• Definition and implementation of abstract data types in the problem domain
2. Formal specification ans implementation of abstract data types:
• Queue (LIFO)
• Stack (FIFO)
• Sequence
• Set
• Dictionary
3. Introduction to Algorithm Analysis. Study of the fundamental data structures, including the analysis of the algorithmic in the best, worst and expected case:
4. Implementation techniques using:
• Vectors.
• Singly and Doubly Linked Lists.
• Open and Closed-Hash Tables.
• Sorting.

Programs

Programs where the course is taught: