Data Structures
Keywords |
Classification |
Keyword |
OFICIAL |
Computer Science |
Instance: 2020/2021 - 2S
![Requerida a integração com o Teams Ícone do Teams](/fcup/pt/imagens/Spacer)
Cycles of Study/Courses
Teaching language
Portuguese
Objectives
It is intended that the student reinforces his programmings skills, gets to know some of the main data structures and associated algorithms and gains basic knowledge on the conception and analysis of algorithms.
Learning outcomes and competences
The main learning goals are:
- Proficiency with the Java language and with the object oriented programming paradigm;
- Knowledge of the main basic data structures: arrays, matrices, linked lists and binary trees;
- Knowledge of the main abstract types of data and their implementations: queues, stacks, sets, dictionaries and priority queues;
- Basic knowledge of algorithmic analsyis and comprehension of the main classes of complexity;
- Enrichment of knowledge about some algorithmic techniques such as recursion, backtracking search and divide-and-conquer;
- Practical experience applied to concrete problems.
Working method
Presencial
Program
- Fundamental Java Concepts:
. Classes, objects, attributes and methods
. Primitive types, Strings, warappers, arrays and and enum types
. Expressions, operators and control flow instructions
. Input/Output and the the Scanner class
. Packages and default libraries of Java
. Principles of software development, style and documentation
- Object Oriented Programming:
. Goals, principles, patterns and inheritance mechanism
. Interfaces and Abstract Data Types (ADTs)
. Using generics and iterators
- Asymptotic Analysis Concepts:
. Basic notions of asymptotic analysis
. Main complexity classes and how to compare them
. Examples of algorithmic analysis
- Algorithm Design Techniques:
. Structures Programming
. Recursion
. Exhaustive search and backtracking
. Divid-and-conquer
- Fundamental Data Structures:
. Arrays and matrices
. Simple linked lists, circular linked lists and doubly linked lists
. Árvores binárias, árvores de pesquisa e heaps
- Abstract Data ypes and their possible Implementations:
. Sequences, stacks, queues and deques
. Associative containers: sets and maps
. Priority queues
Mandatory literature
Goodrich Michael T.;
Data structures and algorithms in Java. ISBN: 0-471-73884-0
Complementary Bibliography
Sedgewick Robert;
Introduction to programming in Java. ISBN: 978-0-321-49805-2
Cormen Thomas H. 070;
Introduction to algorithms. ISBN: 978-0-262-03384-8
Teaching methods and learning activities
Theory classes where the material is explained, including live coding sessions. Practical classes with programming exercises.
Evaluation Type
Distributed evaluation with final exam
Assessment Components
designation |
Weight (%) |
Exame |
70,00 |
Teste |
30,00 |
Total: |
100,00 |
Amount of time allocated to each course unit
designation |
Time (hours) |
Frequência das aulas |
56,00 |
Estudo autónomo |
66,00 |
Trabalho laboratorial |
40,00 |
Total: |
162,00 |
Eligibility for exams
Have filled in at least 50% of the online weekly quizzes.
Calculation formula of final grade
- NP: practical grade, worth 30% of the final grade, obtained with:
2 practical programming tests, in the Mooshak environment (6 points, 30% of final 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 "recurso" 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.
"Recurso" season classification: C = ER*0.7 + NP ≥ 9.5
Examinations or Special Assignments
2 practical programming tests during the semester.
Classification improvement
Contact the professor (you can try to improve just the pratical component, just the theoretical component, or both)