Mudanças entre as edições de "Projeto e Analise de Algoritmos"

De Pontão Nós Digitais
(Informacoes gerais)
 
(40 revisões intermediárias por 4 usuários não estão sendo mostradas)
Linha 1: Linha 1:
Esta é a pagina principal de um curso de projeto de algoritmos ministrado em 2013 no [http://pt.wikipedia.org/wiki/IPRJ IPRJ]/[http://pt.wikipedia.org/wiki/IPRJ UERJ], de utilidade geral para a formacao de programadores de nivel intermediario e avancado.
+
Esta é a pagina principal de um curso de projeto de algoritmos ministrado em 2014 no [http://pt.wikipedia.org/wiki/IPRJ IPRJ]/[http://pt.wikipedia.org/wiki/IPRJ UERJ], de utilidade geral para a formacao de programadores de nivel intermediario e avancado.
  
'''[[PAA2012|Link para o curso de 2012]]'''
+
* Links para o curso de '''[[PAA2012|2012]]''', '''[[PAA2012|2013]]'''.
  
 
[[Imagem:Grafo-cidades-rj-sp-ms.png|right|550px]]
 
[[Imagem:Grafo-cidades-rj-sp-ms.png|right|550px]]
 
== Informacoes gerais ==
 
== Informacoes gerais ==
* Instrutor: prof. [http://www.lems.brown.edu/~rfabbri Ricardo Fabbri], Ph.D.
+
* Instrutor: prof. [http://rfabbri.github.io Ricardo Fabbri], Ph.D.
* Periodo: 1o. Semestre de 2013, voltado ao 7o. periodo de Engenharia da Computacao
+
* Periodo: 1o. Semestre de 2014, voltado ao 7o. periodo de Engenharia da Computacao
* Tercas e Quintas, 10:40-12:20am, sala 212 e Lab Inf 02
+
* Tercas e Quintas, 10:40-12:20am, sala 209 e Lab Inf #??
  
  
Linha 40: Linha 40:
 
* Selecione Practice Rooms -> SRMs  -> problemas Div 1. Os Div 2 sao mais dificeis e deixe-os para depois.
 
* Selecione Practice Rooms -> SRMs  -> problemas Div 1. Os Div 2 sao mais dificeis e deixe-os para depois.
 
* Mais informacoes em [http://blog.theroyweb.com/topcoder-quickstart-tutorial Topcoder Quickstart Tutorial]
 
* Mais informacoes em [http://blog.theroyweb.com/topcoder-quickstart-tutorial Topcoder Quickstart Tutorial]
* Meu template C++ para o topcoder: http://hera.ethymos.com.br:1080/reacpad/p/paa
+
* Meu template C++ para o topcoder: http://sourceforge.net/p/labmacambira/utils/ci/master/tree/templates/topcoder/a.cc
 
* Veja tambem os Editoriais, em que os melhores programadores explicam as solucoes de alguns SRM's e outras competicoes
 
* Veja tambem os Editoriais, em que os melhores programadores explicam as solucoes de alguns SRM's e outras competicoes
 
** http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis
 
** http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis
  
 
=== Aulas - Slides ===
 
=== Aulas - Slides ===
* [http://www.lems.brown.edu/~rfabbri/stuff/01-busca-em-grafos.odp busca em grafos - 26/mar - 4/apr] (atualizado em 8/apr)
+
* '''Baixe todas as aulas:''' [https://drive.google.com/open?id=0B8Z1cZSIN8qyVklPQXpCVFRjdnM Download]
* [http://www.lems.brown.edu/~rfabbri/stuff/02-greedy-etc.odp algoritmos greedy / gulosos]
+
* [https://drive.google.com/uc?export=download&id=0B8Z1cZSIN8qyQTZ4RE1hd3ZSX2c busca em grafos] (atualizado em 8/apr/2012) - cai na P1
* [http://www.lems.brown.edu/~rfabbri/stuff/03-analise-e-divide_and_conquer.odp analise e divide-and-conquer] (atualizado em 20/jun) - cai na P2
+
* [https://drive.google.com/uc?export=download&id=0B8Z1cZSIN8qybUtISWxaSU9mWW8 algoritmos greedy / gulosos] - cai na P1
* [http://www.lems.brown.edu/~rfabbri/stuff/04-dynamic-programming.odp dynamic programming / programacao dinamica] (atualizado em 20-26/jun) - cai na P2
+
* [https://drive.google.com/uc?export=download&id=0B8Z1cZSIN8qyaThXZ2NaYl9UODA analise e divide-and-conquer] (atualizado em 20/jun/2012) - cai na P1
 +
* [https://drive.google.com/uc?export=download&id=0B8Z1cZSIN8qyUDVfaTBIc0duOTg dynamic programming / programacao dinamica] (atualizado em 20-26/jun/2013) - cai na P1
 +
* [https://drive.google.com/uc?export=download&id=0B8Z1cZSIN8qyc0VZWWFuWmVoazA network flow / fluxo em redes -- Parte 1] (atualizado em 20/jun/2013) - cai na P2
 +
* escovando bits
 +
 
 
=== Provas ===
 
=== Provas ===
* P1: 22 de maio [http://www.lems.brown.edu/~rfabbri/stuff/prova-p1-PAA2012.pdf]
+
* P1: 27/jun/2013 [http://www.lems.brown.edu/~rfabbri/stuff/prova-p1-PAA2012.pdf (prova anterior: 2012)]
* P2: Quarta-feira dia 11 de julho
+
* P2:  
* Sub: Sexta-feira dia 13 de julho 10:30am - 12pm [http://www.lems.brown.edu/~rfabbri/stuff/prova-sub-PAA2012.pdf]
+
* Sub/Final: [http://www.lems.brown.edu/~rfabbri/stuff/prova-sub-PAA2012.pdf (prova anterior: 2012)]
  
 
== Recursos adicionais ==
 
== Recursos adicionais ==
Linha 59: Linha 63:
 
* [[Lab Macambira]]: grupo de desenvolvedores de software livre e ajuda com Linux e atividades extra-curriculares de programacao.
 
* [[Lab Macambira]]: grupo de desenvolvedores de software livre e ajuda com Linux e atividades extra-curriculares de programacao.
 
** Confira a sala de bate papo no IRC #labmacambira (freenode) [http://labmacambira.sf.net] para discussao sobre software livre, linux, e afins.
 
** Confira a sala de bate papo no IRC #labmacambira (freenode) [http://labmacambira.sf.net] para discussao sobre software livre, linux, e afins.
** Para discussoes gerais, podemos criar nossa propria sala de bate-papo.
+
** Para discussoes gerais, podemos criar nossa propria sala de bate-papo, veja #iprj
 
** [[Configuring Ubuntu for Programming]]
 
** [[Configuring Ubuntu for Programming]]
  
Linha 71: Linha 75:
 
Quando a tarefa involver qualquer programacao, o aluno devera enviar o codigo fonte. O codigo junto com a documentacao devera estar dentro de um unico diretorio comprimido com .zip ou tar, com o nome do aluno, disciplina e data.
 
Quando a tarefa involver qualquer programacao, o aluno devera enviar o codigo fonte. O codigo junto com a documentacao devera estar dentro de um unico diretorio comprimido com .zip ou tar, com o nome do aluno, disciplina e data.
  
 +
=== Tarefas de 2014 ===
  
=== Tarefa 1 (em aula) ===
+
==== Tarefa 0 (em aula) ====
* Enunciado: flood fill algorithm
+
* Enunciado: flood fill algorithm / labirinto
* Data: primeira aula, 14/mar/2012
+
* Data: primeira aula
* Alunos que entregaram
+
** Eduardo Neves Goulart
+
** Lucas Vieira Souza
+
** Izabela Bastos Noe
+
** Lucas da Silva Oliveira
+
** José Eduardo de A. Agres
+
** Dario Antonio Sanches
+
** Marcos Belchior
+
** Romulo Henrique
+
  
=== Tarefa 2 ===
+
==== Tarefa 1, Importancia de Grafos - 18/mar/2014 ====
 
* Resumir inicio cap 3 do livro de Kleinberg & Tardos, prestando atencao `as aplicacoes
 
* Resumir inicio cap 3 do livro de Kleinberg & Tardos, prestando atencao `as aplicacoes
 +
** Focar nas secoes 3.1 e 3.2
 +
* Utilizar suas palavras e dar sua opiniao onde couber
 
* Digitar em [[Latex]] de preferencia
 
* Digitar em [[Latex]] de preferencia
* Alunos que entregaram
+
* Entrega: 25/Marco/2014
** Marcos Belchior
+
 
+
  
=== Tarefa ===
+
==== Tarefa 2 Busca ====
 
* Enunciado:  BFS pode ser implementado recursivamente? ficaria a implementação?
 
* Enunciado:  BFS pode ser implementado recursivamente? ficaria a implementação?
  
=== Tarefa 4 ===
 
* Enunciado: falar sobre lista de adjacência, matriz de adjacência, lista "direta", matriz de pixels (confirmar)
 
  
=== Tarefa 5 ===
+
=== Projetos no Top Coder ===
* Enunciado: resumo do 4.1, 4.2 e 4.3 (confirmar)
+
 
+
=== Tarefa 6 (em aula) ===
+
* Enunciado: escovando bits e bytes
+
* Alunos que entregaram
+
** Jose Ayres
+
** Izabela Noe
+
** Lucas Vieira
+
** Dayany Cortes
+
** Eduardo Goulart
+
** Romulo Henrique
+
** Paulo Cabral
+
** Hamilton
+
** Lucas Oliveira
+
** Iwyson Thuller
+
 
+
=== Apresentacao  ===
+
* Conteudo: Agendamento de intervalos, algoritmos de cache, estrategias Greedy.
+
* Dayany
+
* Marcos Belchior
+
 
+
=== Projeto no Top Coder ===
+
  
 
* Criar um login do topcoder (anonimo, so voce sabe)
 
* Criar um login do topcoder (anonimo, so voce sabe)
* Fazer 2 SRM's (a serem entregues no futuro). Documente sua solucao (em [[Latex]] de preferencia). Esses SRMs devem ser tais que nao ha' editorial a respeito no topcoder.
+
* Fazer 2 SRM's (div 1 ou 2) a serem entregues em forma de relatório e apresentados ao professor no futuro. Documente sua solucao (em [[Latex]] de preferencia).  
** Um dos SRMs devera ser resolvido em maior detalhe, inclusive com pesquisa sobre assuntos que possam ser relevantes
+
** Cada aluno deverá escolher um SRM primário, do qual será responsável, e um SRM secundário, em que deverá ajudar um outro aluno.
 +
** Os SRMs primário deverá ser programado em maior detalhe pelos alunos responáveis, inclusive com pesquisa sobre assuntos que possam ser relevantes
 +
** Cada aluno irá entregar um relatório e irá fazer um exame oral individual rapido para mostrar que sabe programar os problemas do seus SRMs.
 
** Sugestoes para um trabalho bem-feito:
 
** Sugestoes para um trabalho bem-feito:
 
*** Comente as partes mais obscuras do editorial do seu SRM, se disponivel
 
*** Comente as partes mais obscuras do editorial do seu SRM, se disponivel
Linha 131: Linha 105:
 
*** Forneca desenhos, diagramas, fluxogramas explicando os conceitos e etapas do algoritmo
 
*** Forneca desenhos, diagramas, fluxogramas explicando os conceitos e etapas do algoritmo
 
*** Forneca trechos de livros / pesquisa bibliografica de assuntos que mais te interessaram ou que mais foram uteis na solucao de cada problema.
 
*** Forneca trechos de livros / pesquisa bibliografica de assuntos que mais te interessaram ou que mais foram uteis na solucao de cada problema.
 +
* Notas
 +
** Cada trabalho (SRM) terá uma nota final com base na apresentacao oral ao professor e relatorio
 +
** A nota de cada aluno sera 70% a nota do seu SRM primário mais 30% a nota final do SRM secundário
 +
** Atencao: O peso deste trabalho poderá suplantar o da P2 caso os alunos estejam de acordo.
  
 
==== Duplas p/ Trabalho ====
 
==== Duplas p/ Trabalho ====
 
* Colocar aqui o nome dos integrantes e o SRM(s) escolhidos (isto pode ser alterado no futuro se desejado)
 
* Colocar aqui o nome dos integrantes e o SRM(s) escolhidos (isto pode ser alterado no futuro se desejado)
 +
* Nao pode haver repeticao de SRMs
 +
* Evitar repetir os colegas primarios/secundarios (mas se for necessario repetir, tudo bem)
  
Lucas Oliveira e José Eduardo = SRMs 536 DIV 2 e 149 DIV 2
+
/------------- 2014 ----------------/
  
Iwyson e Romulo: SRM 262 DIV2 e 491 DIV2
+
Ana Carolina Castro (Primária) e Ciro Chang (Secundário): SRM 220 DIV2
  
Marcos Belchior e Izabela Bastos : SRM 535 DIV2 SRM 281 DIV2  
+
Ciro Chang (Primário) e Ana Carolina Castro(Secundária): SRM 382 DIV2
  
Lucas Vieira e Dayany Espíndola = SRM 147 DIV1 e SRM 450 DIV1
+
Luiz Fernando (Primário) e Paulo Augusto (Secundário): SRM 261 DIV 2
  
Eduardo Neves e André Portes = ???
+
Jayme Nogueira (Primário) e Luiz Fernando (Secundário): SRM 318 DIV 2
  
Hamilton e Paulo = SRM Div2 503 e SRM 512 Div2
+
Paulo Augusto (Primário) e Jayme Nogueira (Secundário): SRM 367 DIV 2
 +
 
 +
/------------- 2013 ----------------/
 +
 
 +
Caio(Primário) e Pedro(Secundário): SRM 145 DIV2
 +
 
 +
Gustavo(Primário) e Marcos(Secundário): SRM 147 DIV2
 +
 
 +
Marcos(Primário) e Gustavo(Secundário): SRM 149 DIV2
 +
 
 +
Pedro(Primário) e Caio(Secundário): SRM 144 DIV1
 +
 
 +
Rafael Ferrari(Primário) e Rafael Erthal(Secundário): SRM 152 DIV2
 +
 
 +
Rafael Erthal(Primário) e Rafael Ferrari(Secundário): SRM 174 DIV2
 +
 
 +
Lucas Oliveira(Primário) e Guilherme Carneiro(Secundário): SRM 144 DIV2
 +
 
 +
Guilherme Carneiro(Primário) e Lucas Oliveira(Secundário): SRM 217 DIV2
 +
 
 +
==== Bonus TopCoder ====
 +
Opcionalmente, pontos extras na media serao concedido a alunos que participarem de SRM's oficiais de acordo com os seguintes criterios:
 +
* '''Para receber o bonus o aluno tera que obter nota na P1 acima de 6'''
 +
* Alunos que participarem de um SRM oficial e relatarem os problemas  e solucoes num relatorio curto irao receber ate 1 ponto adicional na media
 +
* Alunos que competirem entre si e obteve primeiro lugar na sala (num mesmo SRM) irao receber ate 2 pontos adicionais na media, contanto que o numero de participantes da sala seja igual ou maior que 3
 +
* Alunos que resolverem todos os problemas dentro do tempo oficial do SRM irao obter 3 pontos adicionais na media
 +
* Alunos que obtiverem top 5 geral no SRM irao passar com media 10
 +
* '''Voces tem varias chances!'''
 +
** Calendario de SRMs do topcoder (horario EST de nova yorque) [http://community.topcoder.com/tc?module=Static&d1=calendar&d2=thisMonth]
 +
 
 +
=== Tarefas de 2013 ===
 +
 
 +
==== Tarefa 1 (em aula) - 2013 ====
 +
* Enunciado: flood fill algorithm / labirinto
 +
* Data: primeira aula
 +
* Alunos que entregaram
 +
** ((lista pendente))
 +
 
 +
==== Tarefa 2 - 2013 ====
 +
* Enunciado: Topological Sort
 +
* Estudar e comentar o funcionamento do codigo fonte do comando GNU tsort do unix
 +
* Pesquisar como funciona a arvore utilizada no codigo
 +
* Note que o algoritmo eh simples mas nao eh trivial de implementar bem
 +
 
 +
==== Tarefa 3 - 2013 ====
 +
* Implementar o mergesort
 +
* Plotar grafico do tempo de execucao minimo, maximo, e medio para diferentes tamanhos de entradas aleatoreas
 +
 
 +
=== Tarefas de 2012 ===
 +
 
 +
==== Tarefa 1 (em aula) - 2012 ====
 +
* Enunciado: flood fill algorithm / labirinto
 +
* Data: primeira aula
 +
 
 +
==== Tarefa 2  - 2012 ====
 +
* Resumir inicio cap 3 do livro de Kleinberg & Tardos, prestando atencao `as aplicacoes
 +
* Digitar em [[Latex]] de preferencia
 +
 
 +
==== Tarefa 3 - 2012 ====
 +
* Enunciado:  BFS pode ser implementado recursivamente? ficaria a implementação?
 +
 
 +
==== Tarefa 4 - 2012 ====
 +
* Enunciado: falar sobre lista de adjacência, matriz de adjacência, lista "direta", matriz de pixels (confirmar)
 +
 
 +
==== Tarefa 5 - 2012 ====
 +
* Enunciado: resumo do 4.1, 4.2 e 4.3 (confirmar)
 +
 
 +
==== Tarefa 6 (em aula) - 2012 ====
 +
* Enunciado: escovando bits e bytes
 +
 
 +
==== Apresentacao  - 2012 ====
 +
* Conteudo: Agendamento de intervalos, algoritmos de cache, estrategias Greedy.
  
 
== Criterio de Avaliacao ==
 
== Criterio de Avaliacao ==
  
* Trabalhos: 30% da media (antes era 10%)
+
* Trabalhos: 30% da media
 
* O criterio final e simplificado ficou (favor avisar se precisar adicionar detalhes ou corrigir no caso de erro/discrepancia):
 
* O criterio final e simplificado ficou (favor avisar se precisar adicionar detalhes ou corrigir no caso de erro/discrepancia):
 
<small>
 
<small>

Edição atual tal como às 23h21min de 1 de abril de 2019

Esta é a pagina principal de um curso de projeto de algoritmos ministrado em 2014 no IPRJ/UERJ, de utilidade geral para a formacao de programadores de nivel intermediario e avancado.

Grafo-cidades-rj-sp-ms.png

Informacoes gerais

  • Instrutor: prof. Ricardo Fabbri, Ph.D.
  • Periodo: 1o. Semestre de 2014, voltado ao 7o. periodo de Engenharia da Computacao
  • Tercas e Quintas, 10:40-12:20am, sala 209 e Lab Inf #??


Pre-requisitos

  • Sera assumido um primeiro curso em algoritmos e estruturas de dados, porem nao e' obrigatorio.

Conteudo aproximado

  • Enfase no projeto (design) de algoritmos
  • Enfase em grafos
  • Uso do C++ e' preferivel
  • Enfase no uso do TopCoder para exercicios
  • Algoritmos gulosos / greedy
  • Programacao dinamica
  • Fluxo em redes (Network flows)

Recursos principais

Bibliografia

  • Livro principal: "Algorithm Design" - Jon Kleinberg & Eva Tardos (ver uerj.tk) cover.jpg
    • Trata-se do melhor livro para estudar para uma entrevista. O Autor desenvolveu ideias das mais famosas relacionados ao PageRank do Google [1]
  • Livro interessante com foco em algoritmos geometricos: Algorithmic Geometry

Top Coder

Aulas - Slides

Provas

Recursos adicionais

  • Slides de aula em Princeton
  • Site de material extra-oficial e troca p2p entre alunos: uerj.tk
  • Lab Macambira: grupo de desenvolvedores de software livre e ajuda com Linux e atividades extra-curriculares de programacao.
    • Confira a sala de bate papo no IRC #labmacambira (freenode) [2] para discussao sobre software livre, linux, e afins.
    • Para discussoes gerais, podemos criar nossa propria sala de bate-papo, veja #iprj
    • Configuring Ubuntu for Programming

Tarefas

Somente serao aceitos arquivos eletronicos no formato PDF ou outro formato aberto como .odt

As tarefas devem ser formatadas com notacao matematica adequada, preferencialmente em Latex.

Somente serao aceitos arquivos eletronicos no formato PDF ou outro formato aberto como .odt

Quando a tarefa involver qualquer programacao, o aluno devera enviar o codigo fonte. O codigo junto com a documentacao devera estar dentro de um unico diretorio comprimido com .zip ou tar, com o nome do aluno, disciplina e data.

Tarefas de 2014

Tarefa 0 (em aula)

  • Enunciado: flood fill algorithm / labirinto
  • Data: primeira aula

Tarefa 1, Importancia de Grafos - 18/mar/2014

  • Resumir inicio cap 3 do livro de Kleinberg & Tardos, prestando atencao `as aplicacoes
    • Focar nas secoes 3.1 e 3.2
  • Utilizar suas palavras e dar sua opiniao onde couber
  • Digitar em Latex de preferencia
  • Entrega: 25/Marco/2014

Tarefa 2 Busca

  • Enunciado: BFS pode ser implementado recursivamente? ficaria a implementação?


Projetos no Top Coder

  • Criar um login do topcoder (anonimo, so voce sabe)
  • Fazer 2 SRM's (div 1 ou 2) a serem entregues em forma de relatório e apresentados ao professor no futuro. Documente sua solucao (em Latex de preferencia).
    • Cada aluno deverá escolher um SRM primário, do qual será responsável, e um SRM secundário, em que deverá ajudar um outro aluno.
    • Os SRMs primário deverá ser programado em maior detalhe pelos alunos responáveis, inclusive com pesquisa sobre assuntos que possam ser relevantes
    • Cada aluno irá entregar um relatório e irá fazer um exame oral individual rapido para mostrar que sabe programar os problemas do seus SRMs.
    • Sugestoes para um trabalho bem-feito:
      • Comente as partes mais obscuras do editorial do seu SRM, se disponivel
      • Compare sua solucao com a solucao de outro participante mais experiente (um dos primeiros colocados do SRM)
        • Em que a solucao dele difere da sua? O que ele aparenta ter feito/usado?
      • Forneca desenhos, diagramas, fluxogramas explicando os conceitos e etapas do algoritmo
      • Forneca trechos de livros / pesquisa bibliografica de assuntos que mais te interessaram ou que mais foram uteis na solucao de cada problema.
  • Notas
    • Cada trabalho (SRM) terá uma nota final com base na apresentacao oral ao professor e relatorio
    • A nota de cada aluno sera 70% a nota do seu SRM primário mais 30% a nota final do SRM secundário
    • Atencao: O peso deste trabalho poderá suplantar o da P2 caso os alunos estejam de acordo.

Duplas p/ Trabalho

  • Colocar aqui o nome dos integrantes e o SRM(s) escolhidos (isto pode ser alterado no futuro se desejado)
  • Nao pode haver repeticao de SRMs
  • Evitar repetir os colegas primarios/secundarios (mas se for necessario repetir, tudo bem)

/------------- 2014 ----------------/

Ana Carolina Castro (Primária) e Ciro Chang (Secundário): SRM 220 DIV2

Ciro Chang (Primário) e Ana Carolina Castro(Secundária): SRM 382 DIV2

Luiz Fernando (Primário) e Paulo Augusto (Secundário): SRM 261 DIV 2

Jayme Nogueira (Primário) e Luiz Fernando (Secundário): SRM 318 DIV 2

Paulo Augusto (Primário) e Jayme Nogueira (Secundário): SRM 367 DIV 2

/------------- 2013 ----------------/

Caio(Primário) e Pedro(Secundário): SRM 145 DIV2

Gustavo(Primário) e Marcos(Secundário): SRM 147 DIV2

Marcos(Primário) e Gustavo(Secundário): SRM 149 DIV2

Pedro(Primário) e Caio(Secundário): SRM 144 DIV1

Rafael Ferrari(Primário) e Rafael Erthal(Secundário): SRM 152 DIV2

Rafael Erthal(Primário) e Rafael Ferrari(Secundário): SRM 174 DIV2

Lucas Oliveira(Primário) e Guilherme Carneiro(Secundário): SRM 144 DIV2

Guilherme Carneiro(Primário) e Lucas Oliveira(Secundário): SRM 217 DIV2

Bonus TopCoder

Opcionalmente, pontos extras na media serao concedido a alunos que participarem de SRM's oficiais de acordo com os seguintes criterios:

  • Para receber o bonus o aluno tera que obter nota na P1 acima de 6
  • Alunos que participarem de um SRM oficial e relatarem os problemas e solucoes num relatorio curto irao receber ate 1 ponto adicional na media
  • Alunos que competirem entre si e obteve primeiro lugar na sala (num mesmo SRM) irao receber ate 2 pontos adicionais na media, contanto que o numero de participantes da sala seja igual ou maior que 3
  • Alunos que resolverem todos os problemas dentro do tempo oficial do SRM irao obter 3 pontos adicionais na media
  • Alunos que obtiverem top 5 geral no SRM irao passar com media 10
  • Voces tem varias chances!
    • Calendario de SRMs do topcoder (horario EST de nova yorque) [3]

Tarefas de 2013

Tarefa 1 (em aula) - 2013

  • Enunciado: flood fill algorithm / labirinto
  • Data: primeira aula
  • Alunos que entregaram
    • ((lista pendente))

Tarefa 2 - 2013

  • Enunciado: Topological Sort
  • Estudar e comentar o funcionamento do codigo fonte do comando GNU tsort do unix
  • Pesquisar como funciona a arvore utilizada no codigo
  • Note que o algoritmo eh simples mas nao eh trivial de implementar bem

Tarefa 3 - 2013

  • Implementar o mergesort
  • Plotar grafico do tempo de execucao minimo, maximo, e medio para diferentes tamanhos de entradas aleatoreas

Tarefas de 2012

Tarefa 1 (em aula) - 2012

  • Enunciado: flood fill algorithm / labirinto
  • Data: primeira aula

Tarefa 2 - 2012

  • Resumir inicio cap 3 do livro de Kleinberg & Tardos, prestando atencao `as aplicacoes
  • Digitar em Latex de preferencia

Tarefa 3 - 2012

  • Enunciado: BFS pode ser implementado recursivamente? ficaria a implementação?

Tarefa 4 - 2012

  • Enunciado: falar sobre lista de adjacência, matriz de adjacência, lista "direta", matriz de pixels (confirmar)

Tarefa 5 - 2012

  • Enunciado: resumo do 4.1, 4.2 e 4.3 (confirmar)

Tarefa 6 (em aula) - 2012

  • Enunciado: escovando bits e bytes

Apresentacao - 2012

  • Conteudo: Agendamento de intervalos, algoritmos de cache, estrategias Greedy.

Criterio de Avaliacao

  • Trabalhos: 30% da media
  • O criterio final e simplificado ficou (favor avisar se precisar adicionar detalhes ou corrigir no caso de erro/discrepancia):

     M_p = (P1 + P2)/2   
     M = 0.7*M_p + 0.3*T (atualizado de 10% para 30% com acordo dos alunos), onde T é a nota dos trabalhos
     Se M >= 5, passa --> M
     Sub: repoe menor de P1, P2 (apenas se alguem faltou alguma prova ou quiser melhorar nota - mas quem entregar ira substituir)
     M_sub = media com sub
     Se M_sub >= 5, passou --> M_sub
     Adendo (em acordo com os alunos): a M_sub = M_f pois sera considerada a mesma prova e a prova final nao mas faz efeito real com trabalhos a 30%.  Quem for usar a prova como Sub ira substituir a nota independentemente do resultado.

  • A prova final passa a nao ser mais obrigatoria.