Description

Theory
1

Theory/Practice
1

Laboratory
2

Instructors

Fátima Rodrigues

Contents

P1-Recursion
Backtracking
Advantages and disadvantages

P2-Generic Programming
Generic Classes and Type Parameters

P3-Algorithm Analysis
Big-Oh notation, properties of Big-Oh
Complexity analysis of Java Collections: ArrayList, LinkedList, Stack, Dequeue, Set, Map, Hash Table
Analysis of main search and sorting algorithms

P4-Binary Search trees
Path traversal algorithms: pre-order, in-order, and post-order
Algorithms for insertion, removal, search
Balanced search trees
KD-dimensional trees

P5-Heaps
Heap Sort Algorithm

P6-Graphs
Data structures for graphs: adjacency matrix, list and map, edge list
Transitive closure of a graph: Floyd Warshall?s algorithm
Graph Traversals: Breadth-first, Depth-first
Strong Components of a Digraph - Kosaraju algorithm
Shortest path: Dijkstra and Bellman Ford algorithms
Topological Sort
Graph cycles: Hierholzer and Fleury algorithms
Minimum Spanning Trees: Kruskal and Prim algorithms
Maximum Network Flow, Ford-Fulkerson algorithm

Learning Outcomes

This subject comprises the study of advanced types of data structures and algorithms for manipulating them. The main topics of the course include binary trees, heaps, graphs, primary and secondary memory, search algorithms, and sorting algorithms, always bearing in mind the complexity analysis of data structures and algorithms. Several case studies will be presented so that students can identify the classes and data structures most suitable for their implementation using the object-oriented paradigm and software design patterns. At the same time, it also aims to deepen programming knowledge (using the Java language) through the study of advanced topics such as generic programming. Knowledge of data structures is essential for the implementation, testing, and maintenance of projects for any software system, which is the contribution of this subject to the course.

By the end of this course the student must be able to:
CO1. Analyse problems and select abstract data types and the most appropriate algorithmic strategies.
CO2. Use abstract data types to implement classes and their methods that satisfy the requirements of a problem.
CO3. Analyse algorithms according to their temporal and spatial complexity and efficiency.
CO4. Define and manipulate linear and non-linear data structures as well as implement the main methods for manipulating these structures.
CO5. Design and implement a software project using several linear and non-linear data structures and make the adequate tests.