Curso Algoritmos e Estrutura de Dados em Java

Sobre o curso CS-14

Esse curso foi montado ao longo dos 4 anos que ministramos o curso de Estrutura de Dados e Algoritmos em Java nos cursos de verão da USP.

Todos os tipos de aplicações (desktop, web, distribuída ou mobile) guardam dados para processá-los. O desempenho dessas aplicações depende muito da forma que os dados são armazenados. O conhecimento sobre as diversas estruturas de dados é de uso fundamental para o bom desenvolvedor. Esse curso apresenta o funcionamento interno das principais estruturas de dados e os algoritmos para manipulá-las. O foco é mostrar quais são as vantagens e desvantagens de cada estrutura e em que situações usá-las.

O curso também aborda o framework de Collections do Java, onde há implementações semelhantes das diversas estrutura de dados apresentadas. Desta forma, o desenvolvedor apenas precisa ter o discernimento para escolher qual estrutura usar dependendo do tipo de problema que ele está resolvendo. Esse discenimento é obtido através do conhecimento mais profundo dessas estruturas.

Vamos do Vector e ArrayList até o HashSet e HashMap, passando por tópicos como equals e hashCode, comparando a performance dos algoritmos em relação ao consumo de tempo. Todas essas estruturas de dados serão implementadas do zero, de maneira similiar às que existem no java.util. Problemas comuns em que as soluções usam destas estruturas são apresentados e discutidos. Boas práticas de OO, como o uso de interface, generics e encapsulamento, são vistas no decorrer da criação das estruturas.

Veja também a ementa detalhada do curso.

Pré-requisitos

Curso Java e Orientação a Objetos ou: linguagem Java, variáveis primitivas e orientação a objetos, tratamento de erro, conhecimentos fundamentais de Java SE.

40 horas aula

Fale com a gente.

Dúvidas, reservas ou um papo com um instrutor?

Conteúdo detalhado

Prefácio

Introdução

  1. Introdução
  2. Algoritmo e Implementação
  3. Estrutura de Dados
  4. Sobre este texto

Armazenamento Sequencial

  1. Motivação
  2. O problema da listagem de alunos
  3. Listas
  4. Modelagem
  5. Exercícios: Armazenamento

Vetores

  1. Os testes primeiro
  2. Operações em vetores
  3. Adicionar no fim da Lista
  4. O método toString() para o Vetor
  5. Informar o tamanho da Lista
  6. Verificar se um aluno está presente no vetor
  7. Pegar o aluno de uma dada posição do array
  8. Adicionar um aluno em uma determinada posição do array
  9. Remover um aluno de uma dada posição
  10. Alocação Dinâmica
  11. Generalização
  12. API do Java
  13. Exercícios: Vetores
  14. Exercícios opcionais

Listas Ligadas

  1. Solução clássica de Lista Ligada
  2. Célula e Lista Ligada
  3. Definindo a interface
  4. Testes
  5. Operações sobre uma Lista
  6. Adicionando no começo da Lista
  7. Adicionando no fim da Lista
  8. Percorrendo nossa Lista
  9. Adicionando em qualquer posição da Lista
  10. Pegando um elemento da Lista
  11. Removendo do começo da Lista
  12. Removendo do fim da Lista
  13. Removendo de qualquer posição
  14. Verificando se um elemento está na Lista
  15. O tamanho da Lista
  16. Lista Duplamente Ligada
  17. Adicionando no começo da Lista
  18. Adicionando no fim da Lista
  19. Adicionando em qualquer posição da Lista
  20. Removendo do começo da Lista
  21. Removendo do fim da Lista ou de qualquer posição
  22. API
  23. Exercícios: Lista Ligada

Pilhas

  1. Introdução
  2. Solução do problemas das Peças
  3. Operações em pilhas: Inserir uma peça
  4. Operações em pilhas: Remover uma peça
  5. Operações em pilhas: Informar se a pilha está vazia
  6. Generalização
  7. API do Java
  8. Escapando do Labirinto
  9. Exercícios: Pilha

Filas

  1. Introdução
  2. Interface de uso
  3. Operações em Fila
  4. Inserir uma aluno
  5. Remover um aluno
  6. Informar se a Fila está vazia
  7. Generalização
  8. API do Java
  9. Exercícios: Fila

Armazenamento sem repetição com busca rápida

  1. Motivação
  2. O problema do vocabulário
  3. Conjuntos

Tabelas de Espalhamento

  1. Introdução
  2. Tabela de Espalhamento
  3. Função de Espalhamento
  4. Operações necessárias
  5. Adicionar uma palavra
  6. Remover uma palavra
  7. Verificar se uma palavra está ou não no Conjunto
  8. Recuperar todas as palavras do Conjunto
  9. Informar o tamanho do Conjunto de palavras
  10. Exercícios: Tabela de Espalhamento 1
  11. Diminuindo Colisões
  12. Espalhando Melhor
  13. Exercícios: Tabela de Espalhamento 2
  14. Tabela Dinâmica
  15. Exercícios: Tabela de Espalhamento 3
  16. Generalização
  17. equals e hashCode
  18. Parametrizando o Conjunto
  19. API do Java
  20. Exercícios: Tabela de Espalhamento 4

Armazenamento Associativo

  1. Motivação
  2. Mapa
  3. Exercícios: Armazenamento Associativo

Mapas com Lista

  1. Introdução
  2. Operações em mapas
  3. Adicionar uma associação
  4. Recuperar o valor associado a uma dada chave
  5. Remover a associação que contem uma determinada chave
  6. Verificar se uma dada chave está em alguma associação
  7. Informar o tamanho do Mapa
  8. Exercícios: Mapas

Mapas com Espalhamento

  1. Introdução
  2. Operações
  3. Verificando se uma chave existe
  4. Removendo uma associação dado uma chave
  5. Adicionando uma associação dado uma chave
  6. Recuperando o valor associado a uma determinada chave
  7. Performance das operações
  8. Generalização e Parametrização
  9. API do Java


* Os apêndices listados são conteúdos adicionais que não fazem parte do curso regular.