Local: LEP-2
Horário: sextas das 13h às 17h
Início: 04 de agosto de 2017
- Repositório:
https://github.com/vigusmao/TEP_2017_2
Conversa introdutória.
Carta do Google com dicas para entrevistas.
Visualizando por que a notação O(.) faz sentido. Constantes multiplicativas e aditivas que realmente não importam. Código no GitHub.
Trabalho 1: o problema de se encontrar números ao mesmo tempo quadrados e triangulares. Ex.: 36=6*6 e 36=1+2+3+4+5+6+7+8. Escreva um programa para listar os primeiros n inteiros com essa propriedade.
Heaps binárias (revisão).
Esperança de variável aleatória. Complexidade de caso médio. O caso médio do QuickSort (assumindo distribuição uniforme das permutações dos n elementos que se quer ordenar).
O problema da selação dos k maiores (ou menores) elementos de uma lista.
Abordagem 1: ordena tudo e retorne os k primeiros.
Abordagem 2: mantém os k maiores já vistos em uma lista (array) não-ordenado.
Abordagem 3: mantém os k maiores já vistos em uma lista (array) ordenado.
Abordagem 4: mantém os k maiores já vistos em uma lista encadeada ordenada.
Abordagem 5: mantém os k maiores já vistos em uma heap de mínimo (de tamanho k).
Abordagem 6: QuickSelect.
Trabalho 2: implementar o QuickSelect e pelo menos duas das outras abordagens, comparando-as para diversos valores de n e k.
Bitwise operations. O problema de se determinar a menor potência de 2 que é maior ou igual ao número dado.
Novo exemplo de uso eficiente de uma heap: ordenando um array cujos elementos estão originalmente no máximo à distância k da posição que ocuparão no array ordenado.
Introdução às classes P e NP. O Problema do Milênio.
Sorteando k elementos sem repetição, com uniformidade, em tempo O(k). Várias abordagens pouco eficientes. O paradigma do colecionador de coupons. Linearidade da esperança. Knuth shuffle (Fisher-Yates shuffle).
Problema: listar todas as permutações dos n primeiros inteiros positivos.
Discussão geral sobre backtracking. Implementação do problema proposto em Python.
Código feito em sala de aula no GitHub.
Trabalho 3: listar todos os anagramas da palavra PARALELA, onde:
- a primeira letra é uma consoante; e
- as letras R e P não aparecem juntas (em qualquer ordem); e
- a primeira ocorrência de um L fica à direita da primeira ocorrência de um A.
Reportar a quantidade de anagramas listados, no final.
Problemas envolvendo hashing.
Problema 1: Dada uma lista com n inteiros e um inteiro k, encontrar os pares de elementos distintos da lista que somem k.
Problema 2: Dadas duas listas, encontrar sua interseção.
Problema 3: Dada uma lista de inteiros e uma função f nos inteiros, encontrar todas as tuplas de elementos distintos (x, y, z, w) que satisfaçam f(x) + f(y) = f(z) + f(w).
Memoização. Memoização com limitação de memória (políticas de cache).
Trabalho 4: Seja f(x) = x/2, se x é par; e f(x) = 3x+1, se x é ímpar. Seja g(x) o número de vezes que deve-se aplicar a função x, a partir de x, até que o resultado obtido seja 1. Exemplo: g(10) = 6, correspondendo à sequência 10 - 5 - 16 - 8 - 4 - 2 - 1. Entrada do programa: dois inteiros, min_x e max_x. Saída: x e g(x), para x que maximiza a função g, com min_x ≤ x ≤ max_x.
Trabalho 5: Seja Xn,k uma variável aleatória definida como o número de vezes que se deve sortear (com reposição) uma k-upla de elementos distintos de A = {1, 2, ..., n} até que todas as k! permutações de algum subconjunto de A já tenham sido sorteadas. Entrada do programa: um inteiro n e um inteiro k. Saída: uma boa aproximação para a esperança de Xn,k, obtida por simulação.
Discussão sobre uso eficiente de memória. Como armazenar as tuplas sorteadas poupando espaço.
Problema incidental: dada uma tupla de k elementos, como saber sua posição na lista de todas as permutações (daqueles k elementos) ordenadas lexicograficamente?
Problema 1: os condenados encapuzados (o poder da paridade)
Problema 2: prédio, duas bolas idênticas (balanceamento, sqrt-decomposition)
Problema 3: histograma de usuários online (estratégia incremental, diff's)
Problema 4: arquivo de transações (hashing duplo, processando arquivo de trs pra frente)
Trabalho 6: Dada uma lista de palavras válidas e um inteiro k, encontrar (se existir) uma matriz k x k em que cada linha e cada coluna contém uma palavra válida de tamanho k.
Tries.
Código feito em sala de aula no GitHub.
Trabalho 6 (continuação): Pensar em outras implementações para tries (como representar os filhos de um nó). Pensar em como usar uma única trie, ao invés de uma trie para cada tamanho de palavra.
Horário: sextas das 13h às 17h
Início: 04 de agosto de 2017
https://github.com/vigusmao/TEP_2017_2
Conteúdo das aulas
04/08
Conversa introdutória.
Carta do Google com dicas para entrevistas.
Visualizando por que a notação O(.) faz sentido. Constantes multiplicativas e aditivas que realmente não importam. Código no GitHub.
Trabalho 1: o problema de se encontrar números ao mesmo tempo quadrados e triangulares. Ex.: 36=6*6 e 36=1+2+3+4+5+6+7+8. Escreva um programa para listar os primeiros n inteiros com essa propriedade.
11/08
Heaps binárias (revisão).
Esperança de variável aleatória. Complexidade de caso médio. O caso médio do QuickSort (assumindo distribuição uniforme das permutações dos n elementos que se quer ordenar).
O problema da selação dos k maiores (ou menores) elementos de uma lista.
Abordagem 1: ordena tudo e retorne os k primeiros.
Abordagem 2: mantém os k maiores já vistos em uma lista (array) não-ordenado.
Abordagem 3: mantém os k maiores já vistos em uma lista (array) ordenado.
Abordagem 4: mantém os k maiores já vistos em uma lista encadeada ordenada.
Abordagem 5: mantém os k maiores já vistos em uma heap de mínimo (de tamanho k).
Abordagem 6: QuickSelect.
Trabalho 2: implementar o QuickSelect e pelo menos duas das outras abordagens, comparando-as para diversos valores de n e k.
18/08
Bitwise operations. O problema de se determinar a menor potência de 2 que é maior ou igual ao número dado.
Novo exemplo de uso eficiente de uma heap: ordenando um array cujos elementos estão originalmente no máximo à distância k da posição que ocuparão no array ordenado.
Introdução às classes P e NP. O Problema do Milênio.
25/08
Sorteando k elementos sem repetição, com uniformidade, em tempo O(k). Várias abordagens pouco eficientes. O paradigma do colecionador de coupons. Linearidade da esperança. Knuth shuffle (Fisher-Yates shuffle).
Problema: listar todas as permutações dos n primeiros inteiros positivos.
Discussão geral sobre backtracking. Implementação do problema proposto em Python.
Código feito em sala de aula no GitHub.
Trabalho 3: listar todos os anagramas da palavra PARALELA, onde:
- a primeira letra é uma consoante; e
- as letras R e P não aparecem juntas (em qualquer ordem); e
- a primeira ocorrência de um L fica à direita da primeira ocorrência de um A.
Reportar a quantidade de anagramas listados, no final.
01/09
Problemas envolvendo hashing.
Problema 1: Dada uma lista com n inteiros e um inteiro k, encontrar os pares de elementos distintos da lista que somem k.
Problema 2: Dadas duas listas, encontrar sua interseção.
Problema 3: Dada uma lista de inteiros e uma função f nos inteiros, encontrar todas as tuplas de elementos distintos (x, y, z, w) que satisfaçam f(x) + f(y) = f(z) + f(w).
Memoização. Memoização com limitação de memória (políticas de cache).
Trabalho 4: Seja f(x) = x/2, se x é par; e f(x) = 3x+1, se x é ímpar. Seja g(x) o número de vezes que deve-se aplicar a função x, a partir de x, até que o resultado obtido seja 1. Exemplo: g(10) = 6, correspondendo à sequência 10 - 5 - 16 - 8 - 4 - 2 - 1. Entrada do programa: dois inteiros, min_x e max_x. Saída: x e g(x), para x que maximiza a função g, com min_x ≤ x ≤ max_x.
15/09
Trabalho 5: Seja Xn,k uma variável aleatória definida como o número de vezes que se deve sortear (com reposição) uma k-upla de elementos distintos de A = {1, 2, ..., n} até que todas as k! permutações de algum subconjunto de A já tenham sido sorteadas. Entrada do programa: um inteiro n e um inteiro k. Saída: uma boa aproximação para a esperança de Xn,k, obtida por simulação.
Discussão sobre uso eficiente de memória. Como armazenar as tuplas sorteadas poupando espaço.
Problema incidental: dada uma tupla de k elementos, como saber sua posição na lista de todas as permutações (daqueles k elementos) ordenadas lexicograficamente?
29/09
Problema 1: os condenados encapuzados (o poder da paridade)
Problema 2: prédio, duas bolas idênticas (balanceamento, sqrt-decomposition)
Problema 3: histograma de usuários online (estratégia incremental, diff's)
Problema 4: arquivo de transações (hashing duplo, processando arquivo de trs pra frente)
Trabalho 6: Dada uma lista de palavras válidas e um inteiro k, encontrar (se existir) uma matriz k x k em que cada linha e cada coluna contém uma palavra válida de tamanho k.
06/10
Tries.
Código feito em sala de aula no GitHub.
Trabalho 6 (continuação): Pensar em outras implementações para tries (como representar os filhos de um nó). Pensar em como usar uma única trie, ao invés de uma trie para cada tamanho de palavra.
