Data Structures

Programming

JAVA language.

(curricular units Introduction to Programming, Programming and Advanced Programming)

In theoretical classes, the most relevant and representative data structures are presented, analyzed and discussed.
In laboratory classes, students operationalize this knowledge, performing exercise sheets that include analysis, implementation, testing and selection of data structures. Periodic laboratory tests allow continuous monitoring of student performance, while seminars promote greater integration of students in the learning process, through the preparation and delivery of presentations on selected topics to their colleagues.

Developing skill related to program curriculum, including:

– Understanding the concept of algorithmic complexity

– Knowing several data sttuctures and complexity profile of supported operations.

– Selecting an appropriate data structure according to the desired usage profile.

– Understanding the behavior of several data structures and the algorithms that are associated to them,

– Developing generic and recursive programming skills

1 – Introduction
1.1 – Complexity analysis
1.2 – Generic programming
1.3 – Collection API
2 –  Fundamental Structures

2.1- Stacks, queues, trees
     2.1.1 – Basics
     2.1.2 – Aplication – Huffman trees
     2.1.3 – Aplication – Expression representation, computation  and infix-postfix conversion
2.2 – Search Trees
     2.2.1 – Basics
     2.2.2 – AVL
     2.2.3 – Red-Black
     2.2.4 – B-Trees
3- Hash Tables
3.1 – Basics
3.2 – Linear and quadratic probing
3.3 – Chained hashes
4- Advanced Structures
4.1 – Heaps
4.2 – Splay Tree
4.3 – Data structures for spacial and multdimensional information.

In lab classes, algorithms and structures studied in theoretical classes will be implemented, applied and tested, using the Java language.

NAO

Goodrich, M. T. ; Tamassia, R., 2011- Data structures and algorithms in Java. 5th ed.. Hoboken, NJ : John Wiley & Sons, cop. 2011. 710 p.. ISBN 978-0-470-39880-7 (1A-1-429 (ISEC) – 16300)
Weiss, M. A., 1992 – Data structures and algorithm analysis. Redwood City, California : Benjamin/Cummings, 1992. 455 p.. ISBN 0-8053-9052-9 (1A-5-26 (ISEC) – 05840)
Cormen, T. H. ; Leiserson, Charles E. ; Rivest, Ronald L., 1997- Introduction to algorithms. Cambridge [etc.] : The MIT Press, 1997 imp. 1028 p.. ISBN 0-262-53091-0 (1A-1-427 (ISEC) – 09849)

Complementar Bibliography:
Weiss, M. A., 2009, Data Structures & Problem Solving Using Java,Pearson; 4th edition
Open data structures in java, 2023 – https://opendatastructures.org/

Provided course material (slides and annotations)