Considere o seguinte algoritmo que recebe um vetor A[p · · ·r] com p > 0, r > 0, e p ≤ r e de números inteiros:

SOMA(A, p,r)

1: if p < r then

2: q ← ⌊ p+r/ 2⌋

3: x ← SOMA(A, p, q)

4: y ← SOMA(A, q + 1,r)

5:     return x + y

6: else

7:     return A[p]

O algoritmo promete devolver a soma dos elementos do vetor, ele faz o que promete? Faça uma pequena simulação para mostrar o passo-a-passo de como ele funciona. Calcule em termos da notação O o tempo desse algoritmo, mas procure dar a resposta mais justa possível. Justifique a sua resposta.

Escreva um algoritmo que recebe um vetor decrescente A[1..n] de números inteiros e devolve a diferença A[j] − A[i] tal que i e j sejam escolhidos de tal forma a maximizar A[j] − A[i] para 1 ≤ i < j ≤ n. Descreva um algoritmo eficiente para esta tarefa. Qual a complexidade do teu algoritmo?

Indique com V (verdadeiro) ou F (falso) cada uma das afirmativas abaixo. É obrigatório justificar a resposta.

(a) O algoritmo de “quicksort” pode ser implementado para tentar na prática evitar o pior caso.

(b) O merge sort sempre consome tempo Θ(nlgn)

(c) A busca binária não precisa de um vetor ordenado para funcionar.

(d) O filho esquerdo de um nó k em um heap é dado por ⌊k/2⌋.