INF1010 3WB – L7: Partição Dinâmica.

Exercícios

1. Considere o conjunto {1,2,3,4,5,6}. Como ficaria a representação por vetor deste conjunto após a operação de criar_particao_dinamica? Como ficaria este vetor após as operações: união(1,3), união(2,3), união(2,5), união(3,4), união(1,6) se: (a) a operação de união for feita sem critério de tamanho, e (b) com critérios de tamanho.
2. Considerando a partição (a) do problema anterior, como ficaria a partição depois de uma busca(5) seguido de uma busca(3) com a estratégia de compressão de caminho?
3. Considere o algoritmo de geração de labirintos numa grade NxN dado abaixo:

     Numere todas as células da grade de 0 a N*N-1;
     Crie todas as paredes isolando todas as células;
     Repita
       Escolha randomicamente uma parede interior;
       Se as duas células adjacentes a esta parede, x e y, estiverem em diferentes partições
             remova a parede e faça uma união(x,y);
     Até que todas as células estejam no na mesma partição.
   

   Explique o seguinte:
   1. O que representa uma partição que quando o algoritmo progride?
   2. Porque o algoritmo para quando todas as células estão numa mesma partição?
   3. Como o algoritmo garante que existe apenas um caminho entre a célula do início e o fim?
   4. Quantas uniões são feitas? Explique sua resposta.
4. Considere que você tenha definido uma estrutura Aluno como mostrada abaixo. Qual é a melhor estrutura de dados para se armazenar uma coleção dessas estruturas Aluno em cada uma das situações a seguir? Explique o motivo de sua escolha para cada um dos itens.
   1. Encontrar rapidamente um aluno dado o seu nome.
   2. Encontrar o aluno com a matrícula mais antiga que ainda está no sistema (isto é, não se sabe a priori qual é essa matrícula).
   3. Considerando que a turma é dividida em grupos de estudo, encontrar o representante do grupo a que um aluno pertence.

   struct Aluno {
   	char*	nome;	/* nome do aluno */
   	int	matricula;	/* matrícula do aluno considerando que o
   			  primeiro aluno matriculado tem matrícula 1,
   			  o segundo, matrícula 2 e assim
   			  sucessivamente */
   	int	idCurso;	/* um identificador do curso escolhido pelo
   			  aluno (1=Engenharia, 2=Economia, ...) */
   }