Professor responsável

• Paulo Fonseca

Monitores

• Gabriel Cortizo (gcf)
• Lucas Albuquerque (lafa)
• Marcello Cordeiro (msc3)
• Pedro Tôrres (phts)

Horário e sala

Aulas

• Segunda-feira 13h-15h (Sala D005)
• Quinta-feira 13h-15h (Sala D005)

Monitoria

• Terça 12-13h (Grad 04)

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

• Quatro 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.

Inscreva-se já no canal oficial de comunicação entre alunos, professores e monitores da disciplina (apenas para alunos matriculados com e-mail do CIn)