Algorithms and Data Structures

Code:

L.EIC011

Acronym:

AED

Keywords
Classification	Keyword
OFICIAL	Informatics Engineering and Computing

Instance: 2021/2022 - 1S

Active?	Yes
Web Page:	https://www.dcc.fc.up.pt/~pribeiro/aulas/aed2122/
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	252	Syllabus	2	-	6	52	162

Teaching language

Portuguese

Objectives

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

1. analyze (and measure experimentally) the temporal and spatial complexity of algorithms;
2. analyze (and test experimentally) the correctness of simple algorithms;
3. know the main array 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 (AVL and splay); B-trees.
Hash tables and related algorithms.
Priority queues and binary heaps.
Basic graph algorithm: types of graphs; representation; depth-first and breadth-first search; topological sorting; cycles; connectivity; shortest path; minimum spanning tree.

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

Complementary Bibliography

Deitel, H. M.; C++ how to program. ISBN: 0-13-185757-6
Stroustrup, Bjarne; The C++ programming language. ISBN: 0-201-88954-4
Koenig, Andrew; Accelerated C++. ISBN: 0-201-70353-X
Cormen, Thomas H.; Introduction to algorithms

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, programming exercises in C ++ are solved, that focus on topics addressed in the theoretical classes. Resolutions are usually in groups of students, and discussion on proposed solutions is encouraged.

The assessment is carried out throughout the semester, on previously announced dates, where students are continuously evaluated at the theoretical and practical level, at individual and group level. During the semester, there are three individual assessment points, including theoretical questions and individual computer exercises. Throughout the semester, two programming projects are also proposed, that are solved in group of students, thus fostering the ability to work in teams. The development of these projects is essentially done out of class, with regular monitoring.

Software

Google Tests: unit testing
Doxygen: Documentation system for C++
CLion: a cross-platform IDE for C++

keywords

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

Evaluation Type

Distributed evaluation without final exam

Assessment Components

Designation	Weight (%)
Teste	60,00
Trabalho laboratorial	40,00
Total:	100,00

Amount of time allocated to each course unit

Designation	Time (hours)
Elaboração de projeto	60,00
Estudo autónomo	40,00
Frequência das aulas	52,00
Trabalho laboratorial	8,00
Total:	160,00

Eligibility for exams

Student may not exceed the limit of absences.

Calculation formula of final grade

Final mark is computed up from:

CIP = practical on computer evaluation, individual programming assignments (average of the  evaluation moments during the semester)

CIT = theory evaluation, multiple-choice questions to be answered on an individual basis

CG = two small projects (GC1 and GC2) to be implemented in group (of 2 or 3 students), of equal weight; these evaluation considers both commitment and attendance of student in group work.

Final mark (F) is given by: F = 30% CIP + 30% CIT + 40% CG


Observations:

1. A minimum mark of 40% is required in every assessment component (CIP, CIT, CG1, CG2)

2. There will be a recovery test for students that did not obtain the minimum required in the component CIP and/or CIT. The grade of this test is limited to 50%.

Examinations or Special Assignments

Special Assignments include two components (EC and PC):

• Exam Component (EC) (60%),  includes:
• a practical programming part using unit tests (PEC)
• theorical part, multiple-choice questions (TEC)

• Practical Work Component (PC) (40%), a small project to be implemented and presented in the day of the exam. Students should contact the professor for the practical work assignment.

Final mark (N) is given by: N = EC*0,6 + PC*0,4.

Students should achieve a minimum success of 40% in every assessment component (PEC, TEC, PC).

Special assessment (TE, DA, ...)

Students registered under any special status:

• group assessment may be performed individually and the student must talk to the lecturer to make all the arrangements and fix a reasonable schedule to be assessed with this regard.
• should attend and perform the individual assessment components, as normally scheduled

Classification improvement

Students may improve their grades in the next course term.