Lista de Exercícios

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

Prova 1

Além dos exercícios abaixo, também é sugerido realizar os exercícios adicionais do Prof. Frederico Messa: Lista 1 (PDF).

Emparelhamento Estável

  1. 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.

  2. 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.

  3. 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).

  4. 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.

Correção de Algoritmos e Invariantes

  1. 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

  2. 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

  1. 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))\)?

  2. Mostre que, para quaisquer constantes reais \(a\) e \(b\), sendo \(b > 0\):

    \[(n+a)^b = \Theta(n^b)\]

  3. 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\)

  4. 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++;

  5. 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).

  6. Para cada um dos itens abaixo, use a ferramenta GeoGebra para encontrar valores de \(c\) e \(n_0\): https://www.geogebra.org/classic/vbuhdgxu

    1. \((n+1)^5 = O(n^5)\)
    2. \(2^{(n-1)} = \Omega(2^n)\)
    3. \(7n^2 = \Omega(n \log n)\)
    4. \(12n^2 + 6n + 4 = \Theta(n^2)\)

Teoria dos Grafos e Algoritmos

  1. 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|)\)

  2. 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|)\)

  3. 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\)

  4. 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\))

  5. Considere o dígrafo abaixo: quantos ordenamentos topológicos distintos ele possui?

G A A B B A->B C C A->C D D B->D E E C->E E->D

  1. \(0\)
  2. \(1\)
  3. \(2\)
  4. \(3\)
  5. \(4\)
  1. Considere o dígrafo abaixo: quantos componentes fortemente conexos ele possui?

G A A B B A->B C C A->C D D B->D E E B->E C->B C->E F F F->C E->D G G E->G G->F

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

  1. 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

  2. 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)\)

  3. 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.

  4. 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

Escalonamento e Particionamento de Intervalos

  1. Considere a seguinte tabela de tarefas, com tempo de início e tempo de fim determinados pela tabela abaixo.

    Tarefa Início Fim
    \(t_1\) 0 2
    \(t_2\) 1 4
    \(t_3\) 2 4
    \(t_4\) 3 5
    \(t_5\) 4 6
    \(t_6\) 4 8
    \(t_7\) 5 6
    \(t_8\) 6 7
    1. Considere que exista uma única máquina capaz de processar uma tarefa por vez (considere que se uma tarefa termina no tempo \(t\) e outra inicia no mesmo tempo \(t\), ambas podem ser realizadas). Qual o número máximo de tarefas que podem ser realizadas nessa única máquina (sem conflitos)?
    2. Considere que será possível alocar mais máquinas para a realização das tarefas acima. Qual o menor número de máquinas necessárias para realizar todas as tarefas acima descritas? Apresente a alocação que usa esse número mínimo.

Caminhos Mínimos

  1. Considere um dígrafo \(G\) com pesos nas arestas. Assuma que os pesos são todos distintos e não-negativos. Seja \(s\) um vértice inicial e \(t\) um vértice final, e assuma que \(G\) possui ao menos um caminho entre \(s\) e \(t\). Determine V (verdadeiro) ou F (falso) para cada uma das seguintes afirmações.

    • ( ) O caminho de menor custo entre \(s\) e \(t\) pode ter até \(n-1\) arestas, sendo \(n\) o número de vértices.
    • ( ) Há um caminho entre \(s\) e \(t\) sem vértices repetidos (isto é, sem loops).
    • ( ) O caminho de menor custo entre \(s\) e \(t\) precisa necessariamente incluir a aresta de menor custo de \(G\).
    • ( ) O caminho de menor custo entre \(s\) e \(t\) precisa necessariamente excluir a aresta de maior custo de \(G\).

  2. Considere um grafo direcionado \(G\) com comprimentos de aresta não negativos e dois vértices distintos, \(s\) e \(t\). A letra \(P\) denota o caminho mais curto de \(s\) para \(t\). Se adicionarmos 10 ao comprimento de cada aresta de \(G\), então: (determine V ou F)

    • ( ) \(P\) definitivamente permanece sendo um caminho mais curto de \(s\) para \(t\).
    • ( ) \(P\) definitivamente não permanece sendo um caminho mais curto de \(s\) para \(t\).
    • ( ) \(P\) pode ou não permanecer sendo um caminho mais curto de \(s\) para \(t\) (dependendo do grafo).
    • ( ) Se \(P\) tiver apenas uma aresta, então \(P\) definitivamente permanece sendo um caminho mais curto de \(s\) para \(t\).

  3. Considere um grafo direcionado \(G\) e um vértice inicial \(s\). Suponha que \(G\) tenha alguns comprimentos de aresta negativos, mas nenhum ciclo negativo, o que significa que \(G\) não tem um ciclo direcionado no qual a soma dos seus comprimentos de aresta seja negativa. Suponha que você execute o algoritmo de Dijkstra com essa entrada. Quais das seguintes afirmações são verdadeiras? (Determine V ou F)

    • ( ) O algoritmo de Dijkstra pode entrar em loop infinito.
    • ( ) É impossível executar o algoritmo de Dijkstra em um grafo com comprimentos de aresta negativos.
    • ( ) O algoritmo de Dijkstra sempre para, mas em alguns casos as distâncias do caminho mais curto que ele calcula não estarão todas corretas.
    • ( ) O algoritmo de Dijkstra sempre para e, em alguns casos, as distâncias do caminho mais curto que ele calcula estarão todas corretas.

Heaps e Filas de Prioridade

  1. Qual dos seguintes padrões em um programa de computador sugere que uma estrutura de dados heap poderia proporcionar um ganho de velocidade significativo? (Marque todas as opções aplicáveis.)

    1. Buscas repetidas.
    2. Cálculos mínimos repetidos.
    3. Cálculos máximos repetidos.
    4. Nenhuma das outras opções.

  2. Suponha que você implemente a funcionalidade de uma fila de prioridade (ou seja, Insert e ExtractMin) usando um array ordenado do menor para o maior. Qual é o tempo de execução no pior caso de Insert e ExtractMin, respectivamente? Considere que você tem um array grande o suficiente para acomodar todas as suas inserções.

    • ( ) \(\Theta(1)\) e \(\Theta(n)\)
    • ( ) \(\Theta(n)\) e \(\Theta(1)\)
    • ( ) \(\Theta(\log n)\) e \(\Theta(1)\)
    • ( ) \(\Theta(n)\) e \(\Theta(n)\)

  3. Suponha que você implemente a funcionalidade de uma fila de prioridade (isto é, Insert e ExtractMin) usando um array não ordenado. Qual é o tempo de execução no pior caso de Insert e ExtractMin, respectivamente? Suponha que você tenha um array grande o suficiente para acomodar todas as suas inserções.

    • ( ) \(\Theta(1)\) e \(\Theta(n)\)
    • ( ) \(\Theta(n)\) e \(\Theta(1)\)
    • ( ) \(\Theta(1)\) e \(\Theta(\log n)\)
    • ( ) \(\Theta(n)\) e \(\Theta(n)\)

Códigos de Huffman

  1. Considere as seguintes frequências (normalizadas) de símbolos para um alfabeto de cinco símbolos:

    Símbolo Frequência
    A 0,32
    B 0,25
    C 0,2
    D 0,18
    E 0,05

    Qual é o comprimento médio de codificação de um código ótimo livre de prefixo?

    1. 2,23
    2. 2,4
    3. 3
    4. 3,45

  2. Qual é o número máximo de bits que o algoritmo guloso de Huffman pode usar para codificar um único símbolo? (Como de costume, \(n\) denota o tamanho do alfabeto.)

    1. \(\log_2 n\)
    2. \(\ln n\)
    3. \(n-1\)
    4. \(n\)

  3. Quais das seguintes afirmações sobre o algoritmo guloso para a construção do código de Huffman são verdadeiras? Suponha que as frequências dos símbolos somam 1. Determine V ou F:

    • ( ) Uma letra com frequência de pelo menos 0,4 nunca será codificada com dois ou mais bits.
    • ( ) Uma letra com frequência de pelo menos 0,5 nunca será codificada com dois ou mais bits.
    • ( ) Se todas as frequências dos símbolos forem menores que 0,33, todos os símbolos serão codificados com pelo menos dois bits.
    • ( ) Se todas as frequências dos símbolos forem menores que 0,5, todos os símbolos serão codificados com pelo menos dois bits.

Propriedades de Grafos

  1. Considere o grafo \(G_1\) descrito pelo seguinte diagrama:

G1 a a b b a--b f f a--f c c b--c d d b--d e e c--e c--f d--e d--f

Complete as seguintes afirmações de forma a torná-las corretas, ou atribua valor verdade (V ou F) às afirmações completas:

  • O número de componentes conexos de \(G_1\) é

    1. 1
    2. 2
    3. 3
    4. 4

  • O grau mínimo e o grau máximo de \(G_1\) são, respectivamente,

    1. 1 e 3
    2. 1 e 4
    3. 2 e 3
    4. 2 e 4

  • O grafo \(G_1\) é uma árvore.

    1. verdadeiro
    2. falso

  • O grafo \(G_1\) é bipartido.

    1. verdadeiro
    2. falso

  • A respeito de existência de circuito/trilha euleriano(a), temos que \(G_1\) é

    1. euleriano
    2. não-euleriano mas semi-euleriano
    3. nem euleriano nem semi-euleriano

  • A respeito de existência de ciclo/caminho hamiltoniano, temos que \(G_1\) é

    1. hamiltoniano
    2. não-hamiltoniano mas semi-hamiltoniano
    3. nem hamiltoniano nem semi-hamiltoniano

  • A respeito de planaridade, temos que \(G_1\) é

    1. planar
    2. não-planar
  1. Considere o grafo \(G_2\) descrito pelo seguinte diagrama:

G2 d d e e d--e f f d--f a a b b a--b c c b--c e--f g g e--g h h e--h f--g f--h g--h

Complete as seguintes afirmações de forma a torná-las corretas, ou atribua valor verdade (V ou F) às afirmações completas:

  • O número de componentes conexos de \(G_2\) é

    1. 1
    2. 2
    3. 3
    4. 4

  • O grau mínimo e o grau máximo de \(G_2\) são, respectivamente,

    1. 1 e 3
    2. 1 e 4
    3. 2 e 3
    4. 2 e 4

  • O grafo \(G_2\) é uma árvore.

    1. verdadeiro
    2. falso

  • O grafo \(G_2\) é bipartido.

    1. verdadeiro
    2. falso

  • A respeito de existência de circuito/trilha euleriano(a), temos que \(G_2\) é

    1. euleriano
    2. não-euleriano mas semi-euleriano
    3. nem euleriano nem semi-euleriano

  • A respeito de existência de ciclo/caminho hamiltoniano, temos que \(G_2\) é

    1. hamiltoniano
    2. não-hamiltoniano mas semi-hamiltoniano
    3. nem hamiltoniano nem semi-hamiltoniano

  • A respeito de planaridade, temos que \(G_2\) é

    1. planar
    2. não-planar

Árvores e Árvores Geradoras Mínimas

  1. Qual é a única árvore identificada pelo código de Prüfer \(1111\)? Assuma que o primeiro vértice é o vértice 1, e que os demais vértices são os números naturais a partir de 1 até o único número de vértices possível quando considerando o código dado.

  2. Assuma que \(G\) é um grafo simples com pesos não-negativos nas arestas. Utilizando um algoritmo clássico (Prim ou Kruskal), você calculou uma árvore geradora mínima para \(G\), a qual vamos chamar \(T\). Considere agora que \(G\) foi modificado pela adição de uma nova aresta \(e\) entre os nodos \(x\) e \(y\) (até então não-adjacentes) com peso \(w\). É possível ajustarmos \(T\) para gerar de forma eficiente a árvore geradora mínima \(T'\) de \(G'\), ou é necessário rodarmos novamente um algoritmo clássico do zero para \(G'\)? Desenvolva essa análise.

Coloração de Grafos

  1. Determine V (verdadeiro) ou F (falso) para cada uma das seguintes afirmações sobre coloração de grafos.

    • ( ) Todo grafo bipartido tem número cromático no máximo 2.
    • ( ) Todo grafo com número cromático 2 é bipartido.
    • ( ) O número cromático de um grafo qualquer é sempre menor ou igual ao seu grau máximo \(\Delta\).
    • ( ) Se \(G\) é um grafo planar, então seu número cromático é no máximo 4.
    • ( ) Se \(G\) possui um clique de tamanho \(k\) (isto é, um subgrafo completo \(K_k\)), então o número cromático de \(G\) é pelo menos \(k\).

  2. Considere o grafo \(H\) com vértices \(\{1, 2, 3, 4, 5\}\) e arestas \(\{1\text{–}2,\ 1\text{–}3,\ 2\text{–}3,\ 2\text{–}4,\ 3\text{–}5,\ 4\text{–}5\}\).

    1. Qual é o número cromático \(\chi(H)\)? Justifique.
    2. Exiba uma coloração ótima de \(H\) (usando \(\chi(H)\) cores), indicando a cor de cada vértice.
    3. O grafo \(H\) é bipartido? Justifique com base no número cromático encontrado.