Programação
0) Apresentação, Revisão e Introdução
Período alvo: 24/08 a 02/09
Objetivo: nesse módulo, a disciplina será apresentada, incluindo sua motivação, formato e avaliação. A seguir será feita uma breve revisão de tópicos relacionados a programação estruturada avançada incluindo principalmente: recursão, gerenciamento de memória principal e secundária, arranjos e registros.
===========================================Bem vindos e bem vindas à ICC2!
Essa disciplina será oferecida à distância, então vai exigir uma atenção extra de todas as partes: professores, assistentes de ensino e também alunos e alunas.
Como todos teremos maior demanda, a leitura (possivelmente seguida de re-leitura) atenta, será fundamental!
- Programas em C criados durante os vídeos de revisão 1 a 4: structs, arrays, alocação dinâmica, arquivos e recursão
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
1) Eficiência de algoritmos com busca e ordenação
Período alvo: 03/09 a 01/10
Objetivo: apresentar métodos de análise de algoritmos e definições de eficiência, utilizando o problema da busca e ordenação como estudo de caso. Estudar funções de eficiência e equações de recorrência
Formato das aulas desse módulo: vídeos interativos gravados com explicação dos conceitos básicos, e aulas ao vivo para realizar exercícios, implementações, e solucionar problemas práticos.
Cronograma tentativo (para aulas ao vivo exceto mencionado contrário):
- 02 a 04/09 - Introdução a análise de algoritmos (apenas aulas gravadas)
- 10/09 - Busca e contagem de operações
- 14/09 - Busca e ordenação com contagem de operações e comparação
- 17/09 - Ordenação com divisão e conquista
- 21/09 - Análise do algoritmo mergesort com equação de recorrência
- 24/09 - Análise comparativa entre algoritmos de ordenação
- SEMCOMPi
- 05/10 - Prática de análise de recorrências e algoritmos
- 08/10 - Avaliaçao do Módulo 1
Introdução a Análise de Algoritmos- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
Busca e contagem de operações
- 10/09 as 10:00 (aula ao vivo, será gravada e disponibilizada) - Busca sequêncial e binária e análise
- 10/09 as 10:00 (aula ao vivo, será gravada e disponibilizada) - Busca sequêncial e binária e análise
- Ver
- Ver
- Ver
- Ver
- Concluir a atividade
- Concluir a atividade
- 14/09 as 10:00 (aula ao vivo, será gravada e disponibilizada) - Ordenação+Busca binária versus Busca sequencial
- 14/09 as 10:00 (aula ao vivo, será gravada e disponibilizada) - Ordenação+Busca binária versus Busca sequencial
- Concluir a atividade
- Concluir a atividade
Ordenação
- Concluir a atividade
- Ver
- 17/09 as 09:00 (aula ao vivo, será gravada e disponibilizada) - Métodos de ordenação
- 05/10 as 09:00 (aula ao vivo, disponibilizada/gravada) - Comparando funções de eficiência
- 05/10 as 09:00 (aula ao vivo, disponibilizada/gravada) - Comparando funções de eficiência
- Avaliação do módulo, 8/10: início
- Avaliação do módulo, 8/10: início
- Ver Fazer um envio
A avaliação tem 2 partes, começando no run.codes com um algoritmo otimizado a submeter, e finalizando aqui, com a entrega da análise de dois algoritmos em formato arquivo, conforme PDF disponibilizado no run.codes.
Você deverá fazer a avaliação de acordo com a letra do seu primeiro nome: A-G, H-L, M-Z
O algoritmo otimizado não precisa ter função de eficiência numa outra classe (ex. abaixar de linear para logaritmo). Caso consiga, ótimo, mas nem sempre isso é possível. Faça seu melhor para que a função de eficiência contenha menos operações.
Para a entrega da contagem de operações, pode ser uma foto de uma folha ou a solução escaneada/digitalizada. Por favor, escreva de forma legível, use caneta com cor escura e boa iluminação - não será corrigido se eu não conseguir ler.
O envio dos arquivos em ambas as plataformas deve ter conteúdo devidamente identificado com seu nome (com número USP e nome nos comentários do código e na folha/material referente à análise dos algoritmos entregue aqui).
- 02 a 04/09 - Introdução a análise de algoritmos (apenas aulas gravadas)
2) Análise de algoritmos com métodos de ordenação baseados em comparação
Período alvo: 13/10 a 09/11
- 15/10 - Notação assintótica
- 19/10 - Análise de algoritmos: da contagem à analise de complexidade (ao vivo)
- 22/10 - Quicksort parte 1
- 26/10 - Quicksort parte 2 (ao vivo)
- 29/10 - Heapsort parte 1
- 05/11 - Heapsort parte 2
- 09/11 - Heapsort parte 3 e análise (ao vivo)
- 12/11 - Limite inferior para algoritmos baseados em comparação
- 16/11 - Avaliação do Módulo 2
- 15/10 as 9h00 - aula ao vivo: Complexidade e notação assintótica
- 19/10 as 10h00 - aula ao vivo: Contagem de operações e complexidade
- Concluir a atividade
- Concluir a atividade
- Ver
- Concluir a atividade
- Ver
- Ver
- Concluir a atividade
* Avaliação do Módulo 2: 16/11 das 10h10 as 11h30
- Ver Receber uma nota
- 15/10 - Notação assintótica
3) Algoritmos de ordenação linear
Cronograma tentativo
- 19/11 - Counting sort com registros e Bucketsort
- 23/11 - Análise e implementação do counting sort e bucket sort (ao vivo)
- 26/11 - Radixsort : análise e implementação
- 30/11 - Radixsort e ideias para melhorar a pesquisa sequencial e binária (ao vivo)
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
23/11 as 10h00 - aula ao vivo: implementação do Counting sort e Bucketsort (assistam os vídeos anteriores!)
- Concluir a atividade
- Concluir a atividade
30/11 as 10h00 - aula ao vivo: comentários sobre Radix sort e ideias para melhorar a busca
- 19/11 - Counting sort com registros e Bucketsort
4) Busca sublinear e Hashing
Cronograma tentativo
- 03/12 - Hashing - introdução e sondagem linear
- 07/12 - Hashing - implementação básica (ao vivo)
- 10/12 - Hashing - sondagem quadrática, hashing duplo e universal
- 11/12 - Avaliaçao do Módulo 3 + 4: das 14h as 15h40
- 17/12 - Substitutiva + Encontro final da disciplina
- Concluir a atividade
- Concluir a atividade
- Concluir a atividade
7/12 as 10h10 - aula ao vivo: hashing com implementação
11/12 das 13h45 as 15h00 - Avaliação módulos 3 + 4 (nos moldes da avaliação 2)
17/12 das 09h00 as 10h15 - Substitutiva: de uma das avaliações (1), (2) ou (3+4)
Essa avaliação substitui a menor nota entre as 3 avaliações já feitas, mesmo que a nova nota seja menor do que a anterior: i.e. sub do mal.
- 03/12 - Hashing - introdução e sondagem linear