2021 Q1

CCM-001 - Análise de Algoritmos e Estruturas de Dados (Pós)

Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br

piadinha


🚨 Avisos importantes (fique atento sempre!)

📌 [07/06] Avisos finais:
  1. Corrigi a prova de recuperação. Se você a fez, enviei por email com alguns comentários.
  2. As notas finais estão na planilha na seção de notas.
  3. Se você deseja solicitar revisão de nota, me envie mensagem pelo Discord ou por e-mail indicando qual questão você quer que eu reveja e o motivo de você achar que a minha correção foi errada.
    Peço que isso seja feito até o dia 15/06.
[09/05] Avisos (semi-)finais importantes:
  1. Corrigi a prova 2. Se você a fez, enviei por email com alguns comentários.
  2. As notas finais (pré-rec) estão na planilha na seção de notas.
  3. A prova de recuperação pode ser realizada por qualquer aluno que ficou com conceito D ou F.
    Se você deseja fazê-la, me envie um email dizendo seu nome e O NOME DA DISCIPLINA no título, por favor.
    A PROVA SERÁ ENVIADA APENAS PARA QUEM MANIFESTAR INTERESSE.
  4. Fiz um formulário anônimo de fim de curso com perguntas específicas dessa modalidade à distância.
    Peço que você gaste mais esses minutinhos com a disciplina para me ajudar a melhorar: clique aqui.
  5. Se você deseja solicitar revisão de qualquer nota, me envie mensagem PELO DISCORD indicando qual questão você quer que eu reveja e o motivo de você achar que a minha correção foi errada.
    Prefira fazer isso amanhã (10/05), pois as notas serão lançadas no dia 11/05.
  6. Por fim, estarei disponível pelo Discord para tirar dúvidas sobre a recuperação a qualquer momento do recesso.
[01/mai] Liberei os bônus das listas 1 a 4. Qualquer dúvida, entrar em contato pelo chat do Discord.
[12/abr] Corrigi a prova 1. Se você a fez, enviei por email com alguns comentários. As notas e os critérios estão na planilha na seção de notas.
[12/abr] Disponibilizei uma versão corrigida da lista 5 (houve apenas uma remoção do item (d) da questão 11).
[29/mar] Com a manutenção dos calendários acadêmicos nesse período de antecipação de feriados, o cronograma de aulas e atendimentos está mantido. Veja mais no Discord.
[29/mar] Detalhes da prova 1 substitutiva na seção cronograma.
[25/mar] Atenção! Sobre o informe da reitoria, veja a seção de avisos no Discord.
[08/fev] Disponibilizei a solução de alguns exercícios da lista 1.
[29/jan] O cronograma foi alterado para seguir o calendário de reposições. Com isso, as provas tiveram Duas datas adiadas em uma semana.
[26/jan] Leia a seção sobre 🔥🔥🔥 como será a disciplina 🔥🔥🔥 sem falta!
[26/jan] Apenas para matriculados e alunos especiais: 🔥🔥🔥 grupo no Discord 🔥🔥🔥 e formulário de início de curso para alunos da graduação e para alunos da pós-graduação.
[26/jan] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado na prova (Será que não vai? 🤔).


🙋 Como será a disciplina?

Nosso meio de comunicação principal será o grupo na ferramenta Discord.
Por favor, participe do servidor apenas se você está matriculado na disciplina ou é aluno especial (e falou comigo).
O site sempre será atualizado com avisos, porém comunicados menores e atendimentos serão pelo Discord.

Aliás, o servidor no Discord pode e deve ser utilizado em qualquer horário, para atendimento assíncrono.

As videoaulas com os conteúdos da disciplina já estão disponibilizadas na seção Cronograma.
Os conteúdos foram distribuídos da forma como eles seriam dados em um curso presencial.
É muito importante que você não só veja os vídeos, mas também consiga ler as notas de aula, que foram preparadas com muito carinho ao longo de outras instâncias do curso.
Pequenos erros seguem sendo atualizados constantemente, mas todo o conteúdo dessa disciplina já está disponível.
Particularmente, o conteúdo da Parte I vai te auxiliar muito no começo da disciplina.

Atenção! Três aulas serão dadas de forma síncrona, como pode ser visto no cronograma.
A sua participação é essencial nelas, mas elas serão gravadas e disponibilizadas logo em seguida, para quem não puder participar.

Nos horários previstos das aulas, estarei online pela ferramenta Google Meet:

O link do Google Meet está disponível no servidor do Discord.
Esses horários devem ser usados para tirar dúvidas do conteúdo e também para discutir a solução de exercícios.

Sugestão de organização dos estudos: assista aos vídeos com atenção, sem fazer anotações. Depois, leia os materiais de apoio enquanto faz anotações. Existem mais exemplos nesses materiais e detalhes que podem passar despercebidos nos vídeos.

Idealmente, siga o cronograma: se no dia está previsto o conteúdo ×, então use o atendimento para tirar dúvidas sobre ×, mesmo que você tenha só aquele horário para assistir aos vídeos.
Mesmo que você não consiga seguir esse "comportamento ideal", não deixe de usar os horários de atendimento 🥺🙏!

Como estamos fazendo a disciplina à distância, eu preciso confiar no material que você vai me entregar.
Meu único pedido é: seja o autor das suas atividades.
Isso basicamente significa: não copie solução encontrada na internet ou feita por outra pessoa.
É claro que você pode e deve trocar ideias com os colegas, porque isso realmente ajuda no aprendizado.
Eventualmente, ver soluções já prontas também ajuda, mas apenas se você entendê-las tão bem que possa, depois, responder sozinho o mesmo problema.
Qualquer violação às regras descritas na seção sobre plágio implicará em descarte dos conceitos atribuídos a TODAS as tarefas avaliativas regulares de TODOS os envolvidos, causando assim suas reprovações automáticas com conceito F. Veja detalhes sobre a avaliação na seção Avaliação.

Por fim, o site tem bastante informação, então leia-o com bastante cuidado.
Não sei se já falei, mas as notas de aula estão muito boas 😉, dê uma olhada.
Meu objetivo aqui é que você aprenda o conteúdo dessa disciplina da melhor forma possível.
Por isso, converse comigo sempre.
Qualquer dúvida e feedback são bem vindos, de verdade.
Acho que é isso, boas aulas!

Importante!

Todas as aulas, com e sem participação dos alunos, serão gravadas e disponibilizadas online segundo a Licença Creative Commons Atribuição-Não Comercial 4.0 Internacional (CC-BY-NC).
Todos os participantes do curso dão sua tácita e irrevogável autorização para que suas imagens e falas sejam transmitidas, gravadas e editadas segundo a licença acima pelo docente responsável, sem nenhuma cobrança, para uso em distintos canais de comunicação e peças publicitárias sem fins comerciais.



🧐 Ementa da disciplina

CCM-001 - Análise de Algoritmos e Estruturas de Dados

Objetivos:



🖖 Recomendação

Para facilitar o acompanhamento do curso, é recomendado que você possua:

Dê uma olhada na lista 0 de exercícios e veja se está confortável com aquele conteúdo (ao menos já viu antes).

Preparei esse material de 🔥revisão🔥 que contém tudo que precisamos na disciplina. Também tenho vídeos com definição e exemplos de indução.

Outros materiais de apoio:



📚 Bibliografia e outros materiais

  1. [LM] Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados (o conteúdo dessa disciplina está completo no livro, mas sempre existem atualizações - verifique sempre sua versão).
  2. [CLRS2] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 2nd ed. MIT Press. 2002.
  3. [CLRS3] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.
  4. [R] Vídeo aulas do prof. Tim Roughgarden, de Stanford, em inglês (com legendas): parte 1 e parte 2.
  5. [DPV] Dasgupta, S.; Papadimitriou, C.; Vazirani, U.. Algorithms. Boston: McGraw-Hill. 2008.
  6. [KT] Kleinberg, J.; Tardos, E.. Algorithm design. Pearson/Alison-Wesley. 2006.
  7. Grupo do Whatsapp criado e mantido pelos alunos.


📆 Cronograma

Aula 1 - 1/fev 🎥🎥 LIVE (aula síncrona) 🎥🎥
Aula 2 - 3/fev
  • Introdução à análise de algoritmos. Corretude de algoritmos (iterativos).
  • Vídeos (tempo total = 82min):
  • Quiz.
  • Referências: Cap. 2 e 3 [LM], Cap. 1 e 2 [CLRS2].
Aula 3 - 8/fev
  • Tempo de execução. Notação assintótica.
  • Vídeos (tempo total = 101min):
  • Quiz.
  • Referências: Cap. 4 e 5 [LM], Cap. 3 [CLRS2].
  • Exercícios resolvidos:
  • Material complementar: Vídeos 1.8, 2.1, 2.2, 2.3, 2.4 e 2.5 [R].
Aula 4 - 10/fev
15/fev (Feriado carnaval 🎉)
  • Reposição em 27/04 (terça-feira).
17/fev (Feriado carnaval 🎉)
  • Reposição em 29/04 (terça-feira).
Aula 5 - 22/fev
  • Corretude e tempo de execução em algoritmos recursivos. Recorrências.
  • Vídeos (tempo total = 42min):
  • Quiz.
  • Referências: Cap. 7 e 8 (intro) [LM], Cap. 2.3, 4 (intro) [CLRS2],
  • Material complementar: Vídeos 4.1 [R].
Aula 6 - 24/fev
Aula 7 - 1/mar
  • Solução de recorrências: substituição e iteração.
  • Vídeos (tempo total = 63min)
  • Quiz.
  • Referências: Cap. 8.1 e 8.2 [LM], Cap. 4 [CLRS2].
Aula 8 - 3/mar
  • Solução de recorrências: árvore de recursão e método Mestre.
  • Vídeos (tempo total = 51min)
  • Quiz.
  • Referências: Cap. 8.3 e 8.4 [LM], Cap. 4 [CLRS2].
  • Exercícios resolvidos:
  • Extra: Vídeos 4.1, 4.2, 4.3, 4.4, 4.5, 4.6 [R].
Aula 9 - 8/mar
Aula 10 - 10/mar
Aula 11 - 15/mar
Aula 12 - 17/mar
  • Busca em profundidade. Aplicações das buscas. Busca em digrafos.
  • Vídeos (tempo total = 35min):
  • Quiz.
  • Referências: Seções 24.2, 24.3, 24.4 e 24.5 [LM], Seção 22.3 [CLRS2],
  • Extra: execução DFS.
Aula 13 - 22/mar 🎥🎥 LIVE (aula síncrona) 🎥🎥
  • Checkpoint: revisão e dúvidas para prova.
  • Vídeo (tempo total = 109min):
Aula 14 - 💥💥PROVA 1💥💥 - 24/mar
  • Das 19h do dia 24/mar às 20h do dia 27/mar - Detalhes serão enviados por e-mail
  • Lembre-se de entregar as suas respostas das listas 1 a 4 até as 19h do dia 24/mar.
Aula 15 - 29/mar
  • Introdução a algoritmos gulosos. Escalonamento de tarefas compatíveis. Mochila fracionária.
  • Vídeos (tempo total = 78min):
  • Quiz.
  • Referências: Seções 21.1 e 21.2 [LM].
  • Extra: Vídeo 3 [R]; site prof. Feofiloff.
Aula 16 - 31/mar
Aula 17 - 5/abr
Aula 18 - 7/abr
Aula 19 - 12/abr
Aula 20 - 14/abr
Aula 21 - 19/abr
  • Redução entre problemas.
  • Vídeos (tempo total = 88min):
  • Quiz.
  • Referências: Cap. 28 [LM], Cap. 34 [CLRS2].
21/abr (Feriado Tiradentes 🦷)
  • Reposição em 7/05.
Aula 22 - 27/abr (na terça-feira às 19h, por ser reposição)
Aula 23 - 29/abr 🎥🎥 LIVE (aula síncrona) 🎥🎥 (na quinta-feira às 21h, por ser reposição)
  • Checkpoint: revisão e dúvidas para prova.
  • Vídeo (tempo total = 111min):
💥💥PROVA 1 SUB💥💥 - 30/abr
  • Das 20h do dia 30/abr às 21h do dia 3/mai - Detalhes serão enviados por e-mail
  • Para os alunos que indicaram interesse em fazê-la via e-mail, quando houve o informe da reitoria sobre antecipação de feriados e proibição de atividades avaliativas entre 27/março a 4/abril.
Aula 24 - 💥💥PROVA 2💥💥 - 4/mai
  • Das 19h do dia 4/mai às 20h do dia 7/mai - Detalhes serão enviados por e-mail
  • Lembre-se de entregar as suas respostas das listas 5 e 6 até as 19h do dia 4/mai.
RECUPERAÇÃO - 26/mai (quadrimestre seguinte)
  • Das 18h do dia 26/mai às 20h do dia 29/mai - Detalhes serão enviados por e-mail


👎 Plágio



🏋 Listas de exercícios



🎓 Critérios de avaliação



💯 Notas



💪 Mecanismo de recuperação



🤒 Mecanismos de avaliação substitutivos




Carla Negri Lintzmayer - carla.negri@ufabc.edu.br