T6

28 Março 2017, 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.

P5

21 Março 2017, 15:00 • Isabel Gama Nunes

Resolution of exercises 7, 8, 9, 11.

T5

21 Março 2017, 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.

P4

14 Março 2017, 15:00 • Isabel Gama Nunes

Resolution of exercises 1 and 2.

T4

14 Março 2017, 13:00 • Isabel Gama Nunes

Greedy algorithms

Interval scheduling (the greedy algorithm stays ahead).

Scheduling all intervals (a structural argument).

Scheduling to minimize lateness (an exchange argument).