MO417 - Prova I1

Criada: 2003-05-03

Data da prova: 2003-04-30. Enunciado: aqui

Soluções e Critérios de Nota:

```
BINARY-SEARCH(A, x)

1  if x < A[1] then
2     return 0
3  if x ≥ A[n] then
4     return n
5  // aqui A[1] ≤ x < A[n]
6  start ← 1
7  end ← n
8  // invariante: A[start] ≤ x < A[end]
9  while start + 1 < end do 
10    middle ← (start + end)/2
11    if A[middle] ≤ x then
12       start ← middle
13    else
14       end ← middle
15 return start
```
O objetivo desta questão era testar o que os alunos apenderam sobre loop invariantes. Infelizmente, vários fizeram recursivo e não deu para atingir este objetivo. Apenas para esclarecer, no caso de um algoritmo recursivo podemos dizer que seu invariante é uma afirmação que é sempre verdadeira no início de cada chamada recursiva.

O critério adotado foi:
- se o algoritmo não funciona em todos os casos, perde 0,5
- se o algoritmo não é O(lg n), perde 0,5
- se o algoritmo ou a a explicação não estão claros, perde 1,0
A recorrência poderia ser resolvida pelo método mestre, o que daria O(n).

O critério adotado foi:
- se usou o mestre mas não citou a condição envolvendo epsilon, perdeu 0,5
- se deu limites corretos, mas não estritos, perdeu 0,5. Por exemplo, quem falou que a solução era Omega(n) e O(n lg n) entrou nesta categoria.
- se só acertou um dos limites (inferior ou superior), ganhou 1,5 caso o limite fosse estrito, e 1,0 caso o limite fosse frouxo. Por exemplo, falar que a solução era O(n lg n) entra neste caso e ganha 1,0 (limite frouxo).
Uma palavra para quem tentou árvore de recursão. É fácil calcular as folhas, que dá O(n) mas somar o tempo gasto em cada nível era mais complicado, infelizmente. Eu fiz em casa mas confesso que tive que usar técnicas de somatório não vistas no curso. É que eu esperava que o pessoal usasse o mestre mesmo.
Solução:

Algoritmo Complexidade média Complexidade Pior Caso

Insertion Sort O(n²) O(n²)

Selection Sort O(n²) O(n²)

Quicksort O(n lg n) O(n²)

Mergesort O(n lg n) O(n lg n)

Heapsort O(n lg n) O(n lg n)

Os pontos foram atribuídos da seguinte forma:
- cada linha da tabela vale 0,5
- a linha que não estiver toda certa não ganha ponto, exceto:
- duas linhas meio certas valem 0,5 também
Uma solução para este problema pode ser obtida com programação dinâmica da seguinte forma. Ordene as atividades por instante de término, em ordem crescente (ou não-decrescente). Defina v[i] = duração total máxima de um subconjunto de atividades compatíveis contendo a_i necessariamente e opcionalmente atividades que terminam antes de a_i.

O vetor v pode ser calculado pela recorrência:
- v[1] = f₁ - s₁
- v[i] = f_i - s_i + máx v[j], onde 1 ≤ j ≤ i-1 e a_j é compatível com a_i.
Após obter todos os v[i], basta tomar o máximo como sendo a resposta final. Isto tudo dá um algoritmo O(n²). Não é o melhor que pode ser feito, há algoritmos O(n lg n).

Os pontos foram atribuídos da seguinte forma:
- descrição ou tentativa de descrição de um método: 0,5
- clareza da descrição: 1,0
- correção do algoritmo: 0,5
- complexidade polinomial: 0,5
É claro que a correção e a complexidade só podem ser determinadas caso o algoritmo esteja claramente descrito, daí a importância da clareza na avaliação. Em alguns casos, embora a descrição não estivesse totalmente clara, o estudante ganhou pontos referentes a correção e/ou complexidade se a descrição fosse suficientemente clara para permitir o jugamento destes quesitos.

Algoritmo	Complexidade média	Complexidade Pior Caso
Insertion Sort	O(n²)	O(n²)
Selection Sort	O(n²)	O(n²)
Quicksort	O(n lg n)	O(n²)
Mergesort	O(n lg n)	O(n lg n)
Heapsort	O(n lg n)	O(n lg n)