Programação das aulas de MAC6711

• 25 de fevereiro: recepção dos ingressantes (não haverá aula)

• 27 de fevereiro (Aula 1):
  • Problema do número de inversões
  • Notação assintótica
  • Divisão e conquista
  • Recorrências
  • Lista 1
  Leitura recomendada: notas de aulas do Prof. Paulo Feofiloff sobre notação assintótica e recorrências, secs 5.1 a 5.3 do livro de Kleinberg e Tardos (KT).
  Slides [pdf].

• 6 de março (Aula 2):
  • Divisão e conquista
  • Par de pontos mais próximos
  Leitura recomendada: sec 33.4 do CLRS, sec 5.4 do livro de Kleinberg e Tardos (KT), sec 7.3 do capítulo 7 das JAI 2009.
  Slides [pdf].

• 11 de março (Aula 3):
  • Multiplicação de números grandes - algoritmo quadrático
  • Algoritmo de Karatsuba
  • Algoritmo de Strassen
  Leitura recomendada: sec 28.2 do CLRS, sobre o algoritmo de Strassen, e sec 5.5 do KT, sobre o algoritmo de Karatsuba. Veja também o vídeo How Karatsuba's algorithm gave us new ways to multiply e a implementação deste algoritmo e outros na GNU Multiple Precision Arithmetic Library. Veja ainda o artigo recente no blog Gödel's Lost Letter sobre o algoritmo O(n lg n) para multiplicação de inteiros com n bits.
  Para resolução de recorrências, leia o cap 4 do CLRS.
  Exercício: Prove, por indução em n, que a solução da recorrência T(1) = 1 e T(n) = 8T(n/2)+n² para n potência de 2 é T(n) = 2n³-n².
  Exercício: Resolva a recorrência T(1) = 1 e T(n) = 7T(n/2)+n² para n potência de 2. Deduza depois qual é o comportamento assintótico de T(n), ou seja, qual é a sua ordem de crescimento.
  Exercício: Se pensarmos que o tamanho da entrada do algoritmo de Strassen é m=2n^2, podemos deduzir que o tempo do algoritmo, em função do m é dado pela seguinte recorrência: T(m) = 8T(m/4) + m. Resolva essa recorrência e conclua qual é o consumo de tempo do algoritmo em função do m. Isso é ou não consistente com o que deduzimos na aula?
  Slides [pdf].

• 13 de março (Aula 4):
  • Uma breve discussão sobre modelos de computação
  • Seleção do k-ésimo menor
  • Lista 2
  Leitura recomendada: Cap 9 do CLRS.
  Slides [pdf].

• 18 de março (Aula 5):
  • Produto de polinômios e convoluções
    
  • Transformada discreta de Fourier (DFT)
    
  • Inversa da DFT
  Leitura recomendada: secs 30.1 e 30.2 do CLRS e sec. 5.6 do KT. Veja também a seguinte notícia, de janeiro de 2012, e o artigo nela mencionado.
  Slides [pdf].

• 20 de março (Aula 6):
  • Algoritmos probabilísticos
    
  • Teste de igualdade de polinômios
  • Problema da contenção
  • Comentários sobre o algoritmo do exponential backoff time
  • Lista 3
  Leitura recomendada: Sec 1.1 do livro Probability and Computing: Randomized Algorithms and Probabilistic Analysis, de Computing and Probability (QA274.M574 2005), e começo do Cap 13 e Sec 13.1 do KT. Leia também a explicação sobre o algoritmo de exponential backoff time, que é utilizado na Ethernet.
  Slides [pdf].

• 25 de março (Aula 7):
  • Quicksort e Select aleatorizados
  • Par mais próximo de pontos: um algoritmo aleatorizado
  Leitura recomendada: Secs 7.3, 7.4 e 9.2 do CLRS. Sec 13.7 do KT.
  Slides [pdf].

• 27 de março (Aula 8):
  • Corte mínimo em um grafo: algoritmo de Karger
  Leitura recomendada: Secs 13.2 do KT e entrada da wiki sobre o algoritmo de Karger. Lá você encontra a descrição da versão acelerada do algoritmo, proposta por Karger e Stein.
  Slides [pdf].