Algorithms and Data Structures

Code:

L.EIC011

Acronym:

AED

Keywords
Classification	Keyword
OFICIAL	Informatics Engineering and Computing

Instance: 2024/2025 - 1S

Active?	Yes
Web Page:	http://www.dcc.fc.up.pt/~pribeiro/aulas/aed2425/
Responsible unit:	Department of Informatics Engineering
Course/CS Responsible:	Bachelor in Informatics and Computing Engineering

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L.EIC	349	Syllabus	2	-	6	52	162

Teaching language

Suitable for English-speaking students

Objectives

At the end of the course, students should be able to:

1. analyze the temporal and spatial complexity of algorithms;
2. analyze the correctness of simple algorithms;
3. know the main search and sorting algorithms and their complexity;
4. understand the concept of abstract data type and know how to organize programs around this concept;
5. know the fundamental data structures (and associated algorithms and respective complexity) used to efficiently implement common abstract data types in collection libraries;
6. choose appropriate collections, data structures and algorithms to solve practical problems;
7. write programs in C++ that implement and use the fundamental data structures and algorithms.

 

Learning outcomes and competences

At the end of this unit course, students should: model problems following the object-oriented paradigm; solve problems using abstract data types and simple data structures (linear and non linear).

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Student should have basic knowledge of programming and C++.

Program

Basic concepts and techniques: space and time complexity of algorithms; abstract data types; analysis of algorithm correctness.
Arrays searching and sorting algorithms.
Linear data structures and their implementation: lists, stacks, and queues.
Hierarchical data structures and their implementation: binary trees; binary search trees; balanced binary trees. Applications.
Hash tables and related algorithms.
Priority queues and binary heaps.
Basic graph algorithm: types of graphs; representation; depth-first and breadth-first search. Applications: topological sorting; cycles; connectivity.

Mandatory literature

Weiss, Mark Allen; Data structures and algorithm analysis in C++. ISBN: 0-201-36122-1
Sedgewick, Robert; Algorithms in C++. ISBN: 0-201-35088-2
Thomas H. Cormen; Introduction to algorithms. ISBN: 978-0-262-53305-8 ((3rd or 4th edition))

Teaching methods and learning activities

Theoretical classes are for formal exposition of the subjects, with the presentation of examples and their analysis and discussion.

In practical classes exercises are solved, mainly, programming exercises in C ++, that focus on topics addressed in the theoretical classes.

The assessment is carried out throughout the semester, on previously announced dates, where students are continuously evaluated at the theoretical and practical level. During the semester, there are three individual assessment points: 2 practical tests and 1 final written exam.

Software

CLion
Mooshak - A system for automatic evaluation of code
VSCode

keywords

Physical sciences > Computer science > Programming
Physical sciences > Mathematics > Algorithms

Evaluation Type

Distributed evaluation with final exam

Assessment Components

Designation	Weight (%)
Teste	25,00
Trabalho laboratorial	5,00
Exame	70,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Estudo autónomo	55,00
Frequência das aulas	52,00
Trabalho laboratorial	55,00
Total:	162,00

Eligibility for exams

Conditions to obtain eligibility for exams: do not exceed the absence limit (25% of practical classes)  

Calculation formula of final grade

Final mark is computed up from:

- NP: practical grade, worth 30% of the final grade. Obtained with 3 components: 2 practical tests (2.5 points each) and continuous evaluation solving exercises during the semester (1 point). Required P>=1.5 (scale from 0 to 6).

There will be an extra practical test before the exams in which students with less than practical minimum grade can try to reach that mininum grade.

- EN: "normal" exam grade, worth 70% of the final grade, obtained with a written exam with a grade from 0 to 20.

"Normal" season classification: C = EN*0.7 + NP ≥ 9.5

- ER: on the "appeal" season, a single exam will be made, with a grade from 0 to 20, and it is not possible to repeat the practical prigramming tests.

"Appeal" season classification: C = ER*0.7 + NP ≥ 9.5

Special assessment (TE, DA, ...)

The same rules apply for all students.

Classification improvement

On the appeal season only the exam component can be improved (EN).

Students from the previous year can keep the practical tests grade from that year (IPC component), which will be converted to the NP component, which is worth 30% of the final grade.