2024
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: Amortised 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.: the Edmonds-Karp algorithm
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.: the Edmonds-Karp algorithm
Complexity theory: The P and NP classes; Problem reduction.
Teaching Methods
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.
In the laboratory classes, students solve programming and theoretical exercises, related to the topics of the lectures.
Assessment
Student work assessment is performed by means of three programming assignments, to be handed in during classes, and of either midterm written tests or a final exam. Grading of the assignments is subject to a direct examination of the student's performance, which may take place during the period for final assessment.
To obtain a passing grade, a student must obtain at least a grade of 7.0, both as the global assignments' grade and as the midterm tests' average grade or exam's grade. The final grade will computed as 70% of the tests' of exam's grade, plus 30% of the global assignments' grade. The last midterm test may take place during the period for final
assessment.
To obtain a passing grade, a student must obtain at least a grade of 7.0, both as the global assignments' grade and as the midterm tests' average grade or exam's grade. The final grade will computed as 70% of the tests' of exam's grade, plus 30% of the global assignments' grade. The last midterm test may take place during the period for final
assessment.
Teaching Staff
Certificações
