Roteiro de Assuntos

Estruturas de dados
- Union Find Disjoint Set
- Pilha
- Fila
- Fila de Prioridades
- Set
- Map
- Grafos
- Fenwick Tree
- Segment Tree
- Matriz Esparsa
- RMQ
- RSQ
Backtraking
- Bitmask
- Heavy Pruning
Programação Dinâmica
- Mochila
  - UVA 562
  - UVA 624
  - UVA 990
  - UVA 10261
  - UVA 11331
- Multiplicação de Matrizes
  - Huxley 557
- Distância de edição
  - Huxley 558
- Texto Justificado
  - Huxley 555
- Max 1D Range Sum
  - UVA 507
  - UVA 787
  - UVA 10684
- Max 2D Range Sum
  - UVA 108
  - UVA 836
  - UVA 10827
- Troco
  - UVA 147
  - UVA 166
  - UVA 357
- Bitmask
- Longest Increasing Subsequence
  - UVA 111
  - UVA 481
  - UVA 1196
  - UVA 11456
- Traveling Salesman
  - UVA 216
  - UVA 10496
  - UVA 11284
Grafos (ver página da disciplina)
- BFS
- DFS
  - UVA 11902
- Componentes conectados
  - UVA 459
- Flood fill
  - UVA 469
  - UVA 260
  - UVA 1103
  - UVA 10336
- Topological sort
  - UVA 10305
  - UVA 124
  - UVA 872
  - UVA 10305
  - UVA 11060
- Grafos bipartidos
  - UVA 10004
  - UVA 663
  - UVA 10349
  - UVA 11045
- Edge-Disjoint Paths
  - UVA 10806
  - UVA 11597
- Encontrando ciclos através de DFS
  - UVA 10515
- Pontos de articulação e pontes
  - UVA 315
  - UVA 610
  - UVA 796
  - UVA 10765
- Componentes fortemente conectados
  - UVA 247
  - UVA 1229
  - UVA 10731
  - UVA 11504
  - UVA 11838
- Minimum Spanning Tree (MST)
  - Kruskal
  - Prim
  - Problemas
    - UVA 908
    - UVA 1174
    - UVA 1208
    - UVA 10369
    - UVA 11733
    - UVA 11747
    - UVA 10600
    - UVA 1234
    - UVA 10147
- Caminho mais curto simples
  - BFS com grafos sem pesos
    - UVA 336
    - UVA 383
    - UVA 10653
    - UVA 532
    - UVA 11049
    - UVA 10977
    - UVA 11101
    - UVA 11513
    - UVA 10150
  - Dijkstra
    - UVA 929
    - UVA 1112
    - UVA 10389
    - UVA 10986
    - UVA 11367
    - UVA 1202
    - UVA 10166
    - UVA 10278
    - UVA 10801
  - Bellman-Ford (ciclos negativos)
    - UVA 558
    - UVA 10449
    - UVA 10557
    - UVA 11280
  - SPFA
- Caminho mais curto (todos)
  - Floyd Warshall com DP
  - Steven Warshall
    - verifica se é possível chegar de i para j
- Grafos especiais
  - Tree
    - LCA
    - Binary
    - AVL
  - Eulerian
- Stoer Wagner (minimum cut)
- Gale Shapley (stable matching)
- Árvore Gomory-HU
Fluxo de redes
- Ford-Fulkerson (max flow)
- Dinic's (max flow)
- Problemas
  - UVA 259
  - UVA 820
  - UVA 11082
Caixeiro Viajante
Matemática
- Big numbers
- Combinatória
  - Fibonacci
    - Matriz de Potência ( Pág 364 )
  - Coeficiente Binomial
  - Catalan Numbers
- Teoria dos números
  - Primos
    - Fatores
    - Crivo de Sieve
  - Maior divisor comum
  - Mínimo múltiplo comum
  - Fatorial
  - Aritmética modular
    - Encontrando ciclos
  - Equações Diofantinas
    - UVA 718
    - UVA 11768
  - Cadeia de Markov
- Teoria dos Jogos
  - Nim Game
  - Árvore de decisão
  - MinMax
- Álgebra Linear
  - Matrizes
  - Eliminação Gaussiana
- Discrete Fourier Transform (DFT)
  - http://www.spoj.com/problems/MUL/
Processamento de string
- Encontrar substrings
  - KMP
  - Rabin-Karp
- Trie de sufixo
- Árvore de sufixo
- Array de sufixo
Geometria Computacional (usar Java)
- Objetos 0-D
  - Pontos
    - Distância
    - Rotação
    - Translação
- Objetos 1-D
  - Retas
    - Construir a partir de pontos
    - Paralelas
    - Igualdades
    - Interseção
    - Segmentos de retas
      - Interseção
    - Distância para um ponto
    - Co-linear
    - Teste CCW ( Anti-horário)
    - Point c in line l that is closest to point p
  - Vetores
    - Escala
    - Translação
    - Rotação
    - Produto Escalar
    - Norma
    - Ângulo
    - Produto Vetorial
- Objetos 2-D
  - Círculos
    - Área
    - Posição do ponto
    - Localizar centros de círculos que se interceptam
    - Problemas:
      - Faster Than a Speeding Bullet (prog. chall. pág 299)
      - UVA 10310
      - UVA 10180
      - UVA 10195
      - UVA 10136
      - UVA 10167
      - UVA 10215
      - UVA 10209
      - UVA 10012
  - Triângulos
    - Área
    - Relações com circunferências
  - Quadriláteros
  - Polígonos
    - Perímetro
    - Área
      - Algoritmo de Van Gogh
    - Côncavo ou convexo
    - Ponto dentro
    - Corte
    - Convex Hull
  - Plane Sweep
  - Line Sweep
  - Closest Pair
  - Furthest Pair
  - Rotating Calipers
  - KD-Tree
  - Problemas
    - UVA 10135
    - UVA 10245
    - UVA 10043
    - UVA 10084
    - UVA 10065
    - UVA 849
    - UVA 10088
    - UVA 10117
- Objetos 3-D
Grids
- Plate Weight (programming challenges pág 275)
- Circle Packing (prog. challen. pág 277)
- Problemas
  - UVA 10161
  - UVA 10047
  - UVA 10159
  - UVA 10182
  - UVA 707
  - UVA 10177
  - UVA 10233
  - UVA 10075
Jogos
- MinMax
- Hackenbush
- Problemas
  - TIMUS 1610

Google Sites

Report abuse