Dia 10/9/08: Primeiro encontro. Presentes 18 alunos.

Apresentação. Objetivos e funcionamento do treinamento. 

Relação dos problemas de programação com as disciplinas do curso: Algoritmos e Programação, Estrutura de Dados, Projeto e Análise de Algoritmos, dentre outras (matemática discreta, geometria analítica, inteligência artificial).

Observações sobre as linguagens de programação: C, C++ e Standard Template Library (STL), Java e Pascal.

Apresentação do site da Maratona de Programação e do site do ICPC da qual a maratona faz parte.

Apresentação do juiz online SPOJ-BR (problemas em português) e SPOJ (problemas em inglês).

Exemplo de problema de dificuldade moderada: Island Hopping (ISLHOP) .

Problema para Casa (aquecimento): PLACAR

Dia 17/9/08: Presentes: 20

Resolvemos o problema PLACAR em C e C++ . 

Falamos sobre strings em C e as funções strcpy( ) e strcmp( ) da biblioteca string.h.

Vimos que ao declarar um vetor de caracteres (char nome[21] ), a leitura com scanf( ) é feita sem

o operador &. O correto é "scanf("%s", nome)". Errado é: scanf("%s", &nome) <-- errado.

Introduzimos entrada e saída em C++ com cin e cout e os operadores << e >> e a classe string e seus operadores de cópia/atribuição (=) e comparação ( < e > ).

Problemas sugeridos do site SPOJ Brasil: Recuperação e Saldo de Gols . 

Dia 24/9/08: Atividade transferida para a palestra do Prof. Luciano Senger.

              Problema proposto para casa: 818. Aeroporto 

Dia 1/10/08: Presentes: 8 alunos. Busca e Ordenação. Aula expositiva sobre busca em vetores, complexidade de tempo dos algoritmos, introdução informal à notação assintótica "big oh" ou "ó grande". Diferença entre problemas com solução de tempo linear e quadráticas, isto é, O(n) contra O(n^2). Relação entre notação assintótica e tempo real de execução. Algoritmos de tempo O(n log n) baseados em ordenação. Método Ordena e Varre. Eliminação de duplicatas de um vetor em O(n log n).  Vejam os slides da aula aqui.

Problema  11493 - The Club Ballroom  ou O Salão do Clube (Primeira Fase, Curitiba/2008)

 

Dia 8/10/08: O professor resolveu o problema do Salão do Clube. Discutiu a questão da ordenação. A solução inicial usou a funcão qsort() da biblioteca da linguagem C. A solução tem tempo esperado de O(n log n).

Devido às restrições do problema, argumentamos que é possível resolver o problema de tempo O(n) (linear).

Para isso, discutimos o método de ordenação por contagem. Primeiro, estudamos o problema de ordenar um vetor de bits. Depois, generalizamos o método para ordenar um vetor de dígitos (0 a 9). Finalmente,

observando que o tamanho das tábuas era de no máximo 10^4 e o número máximo de tábuas era

10^5, consideramos a aplicação da ordenação por contagem ao problema em questão.

Problema para casa: A. Apagando e Ganhando (Primeira Fase, Curitiba/2008) ou aqui: 11491 - Erasing and Winning 

Dia 15/10/08: Implementamos em sala a ordenação por contagem e usamos no problema do Salão do Clube. Submetemos a solução e verificamos a diminuição do tempo de execução.  Estudamos os conceitos de complexidade de tempo de melhor caso, pior caso e caso médio e o conceito de algoritmo ótimo e limite inferior. Estudamos o problema de encontrar o máximo de um vetor de inteiros. Vimos que o algoritmo padrão para o problema faz n-1 comparações. Mostramos que n-1 comparações é um limite inferior para resolver o problema. Assim, concluímos que o algoritmo visto é ótmo. 

Estudamos o problema de encontrar simultaneamente o máximo e o mínimo de um vetor de inteiros. Começamos com uma solução que faz 2(n-1) comparações. Melhoramos ela para uma solução que faz n-1 comparações no melhor caso e 3n/2-3/2 comparações no caso médio. Finalmente, estudamos um algoritmo que faz 3n/2 - 2 comparações no pior caso. Argumentamos que este algoritmo é ótimo.

Dia 22/10/08: Resolução de Problemas do site SPOJ Brasil:  

1850. Conte os Fatores 

842. Torres de Hanói 

Dia 5/11/08: Presentes: 9.  Resolução dos problemas Conte Fatores e Torres de Hanói.

Dia 12/11/08: Presentes 10. Aula expositiva sobre Grafos. Introdução. Discussão introdutória sobre problemas em grafos (apenas definição dos problemas): representação de grafos, vértices e arestas de corte, busca em largura e busca em profundidade, árvore espalhada de custo mínimo (MST - minimum spanning tree), caminhos mínimos, emparelhamento e fluxo em redes. Representação de grafos usando matrizes de ajacência em C. Funções de inicialização. Slides em anexo na mensagem do dia 12/11/08. Slides cobertos: 1 até 11.

Dia 19/11/08: 11 presentes. Busca em Grafos. Busca em Profundidade com Matriz de Adjacência e com Listas de Adjacências implementadas com matriz. Discussão sobre a final brasileira de 2008.

Problema para Casa: 1331. Dominó (SPOJ-BR) 

 

Dias 26/11 e 3/12/08: Programação Dinâmica: Seqüência de Fibonacci. Problema Candy. Problema da Subseqüência Comum mais Longa (LCS - longest common subsequence).

Para casa 1: Implementar a solução do problema Candy da Final Brasileira de 2008.

Para casa 2: Implementar a solução para o problema da Subseqüência Comum mais Longa. Versão 2.1: imprimir o valor da melhor solução (número de caracteres em comum)

Versão 2.2: imprimir UMA subseqüência comum mais longa

Versão 2.3: imprimir TODAS as subseqüências comuns mais longas.

 Slides sobre programação dinâmica: Parte I e Parte II.

Dia 17/4/2009:

Estudar programação dinâmica: capítulo 6 do livro Algorithms de Dasgupta, Papadimitriou e Vazirani.

Problemas:
1. Parque Jurássico
2. The Twin Towers

Dia 24/4/2009:

Problemas:

1.  2281. Rumo aos 9s  (SPOJ-BR)

2.  Problem F: Weights and Measures (UVa)

3.  1856. Pré, Em e Pós  (SPOJ-BR)
4.  Pedido de Desculpas (SPOJ-BR)
5.  Pizza (OBI2007-fase 2 nível 2)

Dia 2/5/2009:
Estudar grafos: capítulo 3 do livro Algorithms, de Dasgupta et al. e slides,
em anexo nesta mensagem.
Problemas:
1737. Mesa da Sra Montagny!
1822. Natureza (dica na interpretação do enunciado: a maior cadeia alimentar não é,  necessariamente, um caminho. O que torna o problema mais fácil.)

Dia 10/5/2009:
Problemas:

112. Tree Summing

344. Roman Digititis<http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&...>

Notem que o site da UVa mudou (novamente) de endereço (url), quebrando todos os links existentes na internet para os problemas. Agora é http://uva.onlinejudge.org como nos links acima.

Dia 15/5/2009:
Problemas:
1353. Festa Junina (SPOJ-BR)
1024. Complete Chess Boards  (SPOJ)
As soluções para os dois problemas envolvem o mesmo tema. Qual é?