2023
Data Structures and Algorithms II
Name: Data Structures and Algorithms II
Code: INF13196L
6 ECTS
Duration: 15 weeks/156 hours
Scientific Area:
Informatics
Teaching languages: Portuguese
Languages of tutoring support: Portuguese, English
Regime de Frequência: Presencial
Sustainable Development Goals
Learning Goals
The students should:
- broaden their knowledge on temporal and space complexity analysis of algorithms;
- become familiar with some advanced algorithm construction techniques;
- be able to design, analyse and implement algorithms base on those techniques;
- understand graphs, their algorithms and applications;
- acquire a working knowledge on how to choose the appropriate data structures and algorithms for a given problem;
- understand the difference between tractable and intractable problems;
- know how to show that a problem is intractable;
- be able to design and describe how an algorithm works.
- broaden their knowledge on temporal and space complexity analysis of algorithms;
- become familiar with some advanced algorithm construction techniques;
- be able to design, analyse and implement algorithms base on those techniques;
- understand graphs, their algorithms and applications;
- acquire a working knowledge on how to choose the appropriate data structures and algorithms for a given problem;
- understand the difference between tractable and intractable problems;
- know how to show that a problem is intractable;
- be able to design and describe how an algorithm works.
Contents
Time and space complexity analysis: Amortized complexity analysis.
Algorithm design: Divide and conquer algorithms; Greedy algorithms; Dynamic programming.
Graphs: Directed and undirected graphs, weighted graphs; Adjacency-list and adjacency-matrix representations; Breadth-first and depth-first search; Topological sort; Connected and strongly connected components; Minimum spanning tree: Prim and Kruskal algorithms; The union-find abstract data type; Shortest paths: Bellman-Ford, Dijkstra and DAG's algorithms; All-pairs shortest paths: the Floyd-Warshall algorithm; Network flows.
Complexity theory: The P and NP classes; Problem reduction.
Algorithm design: Divide and conquer algorithms; Greedy algorithms; Dynamic programming.
Graphs: Directed and undirected graphs, weighted graphs; Adjacency-list and adjacency-matrix representations; Breadth-first and depth-first search; Topological sort; Connected and strongly connected components; Minimum spanning tree: Prim and Kruskal algorithms; The union-find abstract data type; Shortest paths: Bellman-Ford, Dijkstra and DAG's algorithms; All-pairs shortest paths: the Floyd-Warshall algorithm; Network flows.
Complexity theory: The P and NP classes; Problem reduction.
Teaching Methods
The subject matter is introduced in lectures, where solutions for different classes of problems are also studied and analysed.
In the laboratory classes, students solve programming and theoretical exercises, related to the topics of the lectures.
Student work assessment is performed by means of three programming assignments, to be handed in exclusively during classes, and of either midterm written tests or a final exam. The final grade is computed based on the grades of the programming assignments (30%) and of the written tests or exam (70%).
In the laboratory classes, students solve programming and theoretical exercises, related to the topics of the lectures.
Student work assessment is performed by means of three programming assignments, to be handed in exclusively during classes, and of either midterm written tests or a final exam. The final grade is computed based on the grades of the programming assignments (30%) and of the written tests or exam (70%).
Teaching Staff
