Tarefas

Notas das tarefas

Cada tarefa vale um certo número de pontos. Um aluno que tenha acumulado Y pontos terá média de tarefas 100 Y ÷ T, onde T é um pouco menos que a soma dos valores de todas as tarefas.
Cada tarefa consiste em um ou mais exercícios.

Entrega das tarefas

Entregue sua tarefa antes do início da aula.
Não entregue tarefas por email.

Apresentação das tarefas

As tarefas são estritamente individuais (ou seja, não podem ser feitas em grupo). Não haverá tolerância para plágio. (Veja a página sobre plágio preparada pelo professor Arnaldo. Veja também o sítio do Dartmouth College sobre o assunto.)
Se você emprestou ideias de algum livro, de algum colega, ou da Internet deve citar suas fontes de maneira clara, completa e explícita. Faça uma citação clara e precisa (nomes, números de páginas, etc.).
Escreva o enunciado completo de cada exercício antes de resolvê-lo.
Não escreva tudo em letras maiúsculas. Não confunda n com N, por exemplo.
Ao escrever a solução de um exercício, use sentenças completas — com sujeito, verbo, predicado e ponto final.
Evite símbolos lógicos (como ∃, ∀, ⇒, ∴); prefira palavras em português (como existe, para todo, implica, portanto).
Releia e corrija o seu manuscrito antes de considerá-lo pronto.
Escreva suas tarefas com amplas margens (esquerda, direita, acima, abaixo), para que eu tenha onde escrever meus comentários. Deixe várias linhas em branco entre um exercício e outro.
Não escreva dos dois lados da folha de papel.
Antes de entregar uma tarefa, escreva o seu nome, a data, e o número da tarefa no topo da primeira página.
Junte todas as folhas com um grampo no canto superior esquerdo.

Tarefa 1 (em 24/2)

Prove por indução matemática que 2⁰ + 2¹ + … + 2ⁿ = 2ⁿ⁺¹−1
Qual a diferença entre (1,2,3,4) e {1,2,3,4}?
O que significa a expressão log …?
Quanto vale k …?
Escreva um algoritmo recursivo que calcule a soma dos elementos pares de um vetor A[1..n] de números naturais.

Tarefa 2 (para 3/3, vale 4 pontos)

Escreva um algoritmo para o seguinte problema: dado um número x e um vetor crescente A[1..n], encontrar j tal que A[j−1] < x ≤ A[j]. Escreva um algoritmo iterativo e um recursivo. Use a técnica da busca binária em ambos os casos. Prove que cada um dos algoritmos está correto. Estime o consumo de tempo de cada um dos algoritmos.

Tarefa 3 (para 10/3, 5 pontos)

[1 ponto] Prove ou desprove a seguinte conjetura: para todo inteiro positivo n, ⌈lg n⌉ é o menor inteiro k tal que n ≤ 2^k.
[2 pontos] Resolva o problema dos dois algoritmos equivalentes na página de exercícios preliminares do sítio Análise de Algoritmos. Qual dos dois é mais eficiente?
[2 pontos] Seja T a função definida sobre os números naturais pela seguinte recorrência: T(0) = 0 e T(n) = T(⌈(n−1)/2⌉) + 1 para n = 1,2,3,4,… Prove (por indução em n) que T(n) ≤ lg n + 1 para n = 1,2,3,4,…

Tarefa 4 (para 17/3, vale 12 pontos)

[2 pontos] Prove que n = O(2ⁿ). (Use indução.)
[1 ponto] Prove que lg n = O(n).
[1 ponto] Prove que teto(lg n) + 10 = O(lg n).
[4 pontos] Escreva e analise um algoritmo recursivo que calcule piso(lg n).
[1 ponto] Seja f a função definida pela seguinte recorrência: f(1) = 3 e f(n) = f(n/2) + 1 para n = 2¹, 2², 2³, … Mostre que f(n) = lg n + 3 para n = 2⁰, 2¹, 2², 2³, …
[3 pontos] Seja f a função definida pela seguinte recorrência: f(1) = 1 e f(n) = f(n−1) + 2n para todo número natural n ≥ 2. Mostre que f(n) é O(n²). Mostre que f(n) é Ω(n²).

Tarefa 5 (em 7/4)

Prove que 100 lg n + 2n lg n − 10n está em O(n lg n) e também em Ω(n lg n). [Solução]

Tarefa 6 (em 9/4)

Escreva um algoritmo recursivo para o seguinte problema: dados vetores A[1..n] e B[1..n], decidir se existe um índice i tal que A[i] = B[i]. [Solução]

Tarefa 7 (para 14/4, 7 pontos)

[1 ponto] Sejam f' e g' as derivadas das funções f e g respectivamente. Se f'(n) >g'(n) para todo n ≥ 10 podemos concluir que f cresce mais rápido que g e portanto f não é O(g). Discuta essa afirmação.
[3 pontos] O seguinte fragmento de código transforma o vetor A[1..n] em max-heap?

para m ← n decrescendo até 2 faça
Corrige-Subindo (A, m)
[3 pontos] Considere o seguinte problema: decidir se um vetor B[1..k] é uma subsequência de um vetor A[1..n]. Escreva um algoritmo recursivo eficiente para resolver o problema e prove o seu algoritmo está correto.

Tarefa 8 (em 14/4, 3 pontos)

[CLRS 4.2-1] Seja T a função definida assim: T(1) = 1 e T(n) = 3 T(n/2) + n para n = 2¹,2²,2³,… Prove que T(n) é Ω(n^lg 3). Prove que T(n) é O(n^lg 3). (A propósito, lg 3 fica entre 1.5 e 1.6.)

Tarefa Opcional (até 16/5, vale 25 pontos)

Implemente o algoritmo de Karatsuba–Ofman. Implemente o algoritmo usual de multiplicação. Siga de perto o pseudocódigo discutido na aula, mas use base 2¹⁵ em lugar da base 10. (Se a coisa ficar muito complicada, você pode usar base 10000.) Faça testes para comparar a velocidade dos dois algoritmos.
Use linguagem C. Não use C++ nem Java. Use layout padronizado.
É muito provável que não vou gostar das suas primeiras versões e vou sugerir alterações. Por isso, sugiro entregar suas primeiras versões em papel, antes do prazo final. A versão final deve ser entregue ao Moodle. Um resumo dos resultados dos testes deve constar, como comentário, no fim do seu programa C.

Tarefa 9 (para 23/4)

[2 pontos] Seja u o seu número USP e v o número 9898989. Calcule o produto de u por v usando o método de Karatsuba. Aplique apenas um nível de recursão do algoritmo. Use lapis e papel ou uma calculadora eletrônica para fazer as multiplicações intermediárias. Exiba todos os resultados intermediários.
[3 pontos] Seja (s[1],f[1]), … , (s[n],f[n]) uma coleção de intervalos. Suponha que os intervalos são dados em ordem crescente de início. Escreva um algoritmo que devolva uma sdm da coleção e uma cobertura mínima da coleção. O consumo de tempo do seu algoritmo deve estar em O(n). (Sugestão: Faça primeiro uma versão sem cobertura. Depois acrescente o cálculo da cobertura.)
[2 pontos] Dada uma coleção S de intervalos, e um peso numérico w_i > 0 para cada intervalo i, encontrar o peso de uma subcoleção disjunta de S que tenha peso máximo. Escreva um algoritmo de programação dinâmica para o problema.

Tarefa 10 (para 28/4)

[2 pontos] O algoritmo Subset-Sum-Prog-Din preenche a tabela t "por colunas" (a primeira coluna, depois a segunda, etc.). Escreva uma variante do algoritmo que preencha a tabela "por linhas".
[2 pontos] Mostre como um algoritmo para o problema subset-sum generalizado pode ser usado para resolver o nosso problema subset-sum básico.

Tarefa 11 (durante a aula de 28/4)

[1 ponto] Imagine a heurística gulosa óbvia para o problema da mochila booleana. Mostre que a heurística não resolve o problema. Mostre que a heurística não resolve o problema nem mesmo se os objetos forem tomadas em ordem crescente de peso. Idem para ordem decrescente de valor. Idem para ordem decrescente de valor específico (ou seja, valor-dividido-por-peso).
[1 ponto] [Problema do pen drive] Tenho um grande número de arquivos digitais no meu computador. Cada arquivo ocupa um certo número de kilobytes. Quero gravar o maior número possível de arquivos num pen drive com capacidade para W kilobytes. Escreva um algoritmo guloso que resolva esse problema. Mostre que o seu algoritmo está correto.
[1 ponto] Descreva em pseudocódigo um algoritmo de programação dinâmica para o problema da mochila booleana.

Tarefa 12 (durante a aula de 12/5)

[2 pontos] Digamos que tenho um arquivo sobre o alfabeto a, b, c, d, e, f. Cada caractere ocorre exatamente k vezes. (1) Se for necessário representar cada caractere por um número fixo de bits, quantos bits você usaria por caractere? Quantos bits terá o arquivo codificado? (2) Quantos bits terá o arquivo codificado se usarmos um código de Huffman?

Tarefa 13 (para 14/5)

[2 pontos] Calcule o código de Huffman para o alfabeto a, b, . . , h com frequências que são os primeiros números de Fibonacci: f(a) = 1, f(b) = 1, f(c) = 2, f(d) = 3, f(e) = 5, f(f) = 8, f(g) = 13, f(h) = 21. O arquivo original tem 1+1+…+21 = 54 caracteres. Quantos bits tem o arquivo codificado?

Tarefa 14 (para 26/5)

[3 pontos] O alfabeto de um arquivo A tem 256 caracteres. A frequência máxima de um caractere em A é menor que o dobro da frequência mínima. Mostre que a codificação de Huffman para A não é melhor que a codificação usual, que usa 8 bits por caractere.

Tarefa 15 (para 9/6)

[4 pontos] Prove o invariante do processo iterativo que insere e remove numa tabela dinâmica.

Tarefa 16 (durante a aula de 9/6)

Tarefa 17 (para 23/6)

[1 ponto] Mostre que não basta examinar os arcos em ordem crescente de peso para resolver o problema da arborescência maximal de peso mínimo:

[2 pontos] Troque o bloco de linhas 1 a 12 do algoritmo Prim-com-Fila-de-Vértices pelo código abaixo. Mostre que o algoritmo continua correto.

11 o para v crescendo de 1 até n faça
12 oooo chave[v] ← ∞
13 oooo pai[v] ← 0
14 oooo cor[v] ← branco
15 o chave[r] ← 0
16 o pai[r] ← r
10 o Q ← Cria-Fila-Vazia ( )
11 o para v crescendo de 1 até n faça
12 oooo Insere-na-Fila (v, Q)

[2 pontos] Escreva uma versão de Prim-com-Fila-de-Vértices que devolva apenas o peso da arborescência maximal de peso mínimo (e não a arborescência propriamente dita).

[1 ponto] Execute o algoritmo Prim-com-Fila-de-Vértices sobre o digrafo abaixo. (Basta indicar a solução na figura.)

           3         9
       1--------2--------3
       |\       |       /|
      4|  \  5  |6    /  |2
       |    \   |   / 8  |
       |      \ | /      |
       4--------5--------6
       |\    6  |    9
       |  \     |
      6|  7 \   |8
       |      \ |
       7------- 8        9
           8