(1.5 pontos)
Quantos hipercubos de dimensão n disjuntos estão contidos num hipercubo
de dimensão m, para ?
(Por exemplo, um hipercubo de dimensão 2 contém dois hipercubos
de dimensão 1.)
(1 ponto)
Refaça a questão acima se permitirmos superposição de vértices mas não
de arestas. (Por exemplo, um hipercubo de dimensão 2 contém quatro hipercubos
de dimensão 1.)
(1.5 pontos)
Construa o código de Gray refletido (reflected Gray code) de 4 bits.
(3 pontos)
Mostre que qualquer grafo de Bruijn de n vértices contém
uma árvore binária completa de n-1 vértices.
(3 pontos)
Seja dada uma lista linear ligada, em que cada elemento aponta ao próximo
elemento, com o último apontando para si próprio. (Para cada elemento
i suponha dado sucessor suc(i).)
List ranking é o problema de determinar a distância
de cada elemento da lista ao último.
Escreva um algoritmo paralelo para list ranking usando
a técnica de pointer jumping.
Seu algoritmo é ótimo? por que?