Professor responsável

Monitores

  • Maria Luisa Silva (mlss)
  • Rebecca Sousa (rls7)
  • Rodrigo Mota (raafm)
  • Tomás Pimentel (tnbp)

Horário e sala

Aulas

Monitoria

Ementa

  • Conceitos básicos de algoritmos e estruturas de dados (ED)
  • Revisão de ED básicas:
    • ED estáticas (arrays)
    • ED dinâmicas 1-D (listas encadeadas, filas e pilhas)
  • Introdução à análise de algoritmos e complexidade assintótica
  • Busca e ordenação em ED lineares
    • busca linear vs. busca binária
    • Mergesort (Dividir para conquistar - D&Q)
    • Quicksort
  • Tabelas de dispersão (Hash tables)
  • ED dinâmicas N-D: Árvores binárias
  • Busca/ordenação em ED N-D
    • árvores binárias de busca
    • Heaps e Heapsort
  • ED para relações de equivalência: union-find
  • Grafos
    • Grafos dirigidos vs. não-dirigidos
    • Percursos em grafos e aplicações (ordenação topológica, caminhos mais curtos)
    • Grafos ponderados
    • Algoritmos gulosos para problemas de otimização em grafos:
      • Caminhos mínimos com origem comum: Algoritmo de Bellman-Ford, Algoritmo de Dijkstra
      • Árvores geradoras mínimas: Algoritmo de Prim, Algoritmo de Kruskal
  • NP-completude
    • P vs. NP
    • Redução polinomial e NP-completude
    • Heurísticas para problemas NP-C
      • Backtracking
      • Branch&bound
      • Programação dinâmica

Bibliografia

  1. Anany Levitin. Introduction to the design and analysis of algorithms (3rd ed). Addison Wesley, 2011.
  2. Clifford Shaffer. Data Structures and Algorithm Analysis . Dover Publications, 2013
  3. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. Algoritmos. McGraw Hill, 2009
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. Introduction to Algorithms. MIT Press, 2009.

Avaliação

Duas unidades, cada uma composta de

  • Três listas de exercícios práticos de programação (50% da nota da unidade);
  • Uma prova escrita (50% da nota da unidade).

Além disso, cada unidade terá atividades de monitoria que podem somar até 1 (um) ponto extra à média da unidade.

Segunda chamada

  • Sobre todo o conteúdo da disciplina
  • Mediante solicitação formal junto à Secretaria de graduação

Frequência

  • A frequência a pelo menos 75% das aulas e avaliações parciais é obrigatória, respeitados o turno e o horário previstos para a disciplina. Será realizada chamada.
  • A frequência às atividades de monitoria fora do horário de aula é recomendada mas não é obrigatória.

Ética acadêmica

Os alunos são encorajados a discutirem entre si e aprenderem uns com os outros, porém não é permitido compartilhar os trabalhos total ou parcialmente. Os alunos devem proteger o sigilo dos seus trabalhos, com atenção especial a códigos depositados em repositórios públicos (e.g. GitHub, PasteBin, etc). Também não é permitido apresentar material copiado de fontes externas (incluindo código-fonte) como se fosse trabalho original sem as devidas citações e referências. O plágio não será tolerado e trabalhos contendo cópia irregular terão nota zero, independente de quem tenha sido o autor original.

Classroom