Análise de Algoritmos

Mauricio Ayala Rincón

Bibliography:

• S. Baase and A. van Gelder Computer Algorithms, Introduction to Design and Analysis, Third Edition. Addison-Wesley, 1998.
• A. H. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms. Addisson-Wesley, 1974.
• R. Sedgewick, Algorithms in C++. Addison-Wesley, 1992.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms - Second Edition -. MIT press, 2001.
• G. A. Stephen, String Searching Algorithms. Word Scientific, 1994.
• M. Crochemore and W. Ritter, Text Algorithms. Oxford University Press, 1994.

Didactic Material of the course:

• Ementa 2009/I (Postscript 90 KB) (PDF 120 KB)

• Estagiario de Docência 2008/I: Daniel Lima Ventura: ventura [at] mat [dot] unb [dot] br

• Listas de exercícios:
• 1^ra lista Março 2009 (PDF).
  Gabarito(PDF)
• 2^da lista: Maio 2009 (PDF).
  Gabarito(PDF)
• 3^nd lista: Maio/Junho 2009 (PDF).
  Gabarito(PDF)
  Nota: entrega das listas fora do prazo normal com 0%.
• Lecture Notes:
• Slides Fundamentos Teoria Complexidade
• Lists of course projects:
• Course project on approximate string pattern matching via suffix trees (Second Semester 2001). Modify the project dates according to the new programme above (Postscript, 110 KB) In Portuguese. See applet with a nice implementation of Ukkonen's suffix trees based method given by some our best students.
• Course project on string pattern matching and suffix trees (Second Semester 1994) (Compressed postscript, 25 KB) In Portuguese.
• Course project on approximate string pattern matching and suffix trees (Second Semester 1995) (Compressed postscript, 20 KB) In Portuguese.
• Course project on updating suffix trees (Second Semester 1998) ( Postscript, 45 KB) In Portuguese.
• List of toy programs:
• Sorting algorithms in C;
• Knuth-Morris-Pratt algorithm in C
.
• Matchjump Boyer-Moore functionin C
.
• Dynamic programming computation of the optimal sequence for multiplying matrices in C
.
• Dynamic programming computation of optimal binary search trees for keys with searching probabilities in C
.
• Lista de provas:
• Primeira prova, 22.04.2009
  Gabarito (PDF)
  
• Segunda prova, 18.05.2009
  Gabarito (PDF)
  
• Terceira prova, 17.06.2009
  Gabarito (PDF)
  
• Menções 2009/I Revisão final: 08/07 10:00-12:00
• String Pattern Matching Applet Prototypes:
• SAGAReP string pattern matching applet containing the Knuth-Morris-Pratt, the Boyer-Moore and Suffix-Trees based pattern matching methods.