A ideia dos EPs é que todos atinjam um certo grau de habilidade em programação. Fora isso, há exercícios para que todos tenham um certo domínio da teoria envolvida no projeto dos algoritmos. Desenvolver um bom algoritmo é um processo iterativo que envolve: projeto, análise, implementação, experimentação, mais projeto, mais análise, mais...

Aqui está um certo guia para o estudo de vocês. Na semana que vem teremos a primeira prova.

Union-find

Sugiro a leitura da página Case Study. Union-Find (S&W)

Aqui é esperado que todos tenham uma certa familiaridade com as várias implementações e seus desempenhos: Quick-find, Quick-union, Weighted quick-union e Weighted quick-union with path compression. Atenção, desempenho = consumo de tempo e consumo de espaço (memória).

A família quick-union é aquela que na implementação temos uma floresta de conjuntos disjuntos (disjoint-set forest). O consumo de tempo de find() e union() são proporcionais a altura das árvores na floresta. Vocês devem saber, para cada implementação, qual a maior altura possível de uma árvore e como uma árvore com tal altura pode ser obtida.

Ao analisarmos estruturas como as que implementam a ADT Union-find, muitas vezes estamos interessados no consumo de tempo de uma sequência de operações. Consumo de tempo de uma sequência de operações frequentemente nos remete ao consumo de tempo amortizado (médio) de cada operação.

Não deixem de ver:

Exercises: 7, 8 e 10 (todos tem solução na página)
Creative problems: 12, 13, 14 e 17 (todos tem solução, pelo menos parcial, acho que a demonstração de 14 está nas notas de aula). O problema 17 é de um teorema bem conhecido e consiste na sua comprovação experimental. Ele lembra o EP de percolação e a solução está na página.
Web exercises: vejam pelo menos o 1, 2, 3 e 4.