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.

40horas 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.