Teo6

27 Março 2018, 13:00 • Isabel Gama Nunes

Still greedy - Huffman codes.

Dynamic Programming:

Weighted Interval Scheduling: a recursive procedure.

Principles of Dynamic Programming: memoisation or iteration over subproblems.

Segmented Least Squares: multi-way choices.

TP5

20 Março 2018, 15:00 • Isabel Gama Nunes

Resolution of exercises 7, 8, 9.

Teo5

20 Março 2018, 13:00 • Isabel Gama Nunes

Greedy algorithms

Shortest paths in a graph; Dijkstra's algorithm.

The minimum spanning tree problem; Prim's and Kurskal's algorithm.

Clustering.

TP4

13 Março 2018, 15:00 • Isabel Gama Nunes

Resolution of exercise 3.

Teo4

13 Março 2018, 13:00 • Isabel Gama Nunes

Greedy algorithms

Interval scheduling (the greedy algorithm stays ahead).

Scheduling all intervals (a structural bound argument).

Scheduling to minimize lateness (an exchange argument).