Local: LAB-1
Horário: terças e quintas das 10h às 12h
Início: 13 de outubro de 2015
- Repositório:
https://github.com/vigusmao/TEP_2015_2
-
Exercício para casa (entrega até as 23:59 do dia 31/12/2015):
implementar em C (sim, Czão puro :-)) uma tabela hash encadeada com a funcionalidade de
excluir o elemento menos recentemente acessado quando for preciso inserir um novo elemento
e a tabela já tiver atingido sua capacidade máxima (definida no momento da criação).
-
Conversas 1-1 para fechamento do curso:
Dia 25/02
10:10 - Alexandre
10:20 - Allan
10:30 - André
10:40 - Carlos
10:50 - Denis
11:00 - Eduardo
11:10 - Fausto
11:20 - Felipe
11:30 - Fellipe
11:40 - Gabriel Gonçalves
11:50 - Gabriel Kozlowaski
12:00 - Gabriel Luís
Dia 01/03
10:00 - Guilherme
10:10 - Herbert
10:20 - Joshua
10:30 - Josiele
10:40 - Julia Anne
10:50 - Leandro
11:00 - Leonardo
11:10 - Leticia
11:20 - Luan
11:30 - Miguel
11:40 - Raul
11:50 - Thales
12:00 - Wagner
Serão na minha sala (E-2007). É fundamental que vocês cheguem no exato minuto marcado. Do contrário, para evitar o "efeito bola de neve", não vamos discutir tudo que é necessário, e a nota DESPENCARÁ (botando uma pressão, claro :-)). Na quinta, começaremos às 10:10 mesmo, porque vou aplicar prova no LAB-3 até as 10h. Qualquer problema com horários, me comuniquem, de preferência já sugerindo um swap com alguém (que esteja ciente e de acordo). Finalmente, me enviem os slides das apresentações de vocês (quem ainda não o fez). Quem não tiver preparado slide, tudo bem, eu não disse que era necessário (e não era), então nesse caso não precisa me enviar nada. :-)
Início da Primeira Parte do curso. Conversa introdutória. O problema de se produzir um histograma dos usuários online ao longo de um período.
Implementando dois algoritmos para o problema do histograma. Medindo tempos e os relacionando com as complexidades assintóticas.
Desenhando um cluster de servidores para um jogo online no modelo estrela: cada cliente se conecta diretamente a um membro do cluster (i.e., um servidor). Como sincronizar os relógios de todos?
Ainda sobre o cluster de servidores para um jogo online:
- Como selecionar o servidor que cada cliente deverá utilizar para enviar e receber dados?
- Como subir novos servidores? - Como tratar rapidamente o problema de servidores defeituosos / down? - Como balancear as cargas? - Como impedir os possíveis "efeitos-gangorra"?
Descomplicando o backtracking: um esquema limpo. Problema de se enumerar todas as permutações caóticas dos n primeiros naturais.
Implementação do problema das permutações caóticas. Testes unitários.
Para casa: dado n, t_min e t_max, gerar todos os subconjuntos de {1, 2, ..., n} com tamanho entre t_min e t_max (inclusive).
Pensando diferentes estratégias de busca exaustiva. Backtracking com podas, e beneficiando-se das simetrias do problema. Algoritmos exponenciais. Algoritmos pseudo-polinomiais.
O problema da balsa.
Implementação do problema da balsa.
Fatorial recursivo (ok) e não-recursivo. Fibonacci recursivo (não-ok!!) e não-recursivo.
Memoização.
Memoização avançada: limitando o tamanho de memos "imprevisíveis".
Quando uma abordagem recursiva pode ser de fato superior à não-recursiva (permitindo memoizar sub-sub-problemas).
O problema da Conjectura de Collatz.
Raciocínio lógico: pensando o problema ao invés de correr para estruturas.
Arrays de bits/booleanos. Paridade.
O problema dos condenados encapuzados.
O problema dos armários.
O problema dos pontos colineares.
Solução para o problema dos pontos colineares.
Tabelas hash encadeadas (aka LinkedHashMap). Exemplo de aplicação: cache LRU.
O problema do prédio e das duas bolas idênticas.
Mais sobre LinkedHashMap. Implementação.
k-selection. Vários algoritmos. Heap. QuickSelect.
Como permutar aleatoriamente com uniformidade? Vários métodos ineficientes.
Knuth shuffle.
Cuckoo hashing.
Números aleatórios e simulação.
Ex.1: O jogo do trio versus dois pares seguidos.
Ex.2: Probabilidade de A ser igual a C dado que A é diferente de B, para A, B e C variáveis aleatórias independentes e identicamente distribuídas.
Bloom filters.
Tópicos em BD relacionais.
Apresentação do aluno Alexandre Ribeiro de Almeida.
Testes de aceitação e integração.
Apresentação dos alunos Denis Takeo Aoki, Eduardo Felipe Gama Ferreira e Raul Gabrich Moreira de Freitas.
Tries. Árvores de prefixo.
Apresentação do aluno Joshua Silveira Kritz.
Design Patterns.
Apresentação dos alunos Gabriel Gonçalves de Castro Marques, Leonardo Alexandre Santos da Silveira Gonçalves e Thales Nathan Caico Matias da Silva.
Continuous Integration / Continuous Delivery.
Apresentação dos alunos Fausto Ferreira Junqueira e Guilherme Serra Oki.
Heaps e Priority Queues.
Apresentação dos alunos Herbert Salazar dos Santos, Leandro Carneiro Leite e Wagner Luiz Lobo Ferreira.
Controle de versão.
Apresentação dos alunos Gabriel Luis Santos Freire, Josiele de Sousa Gonçalves e Julia Anne de Souza Alves.
NoSQL. MongoDB.
Apresentação dos alunos Allan Monteiro David, Felipe Sepulveda de Faria e Miguel Péres de Castro.
Unit tests / TDD / BDD / Mock.
Apresentação dos alunos Carlos Sergio de Paiva Araujo, Fellipe Fratini Studart Sombra e Luan Cerqueira Martins.
Testes A/B.
Apresentação da aluna Letícia Aguiar e Souza.
Horário: terças e quintas das 10h às 12h
Início: 13 de outubro de 2015
https://github.com/vigusmao/TEP_2015_2
Dia 25/02
10:10 - Alexandre
10:20 - Allan
10:30 - André
10:40 - Carlos
10:50 - Denis
11:00 - Eduardo
11:10 - Fausto
11:20 - Felipe
11:30 - Fellipe
11:40 - Gabriel Gonçalves
11:50 - Gabriel Kozlowaski
12:00 - Gabriel Luís
Dia 01/03
10:00 - Guilherme
10:10 - Herbert
10:20 - Joshua
10:30 - Josiele
10:40 - Julia Anne
10:50 - Leandro
11:00 - Leonardo
11:10 - Leticia
11:20 - Luan
11:30 - Miguel
11:40 - Raul
11:50 - Thales
12:00 - Wagner
Serão na minha sala (E-2007). É fundamental que vocês cheguem no exato minuto marcado. Do contrário, para evitar o "efeito bola de neve", não vamos discutir tudo que é necessário, e a nota DESPENCARÁ (botando uma pressão, claro :-)). Na quinta, começaremos às 10:10 mesmo, porque vou aplicar prova no LAB-3 até as 10h. Qualquer problema com horários, me comuniquem, de preferência já sugerindo um swap com alguém (que esteja ciente e de acordo). Finalmente, me enviem os slides das apresentações de vocês (quem ainda não o fez). Quem não tiver preparado slide, tudo bem, eu não disse que era necessário (e não era), então nesse caso não precisa me enviar nada. :-)
Conteúdo das aulas
13/10
Início da Primeira Parte do curso. Conversa introdutória. O problema de se produzir um histograma dos usuários online ao longo de um período.
15/10
Implementando dois algoritmos para o problema do histograma. Medindo tempos e os relacionando com as complexidades assintóticas.
20/10
Desenhando um cluster de servidores para um jogo online no modelo estrela: cada cliente se conecta diretamente a um membro do cluster (i.e., um servidor). Como sincronizar os relógios de todos?
22/10
Ainda sobre o cluster de servidores para um jogo online:
- Como selecionar o servidor que cada cliente deverá utilizar para enviar e receber dados?
- Como subir novos servidores? - Como tratar rapidamente o problema de servidores defeituosos / down? - Como balancear as cargas? - Como impedir os possíveis "efeitos-gangorra"?
27/10
Descomplicando o backtracking: um esquema limpo. Problema de se enumerar todas as permutações caóticas dos n primeiros naturais.
29/10
Implementação do problema das permutações caóticas. Testes unitários.
Para casa: dado n, t_min e t_max, gerar todos os subconjuntos de {1, 2, ..., n} com tamanho entre t_min e t_max (inclusive).
03/11
Pensando diferentes estratégias de busca exaustiva. Backtracking com podas, e beneficiando-se das simetrias do problema. Algoritmos exponenciais. Algoritmos pseudo-polinomiais.
O problema da balsa.
05/11
Implementação do problema da balsa.
17/11
Fatorial recursivo (ok) e não-recursivo. Fibonacci recursivo (não-ok!!) e não-recursivo.
Memoização.
19/11
Memoização avançada: limitando o tamanho de memos "imprevisíveis".
Quando uma abordagem recursiva pode ser de fato superior à não-recursiva (permitindo memoizar sub-sub-problemas).
O problema da Conjectura de Collatz.
26/11
Raciocínio lógico: pensando o problema ao invés de correr para estruturas.
Arrays de bits/booleanos. Paridade.
O problema dos condenados encapuzados.
O problema dos armários.
O problema dos pontos colineares.
01/12
Solução para o problema dos pontos colineares.
Tabelas hash encadeadas (aka LinkedHashMap). Exemplo de aplicação: cache LRU.
03/12
O problema do prédio e das duas bolas idênticas.
Mais sobre LinkedHashMap. Implementação.
08/12
k-selection. Vários algoritmos. Heap. QuickSelect.
10/12
Como permutar aleatoriamente com uniformidade? Vários métodos ineficientes.
Knuth shuffle.
15/12
Cuckoo hashing.
05/01
Números aleatórios e simulação.
Ex.1: O jogo do trio versus dois pares seguidos.
Ex.2: Probabilidade de A ser igual a C dado que A é diferente de B, para A, B e C variáveis aleatórias independentes e identicamente distribuídas.
07/01
Bloom filters.
12/01
Tópicos em BD relacionais.
Apresentação do aluno Alexandre Ribeiro de Almeida.
14/01
Testes de aceitação e integração.
Apresentação dos alunos Denis Takeo Aoki, Eduardo Felipe Gama Ferreira e Raul Gabrich Moreira de Freitas.
19/01
Tries. Árvores de prefixo.
Apresentação do aluno Joshua Silveira Kritz.
21/01
Design Patterns.
Apresentação dos alunos Gabriel Gonçalves de Castro Marques, Leonardo Alexandre Santos da Silveira Gonçalves e Thales Nathan Caico Matias da Silva.
26/01
Continuous Integration / Continuous Delivery.
Apresentação dos alunos Fausto Ferreira Junqueira e Guilherme Serra Oki.
28/01
Heaps e Priority Queues.
Apresentação dos alunos Herbert Salazar dos Santos, Leandro Carneiro Leite e Wagner Luiz Lobo Ferreira.
02/02
Controle de versão.
Apresentação dos alunos Gabriel Luis Santos Freire, Josiele de Sousa Gonçalves e Julia Anne de Souza Alves.
16/02
NoSQL. MongoDB.
Apresentação dos alunos Allan Monteiro David, Felipe Sepulveda de Faria e Miguel Péres de Castro.
18/02
Unit tests / TDD / BDD / Mock.
Apresentação dos alunos Carlos Sergio de Paiva Araujo, Fellipe Fratini Studart Sombra e Luan Cerqueira Martins.
23/02
Testes A/B.
Apresentação da aluna Letícia Aguiar e Souza.
