Programação avançada

Grupo de email

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

Link

Comentários

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

Estrutura de dados "sagazes"

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

Link

Huxley 690

Huxley 659

Comentários

Exponenciação de matrizes utilizando dividir e conquistar. Mais especificamente Exponentiation By Squaring

Problema de cadeia de markov. Os comentários estão em:

https://youtu.be/CnhNkRwHytQ

Bibliografia

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.
Skiena, Steven S, Programming Challenges: The Programming Contest Training Manual (Texts in Computer Science), 2003
Cormen, Thomas H., et al. Introduction to algorithms. Ed 3. Cambridge: MIT press, 2009.
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

Google Sites

Report abuse