Programação dinâmica

1. A maior subseqüência comum de duas seqüências T e P é a maior seqüência L que é simultaneamente uma subseqüência de T e de P.
A menor superseqüência comum de duas seqüências T e P é a menor seqüência L tal que
ambas, T e P, são subseqüências de L.

2. Dada uma seqüência S_n de inteiros descobrir se existe uma subseqüência com soma K. 

3. Dada uma seqüência S_n de inteiros descobrir se existe uma seqüência que tenha a mesma soma do complemento de sua seqüência.
(Questão C da aula prática 3). 

4. Dada uma seqüência de números S_n, achar a maior seqüência crescente de números.

5. Dadas n moedas com seus respectivos valores, achar quantas maneiras podemos escolher tais moedas para obter um valor V dado.

Se tiver interessado em outros problemas relacionados, falar com a monitoria.

Backtracking (com branch & bound)

1. Achar todas as configurações em um tabuleiro de xadrez N x N que tenha um número máximo de rainhas posicionadas de forma que não se ataquem.

2. Achar todas as configurações possíveis em um tabuleiro N x N que tenha um número mínimo de damas que ameacem todas as posições do tabuleiro.

3. Achar uma k (com k > 3) coloração (ou a impossibilidade) em um grafo não direcionado e conexo G.

4. Considere a restrição de nenhum vértice com cor preta estar vizinho de outro com cor preta. Achar uma coloração (preto e branco) de forma que tenhamos o maior número de vértices com cores pretas.