Lista de Exercícios

Exercícios organizados por tópico. Use o menu lateral para navegar entre os tópicos.

Prova 1

Emparelhamento Estável

Implemente o algoritmo de Gale-Shapley na sua linguagem de programação de preferência. Verifique se ele está correto e se a pior execução não demanda mais do que \(n^2\) propostas.
Resolva os “Solved Exercise 1” e “Solved Exercise 2” disponíveis no final do Capítulo 1 do livro Algorithm Design (Kleinberg, Tardos). Depois leia a solução dos autores do livro e verifique na prática através dos cenários “Categorias boas e ruins” e “Pares proibidos” na visualização.
Considere as tabelas de preferências abaixo para um grupo de alunos e empresas:

Preferências dos Alunos:

Alunos 1ª opção 2ª opção 3ª opção 4ª opção

A Z Y X W

B X Y W Z

C Z W X Y

D W X Y Z

Preferências das Empresas:

Empresas 1ª opção 2ª opção 3ª opção 4ª opção

X D A C B

Y C B A D

Z D C A B

W B D C A

Use o Algoritmo Gale-Shapley para encontrar dois emparelhamentos estáveis entre empresas e alunos considerando estas tabelas (um em que os alunos propõem e outro em que as empresas propõem).
Decida se a seguinte afirmação é falsa ou verdadeira:

Dado qualquer instância do problema do emparelhamento estável é possível determinar se a instância possui solução única (um único emparelhamento estável é possível) com um algoritmo polinomial.

Se a afirmação for falsa, forneça o esboço de uma prova. Se a afirmação for verdadeira, forneça um algoritmo polinomial que determina se a instância tem solução única e explique por que o algoritmo funciona.

Alunos	1ª opção	2ª opção	3ª opção	4ª opção
A	Z	Y	X	W
B	X	Y	W	Z
C	Z	W	X	Y
D	W	X	Y	Z

Empresas	1ª opção	2ª opção	3ª opção	4ª opção
X	D	A	C	B
Y	C	B	A	D
Z	D	C	A	B
W	B	D	C	A

Correção de Algoritmos e Invariantes

Prove que o Algoritmo 1 (Ordenação por Seleção) resolve o problema de ordenação usando o princípio da invariante.
- Entrada: Uma sequência de \(k\) números \(\langle a_1, a_2, \dots, a_k \rangle\).
- Objetivo: Encontrar a permutação \(\langle a_1', a_2', \dots, a_k' \rangle\) tal que \(a_1' \leq a_2' \leq \dots \leq a_k'\).
```
Entrada: Vetor A de tamanho k
para i = 1 até A.length - 1 faça:
    menor = i
    para j = i + 1 até A.length faça:
        se A[j] < A[menor] então:
            menor = j
    troca(A[menor], A[i])
retorne A
```

Considere a seguinte rotina em notação C-like, com indexação de vetor iniciada em 0:

// Entrada: vetor v de tamanho N (>= 1)
// contendo somente inteiros maiores ou iguais a zero
// Saída: variável x
x = 0;
i = 0;
while (i < N) {
    if (v[i] > x) {
        x = v[i];
    }
    i++;
}

Descreva uma invariante do laço while que nos permita concluir, ao final da execução, que \(x\) contém o maior valor presente no vetor \(v\).

Análise Assintótica

Demonstre ou refute usando as definições formais:
1. \(3n^5 = \Theta(n^4)\)?
2. \(42n^2 + 666n + 4 = O(n^2)\)?
3. \(2^{n+1} = O(2^n)\)?
4. \(2^{2n} = O(2^n)\)?
5. \(f(n) = \mathcal{O}(g(n))\) implica \(g(n) = \mathcal{O}(f(n))\)?
6. \(f(n) = \mathcal{O}(g(n))\) implica \(g(n) = \Omega(f(n))\)?
Mostre que, para quaisquer constantes reais \(a\) e \(b\), sendo \(b > 0\):

\[(n+a)^b = \Theta(n^b)\]
Dada a seguinte lista de funções, ordene-as em ordem ascendente de crescimento assintótico. Isto é, se \(f(n)\) ocorre antes de \(g(n)\) na lista, então \(f(n) = O(g(n))\):
1. \(f_1(n) = n^{2.5}\)
2. \(f_2(n) = \sqrt{2n}\)
3. \(f_3(n) = n + 10\)
4. \(f_4(n) = 10^n\)
5. \(f_5(n) = 100^n\)
6. \(f_6(n) = n^2 \log n\)

Apresente a ordem de crescimento assintótica do custo computacional (como função de \(N\)) dos seguintes trechos de código (em notação C-like). Tente definir a ordem mais justa utilizando notação \(O\) (limitante superior).

int sum = 0;
for (int n = N; n > 0; n = floor(n/2))
    for (int i = 0; i < n; i++)
        sum++;

int sum = 0;
for (int i = 1; i < N; i = 2*i)
    for (int j = 0; j < i; j++)
        sum++;

int sum = 0;
for (int i = 1; i < N; i = 2*i)
    for (int j = 0; j < N; j++)
        sum++;

Considere \(v\) como sendo um vetor ordenado de tamanho \(N\). Desenvolva um algoritmo que determine se \(x\) está ou não em \(v\) que, garantidamente, possua custo assintótico estritamente menor que \(O(N)\); isto é, \(o(N)\) (ó pequeno).

Teoria dos Grafos e Algoritmos

Seja \(G = (V, E)\) um grafo simples. Suponha que ele esteja representado por lista de adjacências: um vetor de nodos, onde cada nodo \(n\) aponta para uma lista das arestas que partem de \(n\) (não havendo uma lista específica de arestas que chegam em \(n\)). Dado \(G\) e um vértice \(v\), quantas operações são necessárias para identificar as arestas que chegam em \(v\)?
1. \(\Theta(1)\)
2. \(\Theta(\text{deg}(v))\)
3. \(\Theta(|V|)\)
4. \(\Theta(|V|+|E|)\)
5. \(\Theta(|E|)\)
Seja \(G = (V, E)\) um dígrafo. Suponha que ele esteja representado por lista de adjacências: um vetor de nodos, onde cada nodo \(n\) aponta para uma lista das arestas que partem de \(n\) (não havendo uma lista específica de arestas que chegam em \(n\)). Dado \(G\) e um vértice \(v\), quantas operações são necessárias para identificar as arestas que chegam em \(v\)?
1. \(\Theta(1)\)
2. \(\Theta(\text{deg}(v))\)
3. \(\Theta(|V|)\)
4. \(\Theta(|V|+|E|)\)
5. \(\Theta(|E|)\)
Considere um grafo simples \(G\) com \(n \ge 2\) vértices. Fixe um nodo \(v\), e considere a execução do algoritmo BFS de cálculo de distância em níveis a partir de \(v\). Considerando todos os formatos que \(G\) possa ter, quais são os possíveis números mínimo e máximo de níveis, respectivamente?
1. \(1\) e \(n-1\)
2. \(2\) e \(n-1\)
3. \(1\) e \(n\)
4. \(2\) e \(n\)
5. \(2\) e \(\lfloor \frac{n}{2} \rfloor\)
Considere um grafo simples \(G\) com \(n\) vértices e \(m\) arestas. Quais são os números mínimo e máximo, respectivamente, de componentes conexos que o grafo pode ter?
1. \(1\) e \(n-1\)
2. \(1\) e \(n\)
3. \(1\) e \(\max(m,n)\)
4. \(2\) e \(\max(m,n)\)
5. \(\max(1, n-m)\) e \(n-k+1\), onde \(k\) é o menor inteiro tal que \(\binom{k}{2} \ge m\) (e, se \(m=0\), o máximo é \(n\))
Considere o dígrafo abaixo: quantos ordenamentos topológicos distintos ele possui?

\(0\)
\(1\)
\(2\)
\(3\)
\(4\)

Considere o dígrafo abaixo: quantos componentes fortemente conexos ele possui?

\(0\)
\(1\)
\(2\)
\(3\)
\(4\)

Se você adicionar um novo arco direcionado a um dígrafo, o número de componentes conexos… (escolha todas as opções que se aplicam). Responda considerando componentes fortemente conexos e também considerando componentes fracamente conexos.
1. pode ou não permanecer o mesmo (dependendo de \(G\) e da aresta em questão)
2. pode ser reduzido em exatamente 1 unidade
3. pode aumentar
4. pode ser reduzido em mais de 1 unidade
Se rodarmos o algoritmo BFS básico para simplesmente imprimir os nodos alcançáveis a partir de um dado vértice \(v\) de um grafo simples \(G\), mas utilizarmos a matriz de adjacência para representar \(G\) (ao invés de listas), como fica a complexidade assintótica de BFS (\(m\) = número de arestas, \(n\) = número de nodos)?
1. \(\Theta(m+n)\)
2. \(\Theta(m+n\log n)\)
3. \(\Theta(n^2)\)
4. \(\Theta(m \times n)\)
5. \(\Theta(m)\)
Considere o algoritmo de Kahn para ordenamento topológico (baseado na identificação dos vértices de grau de entrada 0). Seria possível partir das ideias dele para projetar um algoritmo que identifique todos os nós que não fazem parte de nenhum ciclo do grafo? Se sim, descreva o algoritmo e analise seu custo computacional (assintoticamente). Se não for possível, justifique.
Seja \(G=(V,E)\) um grafo conectado não-direcionado sem custos. Seja \(d(u,v)\) o comprimento do caminho mais curto entre \(u\in V\) e \(v\in V\). O diâmetro de \(G\) é o maior caminho mais curto entre quaisquer dois vértices, \(\max_{u,v \in V} d(u,v)\). Apresente um algoritmo que retorna o diâmetro do grafo. O tempo de execução de seu algoritmo deve ser \(\mathcal{O}(n^3)\) para um grafo com \(n\) vértices.

Prova 2

Em breve.