Local: Sala F2-033 (no dia 17/08) e Sala do Futuro 1 (restante do curso)
Horário: sextas das 13h às 17h
Início: 17 de agosto de 2018
Avaliações: trabalhos feitos em sala de aula (e possivelmente terminados em casa, a combinar)
- Repositório:
https://github.com/vigusmao/TEP_2018_2
Problemas recomendados: hackerrank
Conversa inicial sobre o curso. Google Interview Preparation Tips.
Complexidade assintótica: por que é imporante? por que as constantes são desprezíveis?
Complexidade O(sqrt(n))? Exemplo de sqrt-decomposition: o problema do edifício e das duas bolas idênticas.
O problema dos números que estão faltando no array. Código (Python 3) feito em sala de aula no GitHub.
A complexidade de nested loops.
Número harmônico. O problema dos armários. A complexidade do Quick Sort Randomizado.
Algoritmos com complexidades distintas que coexistem como boas opções. Um pode ser mais eficiente do que o outro, dependendo da entrada.
Trabalho 1: O problema do lifespan.
Mais problemas que admitem algoritmos distintos que "competem" entre si. Exemplo: o problema das estradas.
Sorteando números sem reposição. Knuth shuffle (aka Fischer-Yates shuffle).
O "Tuane Shuffle", em que sorteamos k inteiros positivos sem repetição, do intervalo [1, n], para n dado, em tempo e espaço O(k).
Backtracking. O problema das permutações caóticas. Solução em Python. Note que há dois commits. No primeiro, temos a versão de enumeração, que lista todas as permutações; no segundo, temos a versão que encontra apenas uma.
Trabalho 2: Encontre todos os subconjuntos de tamanho k do conjunto {1, 2, 3, ..., n}, para n e k dados.
Solução conjunta do problema dos subconjuntos. Enumeração via bitwise operations.
O problema dos números mágicos. Cuidado com casos que aparentemente te levam a um backtracking, mas que são muito mais fáceis em verdade.
O problema do array "quase ordenado". Recordando listas encadeadas, árvores binárias de busca e heaps.
Problemas do hackersrank:
Ransom Note. Minha solução.
Sherlock and Anagrams. Minha solução.
Trabalho 3: Imprima todos os anagramas de uma palavra dada (qualquer) que:
a) começam por vogal; e
b) não tem três consoantes juntas; e
c) a primeira ocorrência da letra "P", se houver, tem que ocorrer antes da primeira ocorrência da letra "G", se houver; e
d) não tem duas letras iguais consecutivas.
Dividir e conquistar.
Relações de recorrência.
Recursão.
Memoização.
Programação Dinâmica.
O problemas das permutações caóticas via relação de recorrência com memoização.
O problema da mochila via "PD top down", i.e., usando memoização para não resolver subproblemas repetidos.
PS.: Desabilitem a memoização e vejam o que acontece com os tempos!
Trabalho 4: O problema da carga da balsa. Resolva por backtracking ingênuo, depois pense em como se livrar da complexidade exponencial (no número n'de carros que cabem na balsa) usando PD/memoização, chegando a uma complexidade pseudo-polinomial do tipo O(L * n').
Memoização quando não sabemos de antemão a quantidade de subproblemas a memoizar. Políticas de cache.
O problema do 3n+1 (Conjectura de Collatz). Código no GitHub.
A força de um único bit. O problema dos condenados encapuzados.
Trabalho 5: Dada uma lista de palavras válidas, encontrar uma matriz bidimensional de caracteres que possua área máxima e na qual cada linha e coluna corresponda precisamente a uma palavra válida (i.e., um "retângulo mágico").
Tries. Test-driven development (TDD).
Resolução do exercício do retângulo mágico, sem o uso de tries (e sem usar TDD) e com o uso de tries (programadas com TDD). Código no GitHub.
Trabalho 6A: Seja uma moeda com probabilidade p=2/3 de dar cara num cara-ou-coroa. Encontre, computacionalmente (via simulação):
- o número médio de lançamentos da moeda até obter 5 caras;
- o número médio de lançamentos da moeda até obter 2 caras seguidas, e isso por duas vezes independentemente.
O que acontece quando você varia p?
Trabalho 6B: Seja um dado não necessariamente honesto de n faces. Encontre, computacionalmente (via simulação):
- a probabilidade de se obter três resultados iguais em três lançamentos seguidos do dado;
- a probabilidade de se obter dois pares seguidos em quatro lançamentos do dado, i.e., A=B, C=D.
O que acontece quando você varia a distribuição de probabilidades do dado?
Problema: encontrar números que são ao mesmo tempo quadrados perfeitos e triangulares. Como fazer de forma eficiente?
Exercícios envolvendo hashing:
(1) encontrar o par de inteiros para uma soma dada;
(2) encontrar três pontos colineares;
(3) interseção de listas.
BloomFilter.
Trabalho 7: Construa um BloomFilter, estudando seu comportamento para diversos parâmetros. Veja o que acontece (com a probabilidade de falsos positivos) quando você deixa fixo o tamanho do filtro e a quantidade de chaves, mas varia o número de funções hash utilizadas. Veja o que acontece quando você mantém fixa a quantidade de funções hash, mas varia o tamanho do filtro. A seguir, pesquise qual seria a melhor quantidade de funções hash para uma probabilidade de falsos positivos pré-estabelecida. Escreva testes para seu BloomFilter, indicando os números de true/false positives/negatives.
Horário: sextas das 13h às 17h
Início: 17 de agosto de 2018
Avaliações: trabalhos feitos em sala de aula (e possivelmente terminados em casa, a combinar)
https://github.com/vigusmao/TEP_2018_2
Problemas recomendados: hackerrank
Conteúdo das aulas
17/08
Conversa inicial sobre o curso. Google Interview Preparation Tips.
Complexidade assintótica: por que é imporante? por que as constantes são desprezíveis?
Complexidade O(sqrt(n))? Exemplo de sqrt-decomposition: o problema do edifício e das duas bolas idênticas.
O problema dos números que estão faltando no array. Código (Python 3) feito em sala de aula no GitHub.
24/08
A complexidade de nested loops.
Número harmônico. O problema dos armários. A complexidade do Quick Sort Randomizado.
Algoritmos com complexidades distintas que coexistem como boas opções. Um pode ser mais eficiente do que o outro, dependendo da entrada.
Trabalho 1: O problema do lifespan.
14/09
Mais problemas que admitem algoritmos distintos que "competem" entre si. Exemplo: o problema das estradas.
Sorteando números sem reposição. Knuth shuffle (aka Fischer-Yates shuffle).
O "Tuane Shuffle", em que sorteamos k inteiros positivos sem repetição, do intervalo [1, n], para n dado, em tempo e espaço O(k).
Backtracking. O problema das permutações caóticas. Solução em Python. Note que há dois commits. No primeiro, temos a versão de enumeração, que lista todas as permutações; no segundo, temos a versão que encontra apenas uma.
Trabalho 2: Encontre todos os subconjuntos de tamanho k do conjunto {1, 2, 3, ..., n}, para n e k dados.
21/09
Solução conjunta do problema dos subconjuntos. Enumeração via bitwise operations.
O problema dos números mágicos. Cuidado com casos que aparentemente te levam a um backtracking, mas que são muito mais fáceis em verdade.
O problema do array "quase ordenado". Recordando listas encadeadas, árvores binárias de busca e heaps.
Problemas do hackersrank:
Ransom Note. Minha solução.
Sherlock and Anagrams. Minha solução.
Trabalho 3: Imprima todos os anagramas de uma palavra dada (qualquer) que:
a) começam por vogal; e
b) não tem três consoantes juntas; e
c) a primeira ocorrência da letra "P", se houver, tem que ocorrer antes da primeira ocorrência da letra "G", se houver; e
d) não tem duas letras iguais consecutivas.
28/09
Dividir e conquistar.
Relações de recorrência.
Recursão.
Memoização.
Programação Dinâmica.
O problemas das permutações caóticas via relação de recorrência com memoização.
O problema da mochila via "PD top down", i.e., usando memoização para não resolver subproblemas repetidos.
PS.: Desabilitem a memoização e vejam o que acontece com os tempos!
Trabalho 4: O problema da carga da balsa. Resolva por backtracking ingênuo, depois pense em como se livrar da complexidade exponencial (no número n'de carros que cabem na balsa) usando PD/memoização, chegando a uma complexidade pseudo-polinomial do tipo O(L * n').
05/10
Memoização quando não sabemos de antemão a quantidade de subproblemas a memoizar. Políticas de cache.
O problema do 3n+1 (Conjectura de Collatz). Código no GitHub.
A força de um único bit. O problema dos condenados encapuzados.
Trabalho 5: Dada uma lista de palavras válidas, encontrar uma matriz bidimensional de caracteres que possua área máxima e na qual cada linha e coluna corresponda precisamente a uma palavra válida (i.e., um "retângulo mágico").
26/10
Tries. Test-driven development (TDD).
Resolução do exercício do retângulo mágico, sem o uso de tries (e sem usar TDD) e com o uso de tries (programadas com TDD). Código no GitHub.
Trabalho 6A: Seja uma moeda com probabilidade p=2/3 de dar cara num cara-ou-coroa. Encontre, computacionalmente (via simulação):
- o número médio de lançamentos da moeda até obter 5 caras;
- o número médio de lançamentos da moeda até obter 2 caras seguidas, e isso por duas vezes independentemente.
O que acontece quando você varia p?
Trabalho 6B: Seja um dado não necessariamente honesto de n faces. Encontre, computacionalmente (via simulação):
- a probabilidade de se obter três resultados iguais em três lançamentos seguidos do dado;
- a probabilidade de se obter dois pares seguidos em quatro lançamentos do dado, i.e., A=B, C=D.
O que acontece quando você varia a distribuição de probabilidades do dado?
09/11
Problema: encontrar números que são ao mesmo tempo quadrados perfeitos e triangulares. Como fazer de forma eficiente?
Exercícios envolvendo hashing:
(1) encontrar o par de inteiros para uma soma dada;
(2) encontrar três pontos colineares;
(3) interseção de listas.
BloomFilter.
Trabalho 7: Construa um BloomFilter, estudando seu comportamento para diversos parâmetros. Veja o que acontece (com a probabilidade de falsos positivos) quando você deixa fixo o tamanho do filtro e a quantidade de chaves, mas varia o número de funções hash utilizadas. Veja o que acontece quando você mantém fixa a quantidade de funções hash, mas varia o tamanho do filtro. A seguir, pesquise qual seria a melhor quantidade de funções hash para uma probabilidade de falsos positivos pré-estabelecida. Escreva testes para seu BloomFilter, indicando os números de true/false positives/negatives.
