Projeto e Analise de Algoritmos 2012

De Pontão Nós Digitais

Esta é a pagina principal de um curso de projeto de algoritmos ministrado em 2012 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 2012, voltado ao 7o. periodo de Engenharia da Computacao
  • Tercas e Quartas, 9:40-11:30am, sala 211 e Lab Inf 01


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

  • Inicie em http://community.topcoder.com/tc
  • Clique em "Register Now" ou "Login"
  • Clique em O(n) no canto superior esquerdo para iniciar a Arena topcoderalglink.png
  • No ubuntu linux, abra o nautilus (navegador de arquivo) no diretorio onde foi baixado o ContestAppletProd.jnlp
  • Clique no ContestApplestProd.jnlp com o botao direito do mouse, e selecione "abrir com Java Webstart" ou "Iced Tea"
    • Caso nao tenha essa opcao, instale os pacotes iced-tea* usando o synaptic ou outro gerenciador de pacotes
  • Faca o Login
  • Selecione Practice Rooms -> SRMs -> problemas Div 1. Os Div 2 sao mais dificeis e deixe-os para depois.
  • Mais informacoes em Topcoder Quickstart Tutorial
  • Meu template C++ para o topcoder: http://hera.ethymos.com.br:1080/reacpad/p/paa
  • Veja tambem os Editoriais, em que os melhores programadores explicam as solucoes de alguns SRM's e outras competicoes

Aulas - Slides

Provas

  • P1: 22 de maio [2]
  • P2: Quarta-feira dia 11 de julho
  • Sub: Sexta-feira dia 13 de julho 10:30am - 12pm [3]

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) [4] para discussao sobre software livre, linux, e afins.
    • Para discussoes gerais, podemos criar nossa propria sala de bate-papo.
    • 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.


Tarefa 1 (em aula)

  • Enunciado: flood fill algorithm
  • Data: primeira aula, 14/mar/2012
  • 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

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


Tarefa 3

  • 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

  • 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)
  • 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.
    • Um dos SRMs devera ser resolvido em maior detalhe, inclusive com pesquisa sobre assuntos que possam ser relevantes
    • 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.

Duplas p/ Trabalho

  • Colocar aqui o nome dos integrantes e o SRM(s) escolhidos (isto pode ser alterado no futuro se desejado)

Lucas Oliveira e José Eduardo = SRMs 536 DIV 2 e 149 DIV 2

Iwyson e Romulo: SRM 262 DIV2 e 491 DIV2

Marcos Belchior e Izabela Bastos : SRM 535 DIV2 SRM 281 DIV2

Lucas Vieira e Dayany Espíndola = SRM 147 DIV1 e SRM 450 DIV1

Eduardo Neves e André Portes = ???

Hamilton e Paulo = SRM Div2 503 e SRM 512 Div2

Criterio de Avaliacao

  • Trabalhos: 30% da media (antes era 10%)
  • 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.