Local: LAB 3
Horário: segundas e quartas das 10h às 12h
Início: 7 de agosto de 2019
Avaliações: trabalhos feitos em sala de aula (e possivelmente terminados em casa, a combinar)
- Repositório:
https://github.com/vigusmao/TEP_2019_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?
Brain teaser: o problema dos condenados encapuzados (paridade).
Parâmetros da entrada que podem ser usados na expressão da complexidade para entender melhor a performance de um algoritmo. Ele é sensível a quê?
Algoritmos diferentes, com complexidades diferentes, para um mesmo problema, sem que um domine o outro. É preciso saber, dependendo do caso (entradas típicas, ou parâmetros da entrada obtidos via pré-processamento), qual o melhor caminho a seguir.
Exemplos: o problema do histograma (em que ano havia mais pessoas vivas?); o problema das estradas ligando metrópoles.
Problemas de precisão: raiz quadrada ao quadrado pode não dar seu número.
Performance: evite cálculos caros, quando você pode fazer o simples.
O problema dos números mágicos: liste os números naturais que são ao mesmo tempo quadrados perfeitos e números triangulares (a soma dos k primeiros naturais, para algum k).
Memoização. Memoização podendo exaurir toda a memória. Memoização podendo piorara execução (se mal feita). Memoização com políticas de cache. Memoização com hashing vs memoização via endereçamento direto.
O problema da Conjectura de Collatz.
Usando um AND bitwise ao invés de módulo.
Brain teaser: Dada uma lista de tamanho n-1 sem repetição com elementos inteiros em [1, n], qual o elemento que está faltando? E se forem dois elementos faltando? E se a memória auxiliar disponível for logarítmica em n?
O problema do array ordenado e "rodado". Como encontrar de forma eficiente o menor elemento no array?
Horário: segundas e quartas das 10h às 12h
Início: 7 de agosto de 2019
Avaliações: trabalhos feitos em sala de aula (e possivelmente terminados em casa, a combinar)
https://github.com/vigusmao/TEP_2019_2
Problemas recomendados: hackerrank
Conteúdo das aulas
07/08
Conversa inicial sobre o curso. Google Interview Preparation Tips.
Complexidade assintótica: por que é imporante? por que as constantes são desprezíveis?
Brain teaser: o problema dos condenados encapuzados (paridade).
12/08
Parâmetros da entrada que podem ser usados na expressão da complexidade para entender melhor a performance de um algoritmo. Ele é sensível a quê?
Algoritmos diferentes, com complexidades diferentes, para um mesmo problema, sem que um domine o outro. É preciso saber, dependendo do caso (entradas típicas, ou parâmetros da entrada obtidos via pré-processamento), qual o melhor caminho a seguir.
Exemplos: o problema do histograma (em que ano havia mais pessoas vivas?); o problema das estradas ligando metrópoles.
14/08
Problemas de precisão: raiz quadrada ao quadrado pode não dar seu número.
Performance: evite cálculos caros, quando você pode fazer o simples.
O problema dos números mágicos: liste os números naturais que são ao mesmo tempo quadrados perfeitos e números triangulares (a soma dos k primeiros naturais, para algum k).
19/08
Memoização. Memoização podendo exaurir toda a memória. Memoização podendo piorara execução (se mal feita). Memoização com políticas de cache. Memoização com hashing vs memoização via endereçamento direto.
O problema da Conjectura de Collatz.
Usando um AND bitwise ao invés de módulo.
21/08
Brain teaser: Dada uma lista de tamanho n-1 sem repetição com elementos inteiros em [1, n], qual o elemento que está faltando? E se forem dois elementos faltando? E se a memória auxiliar disponível for logarítmica em n?
O problema do array ordenado e "rodado". Como encontrar de forma eficiente o menor elemento no array?
