Local: Sala F2-014.
Horário: 2as e 4as, das 8h às 10h.
Início: 11 de agosto de 2014.
-
Repositório do código criado em sala de aula:
https://github.com/vigusmao/ED_2014_2
- Monitores:
- Jullyana Vycas
- Fabiano Martins
- Ementa aproximada:
- Breve nivelamento em linguagem Python;
- Noções de análise de complexidade de algoritmos;
- Listas lineares: alocação sequencial e alocação encadeada;
- Filas e pilhas;
- Hashing;
- Árvores, árvore binária de busca, árvores binárias de busca balanceadas;
- Programação dinâmica e memoização;
- Conjuntos disjuntos;
- Heaps;
- Algoritmos de ordenação.
- Avaliação:
M = (P1 + P2) / 2 ≥ 6.0 --> aprovação direta;
do contrário, MF = (M + PF) / 2 ≥ 5.0 --> aprovação;
MF < 5.0 --> reprovação.
- Provas:
- P1: 15/10
- P2: 03/12
- PF: 10/12
- SEGUNDA CHAMADA (apenas para quem perdeu alguma prova): 17/12
- Primeira lista de exercícios.
- Segunda lista de exercícios.
Primeira conversa sobre o curso: derrotando o código alheio.
(Comparem a ementa deste curso com o e-mail do Google com dicas para se preparar para uma entrevista para trabalhar com eles.)
Probleminha pra quebrar o gelo: dados dois arrays (listas) de inteiros, encontrar sua interseção.
Código (em Python) feito em sala de aula no GitHub.
Python para quem já programa: conversa rápida sobre alguns aspectos da linguagem.
Por que entender de estruturas de dados e complexidade de algoritmos?
Um exemplo: o problema de se determinar o caracter (ou número) que ocorre com maior frequência em um texto (ou lista).
Código (em Python) feito em sala de aula no GitHub.
Lista linear: a estrutura mais simples. Alocação sequencial e encadeada. Operações mais comuns. Localizando o k-ésimo elemento na lista nas duas implementações. Inserindo no começo da lista nas duas implementações.
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.
Inserindo no fim da lista (append).
Como retornar o tamanho de uma lista encadeada em tempo constante (i.e., sem ter que percorrer a lista inteira).
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).
Mais comparações entre alocação sequencial e encadeada: concatenando duas listas, removendo elementos.
Busca de elemento em array ordenado: (1) parando entes de chegar ao fim; (2) busca binária!
Implementação baixo nível de listas encadeadas. Código (em C) feito em sala de aula no GitHub.
O problema da ordenação topológica: dado um grafo direcionado acíclico, encontrar uma sequência de seus vértices de forma que, para toda aresta (v,w) do grafo, v apareça antes de w na sequência. Quatro implementações distintas de um mesmo algoritmo, usando listas lineares de diversas maneiras, partindo de uma ideia inicial de tempo cúbico no número de vértices até chegar ao ótimo em tempo linear.
Análise de complexidade de algoritmos: caso médio, pior caso. Complexidade assintótica. A notação O.
Exemplo: o problema da seleção dos k maiores elementos de uma lista de n elementos.
Algoritmo O(n log n) usando ordenação.
Algoritmo O(n k) implementando buffer de k maiores usando array ordenado.
Algoritmo O(n log k) implementando buffer de k maiores usando heap.
Pilhas e filas em alocação sequencial.
Pilhas e filas em alocação encadeada.
Árvores. Árvores binárias.
Percursos em árvores. Conversão de florestas e árvores m-árias em árvores binárias.
Árvores binárias de busca.
Árvores binárias de busca ótimas para chaves com frequências de acesso distintas.
Entrada: uma lista ordenada k1 < k2 < ... < kn de chaves, e uma lista f1, f2, ... , fn com as frequências relativas de cada chave.
Saída: uma árvore binária de busca ótima T*(1,n) para essas chaves, isto é, uma que minimize a função custo(T) = Somatóriot = 1, ... , n (nível(kt) * ft).
Dividir e conquistar. Formulação recursiva de um algoritmo para resolver esse problema.
O inconveniente de algumas soluções recursivas: o mesmo sub-problema sendo resolvido muitas vezes. Comparação entre fatorial não-recursivo e recursivo (ok!), e comparação entre fibonacci não-recursivo e recursivo (diferença absurda!).
Programação Dinâmica. Memoização. Implementação do fibonacci recursivo usando memoização. :-)
Outro exemplo: o problema do "3n+1". Implementação recursiva sem memoização (terrível) e com memoização (simples e eficiente).
Como resolver o problema da árvore binária de busca ótima para chaves com frequências de acesso distintas usando memoização.
Código (em Python) feito em sala de aula no GitHub.
Programação Dinâmica clássica (bottom-up). O problema da árvore binária de busca ótima para chaves com frequências de acesso distintas via PD clássica.
Código (em Python) feito em sala de aula no GitHub.
Estruturas para Conjuntos Disjuntos (Union/Find).
Não houve aula por conta da JIC.
Não houve aula por conta da JIC.
Resolução da Primeira Lista de Exercícios em sala de aula. Revisão para a P1.
Primeira Prova.
Entrega das provas corrigidas. Resolução da Primeira Prova em sala de aula.
Código (em Python) feito em sala de aula (para a questão 5 da prova) no GitHub.
Árvores AVL.
Introdução a Hashing. Funções de dispersão, resolução de colisões, fator de carga.
Recesso oficial pelo Dia do Funcionário Público.
Análise do tempo médio de acesso a chaves presentes e ausentes em uma tabela hash com encadeamento.
Discussão sobre aplicabilidade de hashing: vantagens e desvantagens.
O problema dos pares complementares.
Código (em Python) feito em sala de aula no GitHub.
Funções hash: algumas técnicas. Mudança de base.
Mapeamento chave-valor versus mero armazenamento de chaves. Chaves externas e chaves como parte do objeto. Quando os objetos são listas e coisas quetais.
Problema dos pares de pontos colineares (em R2).
Problema da soma dos pares de funções.
Código (em Python) feito em sala de aula no GitHub.
Quando não usar hashing: inexistência de ordem, incerteza de que para uma instância específica a distribuição das chaves será tão boa quanto o caso médio; muitas vezes é overkill em relação ao simples endereçamento direto em um array.
Momento filosófico: é fundamental conhecer as estruturas de dados e seus algoritmos; mas é preciso estar atento à possibilidade de não se usar nada pronto, fechar o livro-texto e usar a pura criatividade.
Problema do mercado financeiro: hashing, hashing duplo e solução "fora da caixa".
Problema do "número que falta" (com limitação de memória).
Não houve aula em função do LAWCG2014.
Não houve aula em função do LAWCG2014.
Trello challenge (apenas o enunciado do problema, não a solução): encontre a palavra P de 9 letras, contendo apenas as letras "acdegilmnoprstuw", tal que hash(P) = 956446786872726, onde hash é dada pelo seguinte código:
Int64 hash (String s) {
Int64 h = 7
String letters = "acdegilmnoprstuw"
for(Int32 i = 0; i < s.length; i++) {
h = (h * 37 + letters.indexOf(s[i]))
}
return h
}
Implementação from scratch de uma tabela hash para armazenar objetos do tipo ALUNO, onde a chave é o DRE do aluno. Código (em C) no GitHub.
Algoritmos de ordenação: BubbleSort, MergeSort, QuickSort, perguntas pertinentes sobre a natureza dos elementos e sua distribuição. Como ordenar, por exemplo, as idades de todos os brasileiros? BucketSort.
Implementações in-place versus uso de memória adicional. Piores casos. Casos médios.
Heap. Heap sort.
k-Selection. Quick Select. Mediana das medianas.
Resolução da Segunda Lista. Revisão para a P2.
Segunda Prova.
Entrega das provas corrigidas. Resolução da Segunda Prova em sala de aula. Arguições sobre o trabalho de implementação.
Prova Final.
Correção da PF, discussão da prova e entrega das notas finais.
Prova de Segunda Chamada.
Encerramento do curso.
Horário: 2as e 4as, das 8h às 10h.
Início: 11 de agosto de 2014.
https://github.com/vigusmao/ED_2014_2
- Jullyana Vycas
- Fabiano Martins
- Breve nivelamento em linguagem Python;
- Noções de análise de complexidade de algoritmos;
- Listas lineares: alocação sequencial e alocação encadeada;
- Filas e pilhas;
- Hashing;
- Árvores, árvore binária de busca, árvores binárias de busca balanceadas;
- Programação dinâmica e memoização;
- Conjuntos disjuntos;
- Heaps;
- Algoritmos de ordenação.
M = (P1 + P2) / 2 ≥ 6.0 --> aprovação direta;
do contrário, MF = (M + PF) / 2 ≥ 5.0 --> aprovação;
MF < 5.0 --> reprovação.
- P1: 15/10
- P2: 03/12
- PF: 10/12
- SEGUNDA CHAMADA (apenas para quem perdeu alguma prova): 17/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
11/08
Primeira conversa sobre o curso: derrotando o código alheio.
(Comparem a ementa deste curso com o e-mail do Google com dicas para se preparar para uma entrevista para trabalhar com eles.)
Probleminha pra quebrar o gelo: dados dois arrays (listas) de inteiros, encontrar sua interseção.
Código (em Python) feito em sala de aula no GitHub.
13/08
Python para quem já programa: conversa rápida sobre alguns aspectos da linguagem.
Por que entender de estruturas de dados e complexidade de algoritmos?
Um exemplo: o problema de se determinar o caracter (ou número) que ocorre com maior frequência em um texto (ou lista).
Código (em Python) feito em sala de aula no GitHub.
18/08
Lista linear: a estrutura mais simples. Alocação sequencial e encadeada. Operações mais comuns. Localizando o k-ésimo elemento na lista nas duas implementações. Inserindo no começo da lista nas duas implementações.
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.
20/08
Inserindo no fim da lista (append).
Como retornar o tamanho de uma lista encadeada em tempo constante (i.e., sem ter que percorrer a lista inteira).
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).
25/08
Mais comparações entre alocação sequencial e encadeada: concatenando duas listas, removendo elementos.
Busca de elemento em array ordenado: (1) parando entes de chegar ao fim; (2) busca binária!
Implementação baixo nível de listas encadeadas. Código (em C) feito em sala de aula no GitHub.
27/08
O problema da ordenação topológica: dado um grafo direcionado acíclico, encontrar uma sequência de seus vértices de forma que, para toda aresta (v,w) do grafo, v apareça antes de w na sequência. Quatro implementações distintas de um mesmo algoritmo, usando listas lineares de diversas maneiras, partindo de uma ideia inicial de tempo cúbico no número de vértices até chegar ao ótimo em tempo linear.
01/09
Análise de complexidade de algoritmos: caso médio, pior caso. Complexidade assintótica. A notação O.
Exemplo: o problema da seleção dos k maiores elementos de uma lista de n elementos.
Algoritmo O(n log n) usando ordenação.
Algoritmo O(n k) implementando buffer de k maiores usando array ordenado.
Algoritmo O(n log k) implementando buffer de k maiores usando heap.
03/09
Pilhas e filas em alocação sequencial.
08/09
Pilhas e filas em alocação encadeada.
10/09
Árvores. Árvores binárias.
15/09
Percursos em árvores. Conversão de florestas e árvores m-árias em árvores binárias.
17/09
Árvores binárias de busca.
22/09
Árvores binárias de busca ótimas para chaves com frequências de acesso distintas.
Entrada: uma lista ordenada k1 < k2 < ... < kn de chaves, e uma lista f1, f2, ... , fn com as frequências relativas de cada chave.
Saída: uma árvore binária de busca ótima T*(1,n) para essas chaves, isto é, uma que minimize a função custo(T) = Somatóriot = 1, ... , n (nível(kt) * ft).
Dividir e conquistar. Formulação recursiva de um algoritmo para resolver esse problema.
O inconveniente de algumas soluções recursivas: o mesmo sub-problema sendo resolvido muitas vezes. Comparação entre fatorial não-recursivo e recursivo (ok!), e comparação entre fibonacci não-recursivo e recursivo (diferença absurda!).
24/09
Programação Dinâmica. Memoização. Implementação do fibonacci recursivo usando memoização. :-)
Outro exemplo: o problema do "3n+1". Implementação recursiva sem memoização (terrível) e com memoização (simples e eficiente).
Como resolver o problema da árvore binária de busca ótima para chaves com frequências de acesso distintas usando memoização.
Código (em Python) feito em sala de aula no GitHub.
29/09
Programação Dinâmica clássica (bottom-up). O problema da árvore binária de busca ótima para chaves com frequências de acesso distintas via PD clássica.
Código (em Python) feito em sala de aula no GitHub.
01/10
Estruturas para Conjuntos Disjuntos (Union/Find).
06/10
Não houve aula por conta da JIC.
08/10
Não houve aula por conta da JIC.
13/10
Resolução da Primeira Lista de Exercícios em sala de aula. Revisão para a P1.
15/10
Primeira Prova.
20/10
Entrega das provas corrigidas. Resolução da Primeira Prova em sala de aula.
Código (em Python) feito em sala de aula (para a questão 5 da prova) no GitHub.
Árvores AVL.
22/10
Introdução a Hashing. Funções de dispersão, resolução de colisões, fator de carga.
27/10
Recesso oficial pelo Dia do Funcionário Público.
29/10
Análise do tempo médio de acesso a chaves presentes e ausentes em uma tabela hash com encadeamento.
Discussão sobre aplicabilidade de hashing: vantagens e desvantagens.
O problema dos pares complementares.
Código (em Python) feito em sala de aula no GitHub.
03/11
Funções hash: algumas técnicas. Mudança de base.
Mapeamento chave-valor versus mero armazenamento de chaves. Chaves externas e chaves como parte do objeto. Quando os objetos são listas e coisas quetais.
Problema dos pares de pontos colineares (em R2).
Problema da soma dos pares de funções.
Código (em Python) feito em sala de aula no GitHub.
05/11
Quando não usar hashing: inexistência de ordem, incerteza de que para uma instância específica a distribuição das chaves será tão boa quanto o caso médio; muitas vezes é overkill em relação ao simples endereçamento direto em um array.
Momento filosófico: é fundamental conhecer as estruturas de dados e seus algoritmos; mas é preciso estar atento à possibilidade de não se usar nada pronto, fechar o livro-texto e usar a pura criatividade.
Problema do mercado financeiro: hashing, hashing duplo e solução "fora da caixa".
Problema do "número que falta" (com limitação de memória).
10/11
Não houve aula em função do LAWCG2014.
12/11
Não houve aula em função do LAWCG2014.
17/11
Trello challenge (apenas o enunciado do problema, não a solução): encontre a palavra P de 9 letras, contendo apenas as letras "acdegilmnoprstuw", tal que hash(P) = 956446786872726, onde hash é dada pelo seguinte código:
Int64 hash (String s) {
Int64 h = 7
String letters = "acdegilmnoprstuw"
for(Int32 i = 0; i < s.length; i++) {
h = (h * 37 + letters.indexOf(s[i]))
}
return h
}
Implementação from scratch de uma tabela hash para armazenar objetos do tipo ALUNO, onde a chave é o DRE do aluno. Código (em C) no GitHub.
19/11
Algoritmos de ordenação: BubbleSort, MergeSort, QuickSort, perguntas pertinentes sobre a natureza dos elementos e sua distribuição. Como ordenar, por exemplo, as idades de todos os brasileiros? BucketSort.
Implementações in-place versus uso de memória adicional. Piores casos. Casos médios.
24/11
Heap. Heap sort.
26/11
k-Selection. Quick Select. Mediana das medianas.
01/12
Resolução da Segunda Lista. Revisão para a P2.
03/12
Segunda Prova.
08/12
Entrega das provas corrigidas. Resolução da Segunda Prova em sala de aula. Arguições sobre o trabalho de implementação.
10/12
Prova Final.
Correção da PF, discussão da prova e entrega das notas finais.
17/12
Prova de Segunda Chamada.
Encerramento do curso.
