Atualizada para o semestre 2017-2.

Algoritmos e Programação III

Avaliação | Trabalhos | Atividades Práticas Supervisionadas | Avaliação | Cronograma | Material de Apoio

A disciplina de Algoritmos e Programação III tem como objetivo principal, desenvolver os conhecimentos sobre estruturas de dados não-lineares, algoritmos de ordenação, e a compreensão de suas características para a sua correta aplicação no desenvolvimento de sistemas. Nesta disciplina são estudados os principais algoritmos de ordenação, sua implementação e suas características. São estudadas estruturas de dados com acesso não-linear, como tabelas de espalhamento (Hashtables), árvores, e grafos, e algoritmos que trabalham com estas estruturas.

Entre os conteúdos estudados, encontram-se:

  • Conceitos básicos de algoritmos como recursividade, e comparação de algoritmos baseado na notação Big-O.
  • Compreensão e avaliação de algoritmos de ordenação.
  • Tabelas de Espalhamento abertas e fechadas.
  • Diferentes modelos de tabelas de espalhamento: Cuckoo Hashing, Robin Hood Hashing e Hopscotch Hashing.
  • Conceitos, aplicações e representações de árvores.
  • Árvores Binárias de Pesquisa e modelos auto-balanceáveis (AVL e Red-Black).
  • Modelos de árvores para diferentes aplicações, como heaps, Árvores B, Radix, e KD.
  • Código de Huffman.
  • Conceitos, aplicações e representações de Grafos.
  • Busca, conectividade e topologia em grafos.
  • Árvore Geradora Mínima, e os algoritmos de Prim e Kruskal.
  • Algoritmo para encontrar o menor caminho em um grafo, utilizando o algoritmo de Dijkstra.

Avaliação

Nesta disciplina, o aluno deve demonstrar a capacidade de compreender, alterar e desenvolver aplicações que utilizam estruturas de dados não-lineares.

Para isso, serão realizadas duas provas, dois trabalhos com escopo definido, e um projeto de implementação cujo escopo será proposto pelo aluno.

Linguagens de Programação

Na disciplina serãoapresentados exemplos utilizando a linguagem de programação Java (versão 8).

Para a implementação dos trabalhos, o aluno poderá escolher entre as linguagens C/C++ (C11/C++14), Python (2.7 ou 3.3+), Javascript (utilizando Node.js), Ruby (2.3), Lua (5.3), Objective-C ou Swift.

Ao utilizar qualquer linguagem de programação, nenhuma dependência extra pode ser requerida. Por exemplo, componentes que não sejam instalados a partir do processo de instalação padrão e mínimo dos compiladores ou interpretadores da linguagem. Todos os trabalhos devem executar a partir de um console (linha de comandos), e os trabalhos podem requerer a criação ou utilização de arquivos com formatos texto (normalmente CSV) ou binários.

Assuma, para a avaliação do trabalho, que o computador onde o sistema será executado, contém a instalação mínima necessária para a linguagem escolhida, e que este é um computador stand-alone, ou seja, não está conectado a nenhuma rede.

Trabalhos

Além de duas provas (com questões práticas e teóricas), o aluno deverá implementar os seguintes trabalhos para demonstrar o desenvolvimento das competências trabalhadas na disciplina.

Os trabalhos possuirão uma data de entrega, onde será realizada a apresentação individual dos trabalhos, e, se não entregues até a data marcada, podem ser entregues com atraso, no entanto, contarão com, no máximo, o conceito C. A entrega dos trabalhos deverá incluir a descrição do repositório Git, e do commit que representa a entrega, pelo Blackboard, e uma apresentação individual do trabalho para o professor. Até que o trabalho seja apresentado ao professor, este será considerado como ainda não entregue.

A descrição dos trabalhos será atualizada, até a 4a aula do semestre.

Trabalho 1 - Caça-Palavras

Objetivo

Implementar um algoritmo que crie um tabuleiro de jogo de "Caça Palavras".

Tarefas

Para a obtenção do conceito C, são necessárias as seguintes funcionalidades:

  • Ler a partir de um arquivo uma lista de palavras, uma por linha.
  • Gerar um grid com as palavras carregadas, na horizontal, da esquerda para a direita, ou na vertical, de cima para baixo. Nas posições em que não se encontram letras das palavras, inserir letras aleatórias.
  • Fazer com que existam cruzamentos entre as palavras. Pelo menos 3 cruzamentos simples, onde uma palavra cruza uma outra, e um cruzamento duplo, onde uma palavra cruza duas outas.
  • As palavras não podem estar em linhas ou colunas adjacentes no grid.

Para a obtenção do conceito B, é necessário cumprir todos os requisitos para a obtenção do conceito C, além de, ao menos uma das seguintes características extras e/ou modificações:

  • As palavras podem estar na vertical de cima para baixo, ou de baixo para cima; e na horizontal, da esquerda para a direita, ou da direita para a esquerda..
  • As palavras podem estar da diagonal, de cima para baixo, ou de baixo para cima, da direita para a esquerda.

Para a obtenção do conceito A, e necessário cumprir todos os requisitos para a obtenção do conceito C, todos os requisitos para a obtenção do conceito B, além de pelo menos uma das seguintes modificações:

  • As palavras podem estar na horizontal, vertical, ou diagonal, em qualquer direção.
  • As palavras podem estar em linhas ou colunas adjacentes, desde que seu início e/ou fim, coincidam.

NOTA: Em qualquer situação, as palavras não podem se "sobrescrever" (ex.: macacoelho), ou começar exatamente quando outra termina (ex.: bolachute).

Entrega

O trabalho deve ser entregue até o início da 7a aula, quando será apresentado.

Referências

Trabalho 2 - Exclusão em uma árvore rubro-negra.

Objetivo

Implementar o método de exclusão em uma árvore rubro-negra, utilizando como base uma implementação já existente em uma biblioteca open source.

Tarefas

Você deve criar um fork do repositório Git [https://github.com/rafasgj/datastructures.git], implementar o método de remoção de elementos da árvore Red-Black, e realizar o "pull request". No "pull request", você deverá explicar a implementação do algoritmo.

A partir deste momento, você receberá uma avaliação do seu código, e da sua explicação, e uma indicação se o pull request foi aceito ou não.

O trabalho será considerado com, no mínimo, conceito C no momento em que o pull request for considerado aprovado. Os conceitos B e A dependerão da qualidade do código e da explicação do algoritmo.

Entrega

O trabalho deve ser entregue até o início da 13a aula.

Referências

Projeto de Desenvolvimento

Objetivo

Implementar uma aplicação, prova de conceito, ou parte de uma aplicação, utilizando estruturas de dados não-lineares.

Tarefas

Você deverá propor uma implementação de uma aplicação, prova de conceito, ou parte de uma aplicação, que utilize estruturas de dados não-lineares. Você deverá também prover os dados necessários para a avaliação da implementação, informando a fonte de onde foram obtidos os dados.

A proposta deve ser aprovada pelo professor, até a 16a aula, e após a proposta ser aprovada, a implementação pode ser iniciada.

Entrega

A proposta do trabalho deve ser aprovada até o final da 16a aula.

O trabalho deve ser entregue até o final da 19a aula.

Referências
  • Datapoa: portal de dados da Prefeitura de Porto Alegre.

Atividades Práticas Supervisionadas

As atividades práticas supervisionadas (APS) devem ser entregues até as datas limite. Caso não sejam entregues até a data limite, não serão computadas as horas de atividades atribuídas às APS. Caso a entrega não apresente os requisitos apresentados nos objetivos da APS, esta não serão computadas as horas de atividades atribuídas às APS.

Título Descrição Horas Data Limite
A-01 Apresentação do algoritmo do trabalho de caça-palavras. 3h 7a Sem.
A-02 Implementação da exclusão em uma árvore rubro-negra. 3h 13a Sem.
A-03 Aprovação da proposta do Projeto de Implementação 3h 16a Sem.
A-04 Relatório sobre a implementação do Projeto de Implementação. 3h 19a Sem.

A-01 Apresentação do Algoritmo do trabalho de caça-palavras.

Objetivo

Apresentar o algoritmo criado para o trabalho de caça-palavras, sem o apoio do código desenvolvido.

Entrega

Esta APS deve ser entregue até a 7a semana de aula.

A-02 Implementação da exclusão em uma árvore rubro-negra.

Objetivo

Dado um código de árvore rubro-negra, sem o método de exclusão, adicionar o método de exclusão de elementos.

Entrega

Esta APS deve ser entregue até a 13a semana de aula.

A-03 Aprovação da proposta do Projeto de Implementação.

Objetivo

Obter aprovação para o Projeto de Implementação. A proposta deve incluir o que será desenvolvido, que dados serão utilizados para testar ou desenvolver o projeto, e que estrutura(s) de dados não-linear(es) serão utilizadas no desenvolvimento, e porque estas estruturas foram escolhidas.

Entrega

Esta APS deve ser entregue até a 16a semana de aula.

A-04 Relatório sobre a implementação do Projeto de Implementação.

Objetivo

O aluno deve apresentar um relatório sobre o Projeto de Implementação, que deverá incluir diagramas que expliquem o funcionamento do sistema, e como os algoritmos e estruturas de dados escolhidos foram utilizados para solucionar o problema proposto.

Entrega

Esta APS deve ser entregue até a 19a semana de aula.

Cronograma

Material de Apoio

Além do material desse site, e do material entregue via Blackboard, é sugerido que o aluno consulte estes materiais ao longo do semestre.

Livros

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein
    Introduction to Algorithms. 3rd Edition.
  • Robert Sedgewick e Kevin Wayne
    Algorithms. 4th Edition.
  • Michael T. Goodrich e Roberto Tamassia
    Estruturas de dados e algoritmos em Java. 5.ed.
  • Sandra Puga e Gerson Rissetti
    Lógica de Programação e Estruturas de Dados com aplicações em Java.
  • Barnes e Kölling
    Programação Orientada a Objetos com Java: uma introdução prática utilizando o BlueJ.
  • Maurício Aniche
    Orientação a Objetos e SOLID para Ninjas: Projetando classes flexíveis.
  • Bruno Preiss
    Estruturas de Dados e Algoritmos
  • Sierra e Bates
    Use a Cabeça! Java
  • Deitel e Deitel
    Java: Como Programar
  • Horstmann e Cornell
    Core Java 2
  • Bruce Eckel
    Thinking in Java
  • Anthony Sintes
    Aprenda Programação Orientada a Objetos em 21 dias.
  • James Raumbaugh et al.
    Modelagem e Projeto Orientado a Objetos
  • Loiane Groner
    Estruturas de dados e algoritmos em JavaScript
  • Bjarne Stroustrup
    Princípios e Práticas de Programação em C++
  • Nilo Ney Coutinho Menezes
    Introdução a Programação com Python
  • Victorine Viviane Mizrahi
    Treinamento em Linguagem C
  • Nivio Zivani
    Projeto de algoritmos: com implementações em Java e C++

Apostilas on-line

Documentação oficial Java

Cursos em Vídeo

Cursos on-line