Tarefa 6: AVL

Maio 29, 2010

Dando continuidade às tarefas de MC202, vou comentar sobre o laboratório 6, que consistia em implementar uma árvore AVL.

A árvore AVL é uma árvore binária balanceada de busca. Isso garante que a altura da árvore fica em torno de log n, onde n é o número de elementos na árvore. Tal propriedade é que possibilita busca, insersão e remocão em tempo log n. Porém, para mantear a árvore balanceada são necessárias operações chamadas de rotação (esquerda ou direita), o que torna a implementação de tal estrutura relativamente complexa.

Considerando que o laboratório pudesse ser complicado demais para se fazer em duas semanas, decidi fornecer um conjunto de cabeçalhos das funções, mais a estrutura da árvore para guiar os alunos na implementação. Isso ainda serve para evitar que os alunos enviassem código pronto copiado da internet, uma vez que dificilmente haverá um código que utiliza a mestra estrutura que eu defini.

Além do mais, optei por cobrar apenas a insersão na árvore, ficando os alunos incumbidos de implementar as rotações. A deleção me pareceu complicada demais a primeira vista e preferi não exigir.

O resultado foi melhor do que eu esperava. O número de submissões que vinha decrescendo a cada laboratório, voltou a atingir 40 (lembrando que para a tarefa Python, esse número fora 27). A minha impressão é de que uma boa parte da dificuldade dos alunos menos experientes é definir as estruturas e funções que servirão de base para a implementação. Ao fornecer a estrutura básica, deixei a eles apenas o trabalho de aplicar os algoritmos da teoria.

O único porém é que uma das minhas funções consistia em, dado um nó i, calcular a altura da subárvore a partir dele. Como havia um campo altura na estrutura do nó, minha ideia era, sempre que houvesse algum tipo de rotação envolvendo i, atualizar sua altura com o máximo da altura do filho esquerdo e do filho direito mais um. Só que essa função deveria ser O(1), uma vez que já temos calculado os valores das alturas do filho esquerdo e direito (hipótese). O problema é que a maior parte dos alunos calculou tal altura recursivamente, chamando a função novamente tanto para o filho esquerdo quanto para o direito, e isso torna a complexidade O(n), o que inutiliza a eficiência da inserção, que era O(log n).

Apesar de tudo, fiquei satisfeito com o resultado e sinto que desta forma os alunos focam mais em entender e aplicar a teoria do que desenvolvimento de sofware. Entretanto essa última habilidade é igualmente importante e deve ser trabalhada. No próximo laboratório, optei por um esquema parecido com o da AVL, mas pretendo deixar a implementação do último trabalho, o qual ainda não defini.

Anúncios

Tarefa 5: DNA

Maio 21, 2010

Nesse extenso intervalo sem postar, especifiquei três laboratórios: python (listas generalizadas), do qual falei no post anterior; dna (árvores binárias), que comentarei nesse post; e avl, a tarefa que está sendo feita atualmente.

A tarefa basicamente pede para avaliar uma expressão através de árvores binárias. Não é difícil encontrar implementações que envolvam avaliações de expressões do tipo:

E para não acontecer de o pessoal pegar código pronto, optei por modificar ligeiramente a especificação. Ao invés de avaliar expressões envolvendo números, o laboratório consistia em avaliar conjuntos. Ao invés de números a expressão consistia de variáveis representando um conjunto de características e no lugar dos operadores de adição, subtração, etc, inclui os operadores de união, interseção e diferença.

A partir daí, deixei os alunos implementarem do jeito que quisessem. Porém, alguns truques facilitam a tarefa:

1) As características eram dadas como strings. Porém, podemos guardar as strings em um dicionário (vetor de strings) e trabalhar só com o índice das strings nesse dicionário (int).

2) Quando os elementos do conjunto estão ordenados, é mais simples (e eficiente) implementar as operações sobre conjuntos. A ideia é parecida com a do merge sort: mantemos ponteiros para cada um dos conjuntos A e B. No começo cada qual aponta para o primeiro elemento do seu respectivo conjunto. Seja o valor do elemento apontado pelo ponteiro do conjunto A e o equivalente para o conjunto B. Na união, se , incluímos na união e andamos com o ponteiro de A. Se fazemos o mesmo com o ponteiro de B, se , incluímos qualquer um dos dois, mas apenas um, pois em conjuntos não consideramos elementos repetidos, e então andamos com ambos os ponteiros. Entendida a ideia, é simples derivar o algoritmo para a operação de interseção e diferença.

Para padronizar a resposta e comparar com minha saída no SuSy, exigi que as características do conjunto final estivessem ordenadas. Porém os alunos não tinham visto ordenação ainda, então passei um código que supostamente iria ordenar um vetor de strings:

qsort(saida, n, sizeof(char*MAXLEN), cmp);

Para quem não sabe, o qsort é uma função que implementa o quicksort e está disponível na biblioteca padrão do C. A função exige que você passe uma função de comparação por parâmetro, que compara duas strings. Porém, se o vetor de strings foi alocado estaticamente (minha sugestão inicial), a função não funciona. Uma alternativa é declarar o vetor como um vetor de ponteiros de char e alocar cada string dinamicamente (porém com tamanho fixo MAXLEN). Aí sim funciona. Outra alternativa, a que acabei sugerindo após descobrir o erro, é ordenar apenas os índices do vetor. Para isso nós orderamos um vetor auxiliar (vetor de permutação), indicando que a posição do i-ésimo elemento é . Inicialmente .

A função de comparação recebe dois inteiros i e j, mas na verdade compara as respectivas linhas da matriz (com strcmp). A vantagem desse método é que as strings continuam no mesmo lugar. O que muda são apenas os índices.


Tarefa 4: Python

Maio 21, 2010

O último post foi a mais de um mês atrás, pois estive muito ocupado. Tive prova e entrega de trabalho de PLI e ainda, com o fim da OBI, comecei a preparar aulas para o pessoal da maratona. Agora com o horário mais folgado, decidi escrever sobre o laboratório 04 de MC202.

O tema central da tarefa 4 de MC202 eram listas generalizadas. Sinceramente não me lembro de ter visto essa estrutura de dados em MC202 (talvez tenha esquecido, afinal cursei-a em 2005). Mas para quem conhece árvores essa estrutura é relativamente fácil de aprender.

Eu estava pensando em algum contexto em que fosse necessário o uso de tais listas, quando me deparei com a estrutura “List” da linguagem de programação python. Ela é justamente uma implementação de listas generalizadas. Propus então que o pessoal implementasse um interpretador para comandos envolvendo as listas generalizadas.

Para simplificar as coisas, restringi os tipos dentro da lista a inteiros. Além do mais os comandos possíveis eram apenas o de impressão e o de atribuição. Mesmo com essas restrições, o exercício ficou bem trabalhoso. Dei duas semanas de prazo e mesmo assim a taxa de submissão foi 27/47 (57,44%) e a média geral foi 3.01 :(