Programação avançada

Professor: Rodrigo de Barros Paes

Grupo de email

pa-ic@googlegroups.com

Solicite a sua inscrição em: https://groups.google.com/d/forum/pa-ic

Como se matricular?

Se você é aluno de Engenharia da Computação ou Ciência da Computação da UFAL, procure as disciplinas de Programação Avançada.

As ementas que existem hoje são:

• Programação Avançada I (sexta-feira das 09:20 as 12:50)
• Programação Avançada III (sexta-feira das 15:20 as 18:50)

Checklist de assuntos

Estude os tópicos abaixo:

• Nível 1:
  • Saber usar direito a biblioteca padrão
  • Busca Binária
  • Busca Ternária
  • DFS/BFS
  • Bicoloração em grafos
  • Dijkstra, Bellman-Ford, Floyd-Warshall
  • PD bottom-up/top-down
  • Exponenciação rápida
  • Segment Tree
  • Fenwick Tree
  • Matemática básica (combinatória básica, gcd, lcm, etc)
• Nível 2:
  • Fluxo em grafos (ford-fulkerson)
    • Entender a relação entre minimo corte e máximo fluxo
  • Relações recursivas lineares com matriz (por exemplo: Fibonacci ou caminhos de tamanho k num grafo dirigido de 1 até n)
  • SQRT decomposition com "buckets"
  • Algoritmo de Mo (entra em SQRT)
  • PD em árvore
  • Merge sort tree
  • Inclusão-exclusão
  • Crivo e derivados (coisas que usam a série harmônica)
  • Geometria básica
    • Distância entre pontos, distância entre retas, convex-hull (olhar a parte de geometria do CP3)
• Nível 3:
  • Line sweep
  • Decomposição em centroide de árvore
  • 2-sat
  • FFT/NTT
  • Otimização de pd
  • Segment tree 2d
  • Tópicos de matemática mais avançada do CP3

No roteiro da UFMG, eles sugerem vários problemas para os tópicos acima. Use para praticar: http://wiki.maratona.dcc.ufmg.br/index.php/Roteiros

Contests

• Veteranos
  • 09/12/2017 (busca ternária): https://www.codepit.io/#/contest/5a1dd9230542c1001db2732e/view
  • 16/12/2017 (exponenciação rápida): https://www.codepit.io/#/contest/5a317be3514b8c001d7b3c45/view
  • 23/12/2017 (fluxo em grafos): https://www.codepit.io/#/contest/5a39a475514b8c001d7b3d66/view
  • 10/01/2018 (segment tree): https://www.codepit.io/#/contest/5a54c7ba636fa800962e43dd/view
• Novatos
  • 09/12/2017 (implementação [novatos]) https://www.codepit.io/#/contest/5a28a3e8514b8c001d7b391e/view
  • 16/12/2017 (busca binária [novatos]) https://www.codepit.io/#/contest/5a32d467b0b8a9001d0a17b1/view
• Faça os contests do codeforces e tente ir subindo no ranking. Mire a categoria imediatamente acima, depois a próxima, a próxima ... até chegar na vermelha.
  • http://codeforces.com/blog/entry/20638
• https://www.ime.usp.br/~maratona/acampimento-2016
• Quanto estiver no nível 3, treine com os problemas das finais da maratona:
  • Problemas da Final Brasileira da Maratona de Programação 2015:
    • Problem A - At most twice - [ Huxley 606 - https://www.thehuxley.com/problem/606 ]
    • Problem B - Blood groups - [ Huxley 609 - https://www.thehuxley.com/problem/609 ]
    • Problem C - Cake cut - [ Huxley 610 - https://www.thehuxley.com/problem/610 ]
    • Problem D - D as in Daedalus [ Huxley 612 - https://www.thehuxley.com/problem/612 ]
    • Problem E - Exposing corruption [ Huxley 613 - https://www.thehuxley.com/problem/613 ]
      • Comentários: Huxley 613 - Expondo a corrupção
    • Problem F - Fence the vegetables fail [ Huxley 614 - https://www.thehuxley.com/problem/614 ]
    • Problem G - Galactic taxes [ Huxley 615 - https://www.thehuxley.com/problem/615 ]
    • Problem H - Height map [ Huxley 611 - https://www.thehuxley.com/problem/611 ]
    • Problem I - Identifying tea [ Huxley 616 - https://www.thehuxley.com/problem/616 ]
    • Problem J - Just a bit sorted [ Huxley 617 - https://www.thehuxley.com/problem/617 ]
    • Problem K - Keep it energized [ Huxley 607 - https://www.thehuxley.com/problem/607 ]

Github

Aprenda com as soluções de seus colegas e contribua com a sua solução: https://github.com/r0drigopaes/maratonaic

Problemas

Só para esquentar

Fila e Fila de Prioridades

[Notas de aula]

Pilha

Dicionário

Busca completa / Backtracking

[Vídeo aula]

[Notas de aula]

Árvore

• Lowest Common Ancestor
• Árvore geradora mínima
  • Kruskal

Grafos

Notas de aula:

• [Percorrendo em Largura e Profundidade - notas de aula]
• [Implementação em C++, usando lista de adjacências]
• Flood Fill
  • [notas de aula sobre flood fill]
• Ordenação topológica
  • [notas de aula de ordenação topológica]
• Pontos de articulação e pontes
  • [notas de aula sobre pontos de articulação e pontes]
• Bicoloring
• Caminho mais barato entre dois pontos
  • Dijkstra
• Grafos com pesos negativos e que formam ciclos
  • Bellman Ford
  • SPFA modificado
• All Pair Shortest Paths
  • Floyd-Warshall´s
  • Ou use múltiplas chamadas ao Dijkstra ou ao Bellman-Ford
• Fluxo máximo
  • Ford-Fulkerson

Programação Dinâmica

[Vídeo aulas]

[notas de aula]

Range Minimum Query

• Range Minimum Query (RMQ)

Range Sum Query

• Range Sum Query (RSQ)

Estrutura de dados "sagazes"

• Segment Tree
• Sparse Table - RMQ
• Union-Find Disjoint Sets

Strings

• KMP
• Suffix trie, tree e array
• Longest Repeated Substring
• Longest Common Substring

Geometria Computacional

• Entendendo produto escalar e produto vetorial (dot product e cross product)
• Closest Pair of Points
• Interseção entre retas
• Distância entre ponto e reta
• Círculos

Teoria dos números

• Exponenciação binária (ou modular)
  • https://www.hackerearth.com/notes/number-theory-1/
• Testar se um número é primo
  • https://www.hackerearth.com/notes/number-theory-1/

Outros temas

• Multiplicação de Matrizes
  • https://docs.google.com/presentation/d/1fRsz-_f_LKannY0rVwX2MceXI1VwtAesuZq0gINZGiA/edit?usp=sharing

Bibliografia

1. Introdução à Programação com a Linguagem C: Aprenda a resolver problemas com uma abordagem prática.
   1. Rodrigo de Barros Paes. Editora: Novatec, 2016.
2. Skiena, Steven S, Programming Challenges: The Programming Contest Training Manual (Texts in Computer Science), 2003
3. Cormen, Thomas H., et al. Introduction to algorithms. Ed 3. Cambridge: MIT press, 2009.
4. Halim, Steven. Competitive Programming 3. 2013.Available at: https://sites.google.com/site/stevenhalim/

Sites

• https://www.hackerearth.com/codemonk/
• https://www.topcoder.com/community/competitive%20programming/
• http://codeforces.com
• https://uva.onlinejudge.org
• https://thehuxley.com

Fotos