Nossa referência básica será

T.H. Cormen, C.E. Leiserson, R.L. Rivest,
Introduction to Algorithms,
MIT Press & McGraw-Hill, 1992.

O livro é conhecido como "o CLR".  A homepage do livro tem uma errata, em postscript; eu fiz uma cópia da errata (errata 1.2, de 28 de julho de 1994) na rede do IME.  A segunda edição acaba de sair:

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein,
Introduction to Algorithms, 2nd. edition,
MIT Press, 2001.

Diremos que esta segunda edição é "o CLRS". Também há uma edição, aparentemente idêntica (estranho, não?), da McGraw-Hill.

O livro de Skiena também pode ser útil:

Steven Skiena, 
The Algorithm Design Manual,
Telos/Springer-Verlag, 1998.
[O livro é acompanhado de um CD-ROM.]

Há muitos livros de análise de algoritmos. Além dos mencionados acima posso sugerir os seguintes:

• D.E. Knuth,   The Art of Computer Programming: Sorting and Searching,
  Addison-Wesley, 1973.

  O clássico dos clássicos.

• A.V. Aho, J.E. Hopcroft, J.D. Ullman,   The Design and Analysis of Computer Algorithms,
  Addison-Wesley, 1975.

  Um pouco antigo, mas ainda está de pé. Não confunda com o Data Structures and Algorithms dos mesmos autores.

• Udi Manber,   Introduction to Algorithms: A Creative Approach,
  Addison-Wesley, 1989.
  
  
• Ian Parberry,   Problems on Algorithms,
  Prentice Hall, 1995.

  Um pequeno livro só de exercícios.  Há uma versão digital do livro.

• G. Brassard e P. Bratley,   Fundamentals of Algorithmics,
  Prentice Hall, 1996.
  
  
• Robert Sedgewick,   Algorithms in C, 3rd. edition, vol. 1,
  Addison Wesley Longman, 1998.

  Mais algoritmos que análise. A parte de análise não é suficiente para MAC5711.

• David Harel,   Algorithmics: The Spirit of Computing, 2nd. edition,
  Addison-Wesley, 1992.
  
  
• Ellis Horowitz, Sartaj Sahni,   Fundamentals of Computer Algorithms,
  Computer Science Press, 1978.
  
  
• Micha Hofri,   Analysis of Algorithms: Mathematical Methods, Computational Tools,
  Oxford University Press, ISBN 0-19-509954-0, 1995.

  Não conheço o livro, mas parece ser interessante.

• Alfred V. Aho, Jeffrey D. Ullman,   Foundations of Computer Science (C edition),
  Computer Science Press, 1995.

  Os alicerces da ciência da computação que todo bacharel da área deveria conhecer. Segundo Ian Parberry, "This textbook is redefining the undergraduate computer science curriculum at many leading institutions. It is a good place to go to brush up on your discrete mathematics, data structures, and problem solving skills."  [O livro é excelente mas tem alguns detalhes fracos. O tratamento de indução matemática nas seções 2.3 e 2.4, por exemplo, é capenga: o livro dedica 18 páginas ao assunto e ainda assim não faz um bom serviço!]
  
  

• Dexter C. Kozen,   The Design and Analysis of Algorithms,
  Sringer-Verlag, 1992.
  

• M. Moret and H. Shapiro,   Algorithms from P to NP: Design and Efficiency,
  Benjamin/Cummings, 1991.

  Muito bom, mas foi escrito para quem já tem alguma noção do assunto.

• Robert Sedgewick e Philippe Flajolet,   An Introduction to the Analysis of Algorithms,
  Addison-Wesley, 1996.

  Talvez pesado demais para MAC5711.

• K. Mehlhorn,   Data Structures and Algorithms 1: Sorting and Searching,
  Springer-Verlag, 1984.
  
  

• G. Gonnet and R. Baeza-Yates,   Handbook of Algorithms and Data Structures, 2nd. ed.,
  Addison-Wesley, 1991.
  
  
• R.L. Graham, D.E. Knuth, O. Patashnik,   Concrete Mathematics, 2nd. ed.,
  Addison-Wesley, 1994.

  Não trata de análise de algoritmos, mas de ferramentas matemáticas úteis para a análise séria de algoritmos.  Há uma edição em português sob o título Matemática Concreta, da editora Livros Técnicos e Científicos, 1995.

Uma das finalidades secundárias de MAC5711 é desenvolver a habilidade de argumentar com precisão, ou seja, a habilidade de escrever "provas matemáticas".  Eis alguns livros que podem ajudar:

• Daniel J. Velleman,  How to Prove It,
  Cambridge University Press, 1994.
• Nicholas J. Higham,  Handbook of Writing for the Mathematical Sciences,
  SIAM, 1993.
• Donald E. Knuth, Tracy Larrabee, Paul M. Roberts,  Mathematical Writing,
  MAA (The Mathematical Association of America), 1989.
• Norman E. Steenrod, Paul R. Halmos, Menahem M. Schiffer, Jean A. Dieudonné,  How to Write Mathematics,
  AMS (American Mathematical Society), 1973.
• Dicas sobre como escrever texto científico, do prof. Fernando Q. Gouvêa (Colby College, Maine).