E04xxb

Prévia do material em texto

SIN110 Algoritmos e Grafos exercícios E04 Proj Induc/Div e Conq/Prog Din
1) Dados um vetor ordenado A de n números reais, n ≥ 1, e um número real x, determine se existem A[i] e
A[j], 1 ≤ i, j ≤ n, tais que x = A[i] + A[j]. Para solução, projete um algoritmo por indução de complexidade
O(n). Escreva a relação de recorrência T(n) para seu algoritmo e prove que o resultado desta recorrência é
de fato O(n).
2) Num conjunto S de n pessoas, uma “celebridade” é uma pessoa conhecida por quase todas as pessoas
de S, mas não conhece ninguém (incluindo a si própria...). Isso implica que pode existir somente uma cele -
bridade em S. (Note-se que “celebridades” são pessoas de difícil convívio) Problema: desenvolver um al-
goritmo por indução, de complexidade O(n), que determine se existe uma celebridade em S.
3) Considerando que o vetor A com n números reais do exercício 1, não está necessariamente ordenado. E
dado um número real x, queremos determinar se existem A[j], 1 ≤ i, j ≤ n, tais que x = A[i] + A[j]. Na
solução, desenvolva um algoritmo de complexidade O(nlgn). Escreva a relação de recorrência T(n) para
seu algoritmo e prove que o resultado desta recorrência é de fato O(nlgn).
4) Em um vetor A[1..∞], de “tamanho infinito”, as primeiras n células contem números inteiros ordenados de
forma crescente e o restante das células está preenchido com ∞. Projete um algoritmo que recebe o vetor A
e uma chave x para pesquisar e devolve a posição de x em tempo proporcional a O(lgn). Prove que
funciona corretamente e consome o tempo proposto.
Obs.: você não tem a informação do valor de n nos dados de entrada.
5) Observe o algoritmo Mergesort aplicado a um vetor de 16 elementos, desenhando a árvore de recursão
do processamento. Por que a técnica de programação dinâmica não é capaz de acelerar o algoritmo?
6) Sabe-se que, para m > 1 e n > 1:
Considere as duas maneiras de implementar uma função que calcula, dados m e n, o valor de (mn) :
a) Qual é a complexidade de cada uma das funções? Justifique sua resposta.
b) Qual é a mais eficiente? Por quê?