Local: Sala F2-014.
Horário: 2as e 4as, das 8h às 10h.
Início: 12 de setembro de 2016.
-
Repositório do código criado em sala de aula:
https://github.com/vigusmao/ED_2016_2
- Ementa aproximada:
- Noções de análise de complexidade de algoritmos;
- Listas lineares: alocação sequencial e alocação encadeada;
- Filas e pilhas;
- Árvores, árvore binária de busca, árvores binárias de busca balanceadas;
- Hashing;
- Programação dinâmica e memoização;
- Heaps;
- Algoritmos de ordenação.
- Avaliação:
M = (P1 + P2 + P3 - min(P1, P2, P3)) / 2 (sem segunda chamada)
M >= 5.0 --> aprovação; M < 5.0 --> reprovação
-
Provas:
- P1: 07/11
- P2: 05/12
- PF: 12/12
- Primeira lista de exercícios aqui.
Primeira conversa sobre o curso: derrotando o código alheio.
Por que entender de estruturas de dados e complexidade de algoritmos?
Probleminha pra quebrar o gelo: dados dois arrays (listas) de inteiros, encontrar sua interseção.
Lista linear: a estrutura mais simples. Alocação sequencial (arrays) e encadeada (listas encadeadas).
Operações mais comuns (nas duas implementações): ler o k-ésimo elemento da lista; inserir no começo da lista; inserir no fim da lista (append); concatenar listas; remover um elemento.
Políticas de crescimento de listas em alocação sequencial (arrays): crescimento em P.A. (tempo total quadrático) e em P.G. (tempo total linear).
Busca de elemento em array ordenado: (1) parando entes de chegar ao fim; (2) busca binária!
Implementação do problema da interseção.
Código (em Python) feito em sala de aula no GitHub.
Comparando a ementa do curso com o e-mail do Google com dicas para se preparar para uma entrevista para trabalhar com eles.
Análise de algoritmos: discussão sobre o número de "passos" de um programa, i.e., a quantidade de operações básicas que são executadas, ou, equivalentemente, de blocos com número constante de operações de tempo constante que são executados. Complexidade assintótica. A notação O.
Implementação de listas encadeadas "from scratch" em C. Código feito em sala de aula no GitHub.
Continuação de listas encadeadas. Remoção, concatenação, etc.
Filas e pilhas. Implementação usando arrays e usando listas encadeadas.
Árvores. Árvores binárias.
Busca em árvores. Percurso em pré-ordem, pós-ordem, ordem simétrica, largura. Exemplos de aplicação.
Discussão sobre programas recursivos versus não-recursivos: nenhum problema em usar recursão, desde que se evite resolver o mesmo subproblema inúmeras vezes. Exemplo: Fibonacci.
Código feito em sala de aula no GitHub.
Árvore binária de busca.
Frequências de acesso distintas. Árvore binária de busca ótima.
Implementação recursiva (com memoização) do algoritmo da árvore binária de busca ótima.
Código feito em sala de aula no GitHub.
Árvores auto-balanceáveis. Árvore AVL.
Revisão para a P1. Correção da primeira lista.
P1.
Correção da P1 em sala de aula.
Hashing. Tratamento de colisões via encadeamento externo.
Complexidade esperada para operações de dicionário.
Outras formas de tratar colisões.
Cuckoo hashing.
Heaps.
Algoritmos de ordenação. Tempo. Espaço. Estabilidade.
Selection Sort. Insertion Sort. Bubble Sort.
Merge Sort. Heap Sort. Quick Sort.
A complexidade de caso médio do Quick Sort.
Ordenando em tempo O(log n). Count Sort.
P2.
Horário: 2as e 4as, das 8h às 10h.
Início: 12 de setembro de 2016.
https://github.com/vigusmao/ED_2016_2
- Noções de análise de complexidade de algoritmos;
- Listas lineares: alocação sequencial e alocação encadeada;
- Filas e pilhas;
- Árvores, árvore binária de busca, árvores binárias de busca balanceadas;
- Hashing;
- Programação dinâmica e memoização;
- Heaps;
- Algoritmos de ordenação.
M = (P1 + P2 + P3 - min(P1, P2, P3)) / 2 (sem segunda chamada)
M >= 5.0 --> aprovação; M < 5.0 --> reprovação
- P1: 07/11
- P2: 05/12
- PF: 12/12
Bibliografia sugerida
| Estruturas de Dados e seus Algoritmos | Introduction to Algorithms | ||
| (J. L. Szwarcfiter, L. Markenzon) | (Cormen, Leiserson, Rivest & Stein) | ||
 |  |
Conteúdo das aulas
12/09
Primeira conversa sobre o curso: derrotando o código alheio.
Por que entender de estruturas de dados e complexidade de algoritmos?
Probleminha pra quebrar o gelo: dados dois arrays (listas) de inteiros, encontrar sua interseção.
14/09
Lista linear: a estrutura mais simples. Alocação sequencial (arrays) e encadeada (listas encadeadas).
Operações mais comuns (nas duas implementações): ler o k-ésimo elemento da lista; inserir no começo da lista; inserir no fim da lista (append); concatenar listas; remover um elemento.
Políticas de crescimento de listas em alocação sequencial (arrays): crescimento em P.A. (tempo total quadrático) e em P.G. (tempo total linear).
19/09
Busca de elemento em array ordenado: (1) parando entes de chegar ao fim; (2) busca binária!
Implementação do problema da interseção.
Código (em Python) feito em sala de aula no GitHub.
21/09
Comparando a ementa do curso com o e-mail do Google com dicas para se preparar para uma entrevista para trabalhar com eles.
Análise de algoritmos: discussão sobre o número de "passos" de um programa, i.e., a quantidade de operações básicas que são executadas, ou, equivalentemente, de blocos com número constante de operações de tempo constante que são executados. Complexidade assintótica. A notação O.
26/09
Implementação de listas encadeadas "from scratch" em C. Código feito em sala de aula no GitHub.
28/09
Continuação de listas encadeadas. Remoção, concatenação, etc.
03/10
Filas e pilhas. Implementação usando arrays e usando listas encadeadas.
05/10
Árvores. Árvores binárias.
Busca em árvores. Percurso em pré-ordem, pós-ordem, ordem simétrica, largura. Exemplos de aplicação.
10/10
Discussão sobre programas recursivos versus não-recursivos: nenhum problema em usar recursão, desde que se evite resolver o mesmo subproblema inúmeras vezes. Exemplo: Fibonacci.
Código feito em sala de aula no GitHub.
Árvore binária de busca.
24/10
Frequências de acesso distintas. Árvore binária de busca ótima.
26/10
Implementação recursiva (com memoização) do algoritmo da árvore binária de busca ótima.
Código feito em sala de aula no GitHub.
Árvores auto-balanceáveis. Árvore AVL.
31/10
Revisão para a P1. Correção da primeira lista.
07/11
P1.
09/11
Correção da P1 em sala de aula.
16/11
Hashing. Tratamento de colisões via encadeamento externo.
21/11
Complexidade esperada para operações de dicionário.
Outras formas de tratar colisões.
Cuckoo hashing.
23/11
Heaps.
28/11
Algoritmos de ordenação. Tempo. Espaço. Estabilidade.
Selection Sort. Insertion Sort. Bubble Sort.
Merge Sort. Heap Sort. Quick Sort.
30/11
A complexidade de caso médio do Quick Sort.
Ordenando em tempo O(log n). Count Sort.
05/12
P2.
