MAC338  PROVA 1  25/4/2000

Duração da prova: 2 horas

1. [3 pontos] Temos usado a notação O em sala regularmente. Lembre que podemos escrever O(f(n)) no lugar de qualquer função g(n) para a qual existam C > 0 e n_{0} ≥ 1 tais que

|g(n)| ≤ Cf(n) para todo n ≥ n_{0}.

(i) É correto dizer que n log n = O(n^{2})?

(ii) Suponha que deduzimos que a complexidade de tempo de dois algoritmos A e B são, respectivamente, O(n log n) e O(n^{2}), para entradas de tamanho n. É correto dizer que o algoritmo A é pelo menos tão eficiente quanto o algoritmo B para entradas suficientemente grandes? Justifique sua resposta. [Sugestão: cuidado!]

(iii) O que é mais informativo: dizer que a complexidade de tempo de um algoritmo é O(n(log n)^{3}) ou dizer que é O(n^{2})? Justifique sua resposta.

2. [3 pontos] Nesta questão, consideramos dois grafos orientados G_{1} e G_{2}. Fixe dois inteiros k ≥ 2 e n ≥ 1. Ambos G_{1} e G_{2} têm conjunto de vértices V = [k]^{n} = [k] × ⋯ × [k], onde [k] = {1, …, k}. Em G_{1}, temos um arco de x = (x_{1}, …, x_{n}) para y = (y_{1}, …, y_{n}) se (a) x_{i} ≤ y_{i} para todo i e (b) ∑_{i} y_{i} = 1 + ∑_{i} x_{i}, isto é, todas as coordenadas de y são as mesmas de x exceto por uma, que é exatamente um maior que a coordenada correspondente de x. Em G_{2}, temos um arco de x = (x_{1}, …, x_{n}) para y = (y_{1}, …, y_{n}) se (a) x ≠ y e (b) x_{i} ≤ y_{i} para todo i.

(i) Desenhe os grafos G_{1} e G_{2} no caso em que k = 2 e n = 3. Note que estes grafos têm 2^{3} = 8 vértices. Ademais, eles têm 12 arcos e 19 arcos, respectivamente.

(ii) Em geral, mostre que G_{1} tem no máximo nk^{n} arcos e G_{2} tem exatamente

\{\binom{k}{1} + \binom{k}{2}\}^{n} − k^{n} = \binom{k + 1}{2}^{n} − k^{n}  (*)

arcos. [Sugestão: a grosso modo, cada arco (x, y) em G_{2} pode ser codificado como um vetor com n coordenadas, cada coordenada assumindo um dentre k + \binom{k}{2} valores.]

(iii) Mostre que a quantidade em (*) é pelo menos

\frac{1}{3}\binom{k + 1}{2}^{n}.

(iv) Mostre que G_{1} e G_{2} têm o mesmo conjunto de ordenações topológicas.

(v) Suponha que o algoritmo Topological-Sort que estudamos em sala demora N + M unidades de tempo para encontrar uma ordenação topológica de um grafo orientado acíclico com N vértices e M arcos. O que podemos dizer sobre o tempo de execução de Topological-Sort(G_{1}) e Topological-Sort(G_{2})? Suponha agora que k = 2 e n é grande. Como você pode comparar estes dois tempos de execução? Dê um valor de n para o qual um tempo é pelo menos 10 vezes maior que o outro. Faça o mesmo para 1000.

3. [3 pontos] Faça uma tabela 3 × 3 com as linhas e colunas indexadas pelas cores branca, cinza e preta. Na entrada (i, j) desta tabela, indique se é possível acontecer de termos um arco de um vértice de cor i para um vértice de cor j em uma execução de DFS(G) para um grafo orientado G. Responda a mesma pergunta para o caso em que G é um grafo não-orientado. No caso das entradas negativas, justique sua resposta.

4. [3 pontos] Suponha que (u, v) é um arco de um grafo orientado G e que executamos DFS(G). Por simplicidade, suponha que G não tem laços, isto é, arcos da forma (u, u). Mostre que (u, v) é

(i) um arco da floresta de busca ou um arco longitudinal descendente se e só se d[u] < d[v] < f[v] < f[u], (ii) um arco longitudinal ascendente se e só se d[v] < d[u] < f[u] < f[v], e (iii) um arco transversal se e só se d[v] < f[v] < d[u] < f[u].

Ademais, se x e y são vértices quaisquer de G, (iv) o que podemos dizer sobre a paridade de f[x] − d[x]? Justifique.

(v) Podemos ter d[x] < d[y] < f[x] < f[y]? Justifique.