Aula de Hoje

[Luís Theodoro Oliveira Camargo]

Pessoal, não pude ir a aula de hoje por causa dessa bendita greve :(. Por favor alguém poderia me falar o que o professor passou na aula hoje e se ele corrigiu a prova, sei que é muito trabalho, mas queria poder discutir a resolução dos exercícios da prova se alguém se habilitar a transcrever a resolução :).

Obrigado

--
Luís Theodoro Oliveira Camargo

Mestrando em Ciência da Computação pela UNICAMP

Curriculo Lattes: http://buscatextual.cnpq.br/buscatextual/visualizacv.jsp?id=K4249827H6

Skype: theodorocamargo

[Luís Theodoro Oliveira Camargo]

[Pedro Mesquita Moura]

Opa, o professor deu a aula inicial de grafos e apresentou os conceitos e tipos de grafos (caminho, ciclo, 
grafo completo, grafo conexo). Acredito que lendo os slides não tenha problemas.

O professor também passou a correção da prova, e discutimos os resultados.

--
Atenciosamente,
Pedro Mesquita Moura

[Thiago S. A.]

Eu também não pude ir na aula hoje.
O que ele falou sobre a questão 5?

[Pedro Mesquita Moura]

Ele disse que a solução é com o uso de um algoritmo com medianas, mas ele concordou que a questão ficou meio confusa, e disse que vai ser mais generoso na correção.

Em 17 de maio de 2012 12:32, Thiago S. A. <thiag...@gmail.com> escreveu:

Eu também não pude ir na aula hoje.
O que ele falou sobre a questão 5?

[Thiago S. A.]

Ele disse qual seria a complexidade para a questão 6?

[Thiago Godoi]

n lg n

Em 17 de maio de 2012 12:58, Thiago S. A. <thiag...@gmail.com> escreveu:

Ele disse qual seria a complexidade para a questão 6?

--
Thiago Anzolin de Godoi
(11) 7398-3522
(19) 9325-0457

 

[Pedro Mesquita Moura]

E todas as questões valerão dois pontos cada.

[Jhonatan Raphael]

O(n lg n) na 6? :D

--

Att.

Jhonatan Ríchard Raphael

Bacharel em Ciência da Computação - UEMS
Mestrando em Ciência da Computação - UNICAMP

[Luís Theodoro Oliveira Camargo]

Eu não fiz a analise na 6, mas acho coerente a complexidade ser O(n log n)

[Thiago Godoi]

O pior caso é quando o vetor possui (lg n) -1 números que aparecem apenas uma vez, e 1 que se repete no resto do vetor. Além disso as primeiras lg n iterações do quicksort pega os números que aparecem apenas uma vez como pivo.

Dessa forma cada iteração do partition leva O(n), e como são no máximo lg n números distintos, existirão no máximo lg n chamadas recursivas. Assim :

O(n) * O(lg n) = O(n lg n)