MAC 122 - Princípios de Desenvolvimento de Algoritmos

BCC - Terceira Prova - 7 de novembro de 2000

NOME DO ALUNO :
NUSP :
ASSINATURA:

INSTRUÇÕES

1. Preencha o cabeçalho acima.
2. A prova deve ser resolvida sem consulta a apontamentos, cadernos, livros ou colegas. Você pode perguntar o que desejar ao professor.

DURAÇÃO DA PROVA: 1 hora e 40 minutos

	Nota
Questão 1
Questão 2
Questão 3
Questão 4
TOTAL

B O A P R O V A

1. (valor 3.0 pontos)
   Lembrando que dizemos que uma função $f(n)$ é O$(g(n))$ se existem constantes inteiras positivas $c$ e $n_0$ tais que
   
   $$f(n) \le cg(n), \mbox{ para todo } n \ge n_0$$
   
   
   Mostre que:
   • $2(n+1) \ln (n+1)$ é O$(n\log n)$.
   • $n^3$ não é O$(n^2)$.

2. (valor 3.0 pontos)
   Faça uma função que recebe um vetor $v$ com $n$ inteiros e sem utilizar espaço adicional coloca os números pares no começo do vetor e os números ímpares no fim, devolvendo o índice do primeiros número ímpar, ou $n$ se todos os números do vetor forem pares. Diga qual é a complexidade de sua função, e justifique.

   Dica: Pense no separa do quicksort.

3. (valor 3.0 pontos)
   Faça uma função de complexidade O( $\mathbf{\log n}$) que recebe um vetor $v$ com $n$ inteiros distintos e verifica se existe algum índice $i$ no vetor tal que $v[i] = i$.

   Dica: Pense na busca binária, e note que todos os elementos do vetor são distintos.

4. (valor 1.0 ponto)
   

   Aproveite este última folha para fazer uma crítica à disciplina: aulas, trabalhos, listas, etc.