---

2023 Q2

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

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

🚨 Avisos importantes (fique atento sempre!)

[5/out] 🔥🔥🔥🔥🔥 As notas finais, pós-rec, estão disponíveis na planilha. Cheque seu e-mail para mais informações!

[20/set] ATENÇÃO!! A prova de recuperação acontecerá na sala S-212-0.
[25/ago] Avisos (semi-)finais:

• As notas das listas e da prova 2 estão disponíveis na seção de notas, bem como as médias e conceitos pré-recuperação.
• A vista de prova nesse quadrimestre poderá ser feita no dia 30 de agosto, entre 16h e 18h, ou no dia 20 de setembro, entre 10h e 12h, na minha sala.
• Os que quiserem realizar a prova de recuperação (conceito final F) devem enviar e-mail até o dia 20 de setembro, para que eu possa imprimir a quantidade certa de provas.
• Nos dias 18 de setembro, das 16h às 18h, e no dia 20 de setembro, entre 10h e 12h, estarei disponível para atendimento na minha sala.
• Enviarei e-mail na próxima semana comentando alguns detalhes sobre a solução da prova 2.

[18/ago] Haverá atendimento extra, do monitor da disciplina, na segunda-feira, dia 21/08, na sala de aula (302-2), das 17h às 19h.
[4/ago] Há um exemplo extra de programação dinâmica disponível no cronograma!!
[4/ago] Haverá um atendimento extra das 18h às 19h no dia 16 de agosto, na sala da professora.
[1/ago] Como não haverá aula nem atendimento no dia 9/ago, haverá um atendimento extra no dia 11/ago, antes da aula: a partir das 14h30, na sala da professora.
[21/jul] O atendimento feito antes da aula da próxima quarta, dia 26/jul, será, excepcionalmente, cancelado. Para compensar, farei atendimento após a aula, das 18h às 20h no mesmo dia.
[19/jul] Aos alunos que requisitaram sub da P1 (por e-mail): verifiquem seus e-mails.
[19/jul] As notas da terceira entrega de exercícios está disponível na seção de notas.
[10/jul] As notas da prova 1 estão disponíveis na seção de notas. A vista das provas poderá ser feita em qualquer horário de atendimento.
[5/jul] As notas das listas de exercícios foram atualizadas com as notas da segunda entrega.
[23/jun] As notas das listas de exercícios estão disponíveis na seção de notas. As listas serão/foram entregues na aula de hoje. Não se esqueça de pedir ajuda sobre o que errou!
[21/jun] A segunda entrega de exercícios, prevista para o dia 23/jun, pode também ser entregue no dia 28/jun, entre as 16h e as 16h30, na sala 518-2, para o professor Maycon Sambinelli.
[21/jun] No dia 1/jul, dia da reposição, haverá atendimento entre 9h e 10h e entre 12h e 13h, na própria sala da aula (S-212-0).
[21/jun] Nos dias 28/jun e 30/jun não haverá atendimento da professora.
[21/jun] As listas corrigidas serão devolvidas aos alunos, para que possam aprender com os problemas. Até o final do quadrimestre, devem ser devolvidas à professora, pois são itens de avaliação.
[21/jun] Atenção! Modifiquei algumas coisas na parte de entregas das listas de exercícios. Confira!
[13/jun] Atenção! As entregas das listas que valem nota devem ser feitas durante os horários das aulas!
[7/jun] As datas de entrega das listas foram modificadas (adiadas).
[2/jun] Os horários de atendimento foram definidos.
[2/jun] Um exercício novo (4(c)) foi inserido na lista de entrega dos exercícios da lista 1.
[24/mai] Verifique a seção Recomendação!!!
[24/mai] Responda a esse formulário antes das aulas começarem para podermos definir os melhores horários de atendimento extra-classe.
[24/mai] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado em avaliação.

📝 Dias, horários e locais das aulas

🙋 Dias, horários e locais dos atendimentos

🧐 Ementa da disciplina

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

Objetivos:

• Apresentar noções e conceitos de complexidade de computação;
• Apresentar métodos e conceitos que permitam ao aluno, de maneira confiável, avaliar a qualidade de um algoritmo. A essência destes métodos e conceitos estará focalizada no cálculo de complexidade e prova de corretude de algoritmos;
• Caracterizar técnicas gerais de desenvolvimento de algoritmos que permitam ao aluno melhor projetá-los conforme sua natureza. As técnicas gerais escolhidas a serem estudadas são Divisão e Conquista, Método Guloso e Programação Dinâmica;
• Apresentar noções básicas de Classes de Complexidade, em particular as classes P, NP e NP-Completo.

🖖 Recomendação

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

• conhecimentos de programação (em qualquer linguagem imperativa), com boas noções de algoritmos recursivos,
• familiaridade com estruturas de dados básicas (vetores, listas, pilhas, filas e árvores),
• capacidade para reconhecer argumentos lógicos em uma prova matemática (por indução, contradição, construção),
• familiaridade com linguagem matemática (como quantificadores lógicos, somatórios e manipulação de funções).

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 também 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.

⚠ Revise, no mínimo, indução e recursão antes das aulas começarem!!!⚠
Veja a lista 0 de exercícios!

Outros materiais de apoio:

• Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
• Videoaulas de Fundamentos da matemática para computação, do prof. Cláudio Possani, da USP.
• Meus vídeos com definição e exemplos de indução.
• Projeto de algoritmos (em C), do prof. Paulo Feofiloff, da USP.
• Estruturas de dados (em C), do prof. Paulo Feofiloff, da USP.
• Videoaulas de Algoritmos e Estruturas de Dados I, do prof. Mário San Felice, da UFSCar.
• Notas de aula da disciplina de Estruturas de Dados do prof. Rafael Schouery, da Unicamp (introdução à programação em C, recursão, listas, pilhas e filas, árvores).

📚 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 pequenas 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.

📆 Cronograma

• Sobre qualquer material feito por mim, participe do banco de informantes.

ATENÇÃO! O conteúdo exato e materiais de apoio de cada aula são atualizados durante o quadrimestre.
As aulas que já foram ministradas estão coloridas.

Aula 1 - 31/mai Conteúdo: Sobre o curso. Referências: veja seção de recomendação e o Cap. 1 [LM]. Material complementar: slides de introdução ao curso e revisão; Lista 0; vídeos sobre indução:

Aula 2 - 2/jun Conteúdo: Introdução à análise de algoritmos. Corretude de algoritmos (iterativos). Referências: Cap. 2 e 3 [LM], Cap. 1 e 2 [CLRS2].

Aula 3 - 7/jun Conteúdo: Finalização da corretude da busca binária. Tempo de execução. Notação assintótica. Referências: Cap. 4 e 5 [LM], Cap. 3 [CLRS2].

9/jun (Feriado Corpus Christi) Reposição em 22/ago (terça-feira).

Aula 4 - 14/jun Conteúdo: Tempo com notação assintótica. Insertion Sort. Referências: Cap. 6 e 15 [LM], Cap. 2.1, 2.2, 3.1, 3.2 [CLRS2], Extra: execução Insertion Sort.

Aula 5 - 16/jun Conteúdo: Recursão. Corretude e tempo de execução em algoritmos recursivos. Recorrências. Referências: Cap. 7 e 8 (intro) [LM], Cap. 2.3, 4 (intro) [CLRS2],

Aula 6 - 21/jun Conteúdo: Divisão e Conquista. Mergesort. Recorrências. Referências: Cap. 16 [LM], Cap. 4 [CLRS2]. Extra: execução Mergesort, execução Mergesort com código.

Aula 7 - 23/jun Conteúdo: Selection Sort. Heap. Referências: Cap. 12 e 17 [LM], Cap. 6 [CLRS2]. Extra: execução SelectionSort, execução Heap, execução Heap e Heapsort, execução Heapsort, execução ordenação, limite inferior ordenação;

Aula 8 - 28/jun - Sem aula presencial e sem atendimento! Conteúdo: Solução de recorrências: substituição e iteração. Referências: Cap. 8.1 e 8.2 [LM], Cap. 4 [CLRS2]. Vídeos para apoio a esse conteúdo (tempo total = 63min):

Aula 9 - 30/jun - Sem aula presencial e sem atendimento! Conteúdo: Solução de recorrências: árvore de recursão e método Mestre. Referências: Cap. 8.3 e 8.4 [LM], Cap. 4 [CLRS2]. Vídeos para apoio a esse conteúdo (tempo total = 51min): Extra!! Demonstração do Teorema Mestre:

Reposição - 1/jul (sábado) - 10h às 12h Conteúdo: Aulas 8 e 9. Sala: S-212-0. Haverá atendimento entre 9h e 10h e entre 12h e 13h, na mesma sala.

Aula 10 - 5/jul Conteúdo: Término de heap e Heapsort. Fim de ordenação. Revisão e dúvidas para prova.

Aula 11 - 7/jul Prova 1 Atenção! Não haverá monitoria neste dia!

Aula 12 - 12/jul Conteúdo: Introdução a grafos (grafos, digrafos, Teorema do Aperto de Mãos, subgrafos, passeios/caminhos, conexidade e distância). Introdução à análise de algoritmos em grafos (representação em listas e matriz de adjacências e cálculo do grau). Referências: Cap. 23 (até seção 23.8) [LM], Cap. 22 [CLRS2]. Material complementar: texto completo da aula, implementações.

Aula 13 - 14/jul Conteúdo: Árvores. Busca em grafos e busca em largura. Referências: Seções 23.8, 23.9, 23.10 e 24.1 [LM], Cap. 22 [CLRS2]. Extra: execução BFS, execução BFS.

Aula 14 - 19/jul Conteúdo: Busca em profundidade. Aplicações das buscas. Busca em digrafos. Referências: Seções 24.2, 24.3, 24.4 e 24.5 [LM], Seção 22.3 [CLRS2]. Extra: execução DFS.

Aula 15 - 21/jul Conteúdo: Introdução a algoritmos gulosos. Escalonamento de tarefas compatíveis. Referências: intro 21, 21.1 [LM].

Aula 16 - 26/jul Conteúdo: Mochila fracionária. Árvore geradora mínima. Referências: Seção 21.2 e intro 25 [LM], Cap. 23 [CLRS2].

Aula 17 - 28/jul Conteúdo: Algoritmo de Kruskal. Union-Find. Referências: Cap. 25.1, 13 [LM], Cap. 15 [CLRS3]. Extra: execução Union Find; outra execução Union Find; execução Kruskal; outra execução Kruskal.

Aula 18 - 2/ago Conteúdo: Kruskal com Union-Find. Introdução à Programação Dinâmica. Mochila inteira. Referências: Seção 25.1, intro Cap. 22, Seção 22.3 [LM], Cap. 15 [CLRS3]. Extra: execução Mochila com código.

Aula 19 - 4/ago Conteúdo: Término da Mochila inteira. Alinhamento de sequências. Caminhos mínimos. Referências: Seção 22.4 e Cap. 27 e Seções 27.1 e 27.2 [LM], Cap. 24.3 e 25.2 [CLRS2]. Extra: execução Alinhamento, execução Dijkstra, outra execução Dijkstra, execução Floyd-Warshall.

9/ago - SEM AULA Conforme já previsto desde o início do quadrimestre. Também não haverá atendimento nesse dia, e haverá atendimento a partir das 14h30 do dia 11/ago na sala da professora. Exemplo extra de programação dinâmica: problema do Corte de Barra de Ferro.

Aula 20 - 11/ago Algoritmo de Floyd-Warshall. Redução entre problemas. Referências: Cap. 28 [LM], Cap. 34 [CLRS2]. Material complementar (apresentado em sala): texto completo Floyd-Warshall, slides de complexidade.

Aula 21 - 16/ago Classes P, NP, NP-completo e NP-difícil. Problemas NP-completos. Referências: Cap. 29 [LM], Cap. 34 [CLRS2]. Material complementar (apresentado em sala): slides de complexidade. Curiosidades: P vs. NP and the Computational Complexity Zoo; Map of Computer Science. Extra: Curso de otimização combinatória - como lidar com problemas NP-difíceis.

Aula 22 - 18/ago Revisão e dúvidas para prova.

Aula 23 - 22/ago (⚠ Em uma terça-feira, às 16h, por ser reposição - na mesma sala!) Prova 2 Atenção! Não haverá monitoria neste dia!

Aula 24 - RECUPERAÇÃO - 23/set (quadrimestre seguinte) Prova de recuperação para os alunos que ficaram com conceito F ** E QUE ** enviarem e-mail indicando interesse em realizá-la. Das 10h às 12h na sala S-2012-0.

👎 Plágio

• Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:
  1. fraudem avaliações,
  2. fabriquem ou falsifiquem dados,
  3. plagiem ou não creditem devidamente autoria,
  4. aceitem autoria de material acadêmico sem participação na produção,
  5. vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.
  
  
• Muitos ainda têm dúvidas sobre a interpretação das regras definidas pelo Código de Ética da UFABC.
• Por esta razão, diversos professores elaboraram um documento (disponível aqui) com vários exemplos e esclarecendo a interpretação das regras acima.
• Abaixo uma versão resumida, que não substitui de modo algum sua leitura:
• Regra 1: Você não pode enviar para avaliação um trabalho que não seja de sua própria autoria ou que seja derivado/baseado em soluções elaboradas por outros.
• Regra 2: Você não pode compartilhar a sua solução com outros alunos nem pedir aos seus colegas que compartilhem as soluções deles com você.
• Regra 3: Nos trabalhos enviados para avaliação você deve indicar eventuais assistências que você tenha recebido.
• Nós encorajamos fortemente que você procure outras pessoas quando houver a necessidade. Discuta o problema e possíveis ideias para soluções, mas elabore sua própria solução, por conta própria.
• Qualquer violação às regras descritas acima 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.
• Possível denúncia à Comissão de Transgressões Disciplinares Discentes da Graduação, a qual decidirá sobre a punição adequada à violação que pode resultar em advertência, suspensão ou desligamento, de acordo com os artigos 78-82 do Regimento Geral da UFABC.
• Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!

🏋 Listas de exercícios

• Sobre gabaritos de listas de exercícios:
  eu acredito que o objetivo de um exercício teórico não é a resolução do problema em si, mas sim praticar a resolução de problemas;
  você precisa chegar nas soluções por conta própria (com algumas dicas da minha parte) ao invés de apenas ler um gabarito (que mostrará uma única solução possível);
  por isso, eu não disponibilizo gabaritos das minhas listas;
  a melhor forma para você saber se resolveu o exercício corretamente é me procurando em horários de atendimento e me mostrando a sua solução.
• Sobre descrição de algoritmos nos exercícios: veja essa página.



• Ao todo teremos 6 listas, cujos enunciados estão disponibilizados abaixo.
• O objetivo principal é prover problemas representativos dos conceitos vistos, equivalentes aos que serão cobrados nas avaliações.
• As soluções das listas deverão ser feitas à mão em papel (capriche na letra!).
  • Se algo te impossibilita de fazer as listas à mão, converse comigo antes de fazer em outro formato, pois caso contrário sua nota naquela lista será zero.
• Não entregue sua primeira solução! Passe a limpo antes.
• Procure atendimento sempre que tiver dúvidas nos exercícios.
• Faça o maior número de exercícios que puder, sempre.
  • Os exercícios destacados abaixo, após as listas, são os que valerão nota.
  • Vale moral!!
    Qualquer exercício extra que for feito pode ser entregue nos dias das provas para serem considerados como evidência do seu esforço.
    Participar das aulas, dos atendimentos/monitorias, também vale moral.
    Alunos com moral terão direito a pedir arredondamento de conceitos e notas ou abono de alguma falta ao final do curso.
    Em nenhuma hipótese será feito o arredondamento de conceitos ou abono de faltas para alunos sem moral.



• Finalmente:
  • Lista 0 (revisão, não vale nota e não precisa entregar)
  • Lista 1 (tempo de execução, notação assintótica e corretude de algoritmos iterativos - Aulas 2, 3, 4)
    Vocês podem ver as soluções de alguns exercícios neste documento ou então nestes vídeos:
    
  • Lista 2 (recorrências e corretude de algoritmos recursivos - Aulas 5, 6, 7, 8)
    Vocês podem ver as soluções de alguns exercícios nestes vídeos:
    
  • Lista 3 (ordenação - Aulas 4, 6, 9)
  • Lista 4 (introdução a grafos - Aulas 12, 13, 14)
  • Lista 5 (algoritmos gulosos e programação dinâmica - Aulas 15 a 19)
  • Lista 6 (complexidade - Aulas 20 a 22)



• As listas devem ser entregues durante os horários das aulas e os extras devem ser entregues no dia das provas!



• As listas corrigidas serão devolvidas aos alunos, para que possam aprender com os problemas. Até o final do quadrimestre, devem ser devolvidas à professora, pois são itens de avaliação.



• Datas das entregas:
  • Até o dia 16/jun: exercícios 2(a), 3, 4(b) e 4(c) da Lista 1.
  • Até o dia 23/jun: exercícios 11 e 18 da Lista 1.
    Opcionalmente, vocês podem entregar a lista no dia 28/jun, para o prof. Maycon Sambinelli, na sala 518-2, entre 16h e 16h30.
  • Até o dia 7/jul: exercícios 2(a), 2(l), 2(m), e 8 da Lista 2 e exercício 8 da Lista 3.
    No exercício 8 da lista 2, não precisa provar invariante de laço, caso sua solução use laços.
    No exercício 8 da lista 3, não precisa fazer demonstração formal.
  
  
  • Até o dia 26/jul: exercícios 3 e 8 da Lista 4.
  • Até o dia 4/ago: 5 e 7 da Lista 5.
  • Até o dia 16/08: 12 e 13 da Lista 5.
  • Até o dia 22/08: 2, 4 e 6 da Lista 6.

🎓 Critérios de avaliação

• A avaliação da disciplina constituirá da nota de duas provas, denotadas P₁ e P₂, e da média ponderada das notas das listas, denotada L.
• A prova 1 vale 43% da nota e 0 ≤ P₁ ≤ 10.
• A prova 2 vale 42% da nota e 0 ≤ P₂ ≤ 10.
• As listas valem 15% da nota e 0 ≤ L ≤ 10, com L = 10 × (soma das notas obtidas nos exercícios entregues) / (número de exercícios exigidos).
• O conteúdo das provas englobará todos os temas vistos até a data das mesmas.


• Sua média final (MF) antes da recuperação, portanto, será
  
  MF = 0.43 × P₁ + 0.42 × P₂ + 0.15 × L


• Seu conceito final será
  
  A, se MF ≥ 8.5
  B, se 7.0 ≤ MF < 8.5
  C, se 5.0 ≤ MF < 7.0
  F, se MF < 5.0
  


• Não esqueça do vale moral!

💯 Notas

Confira aqui as notas das listas de exercícios!

Confira aqui as notas de todas as atividades.

Lembre-se sempre que a intenção das listas de exercício é reforçar seu aprendizado.
Não deixe de procurar atendimento para entender o motivo de ter errado algum exercício!

💪 Mecanismo de recuperação

• A recuperação será aplicada apenas aos alunos que tiverem conceito final F e que enviarem e-mail confirmando interesse.
• O conteúdo da prova englobará todos os temas vistos durante o quadrimestre.
• A nota obtida na prova de recuperação (NR) será usada obter a nota final com recuperação (NFR), que consiste na média a seguir:
  NFR = max {MF, (MF + NR) / 2}
• O conceito final obtido na recuperação substituirá o conceito original e será
  C, se NFR ≥ 5.0
  F, se NFR < 5.0
  

🤒 Mecanismos de avaliação substitutivos

• Uma prova substitutiva será aplicada ao aluno que possuir justificativa de ausência em uma das provas.
• A listagem dos documentos aceitos como justificativa consta na resolução ConsEPE n° 181.
• A nota obtida na prova substitutiva necessariamente substituirá a prova para a qual o aluno tem justificativa.
• A data para realização da prova substitutiva deverá ser combinada com a professora por e-mail o quanto antes, assim que o aluno estiver em condições de realizá-la.

---