Material sobre curso de algoritmia

El profesor Jeff Erickson de la facultad de ciencias de la computación de la Universidad de Ilinois, ha puesto a disposición de cualquiera todo el material que imparte en sus clases sobre algoritmia. Éste lleva impartiendo esta clase desde al año 1999.

El temario que usa para impartir su clase es el siguiente:

0. Introduction, history, and course goals
Recursion
- 1. Simplify and delegate
- 2. Fast Fourier transforms
- 3. Backtracking
- 4. Fast exponential-time algorithms
- 5. Dynamic programming
- 6. Advanced dynamic programming tricks
- 7. Greedy algorithms
- 8. Matroids
Randomization
- 9. Nuts and bolts (randomized quicksort)
- 10. Treaps and skip lists
- 11. Tail inequalities
- 12. Uniform and universal hashing
- 13. Randomized minimum cut
Amortized analysis
- 14. Aggregation, taxation, potential
- 15. Scapegoat trees and splay trees
- 16. Maintaining disjoint sets ("union-find") — includes O(α(n)) amortized analysis
Basic graph algorithms
- 17. Representations, traversal
- 18. Minimum spanning trees
- 19. Single-source shortest paths
- 20. All-pairs shortest paths
Flows and cuts
- 21. Maximum flows and minimum cuts
- 22. Maximum flow algorithms
- 23. Applications of maximum flow
- 24. Extensions of maximum flow
Linear programming
- 25. Definitions and duality
- 26. The simplex algorithm
Lower bounds
- 27. Decision trees, leaf counting
- 28. Adversary arguments ("n-card monte")
- 29. NP-hardness
- 30. Approximation algorithms
Appendix
- I. Induction proofs
- II. Solving recurrences

Pero además del temario en sí, también podemos acceder a todas las diapositivas, deberes y exámenes de cada clase por año.

Podemos también descargarnos todo el contenido en un sólo fichero, las charlas o los deberes y exámenes. Todos ellos en formato PDF.

Libros

Buscar

Entradas Recientes

Categorías

Enlaces