Reading

Reference Books & Lecture Notes
[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.
[DPV]S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, 2006.
[Ed] H. Edelsbrunner. CPS230 Lecture Notes. Duke University, 2008.
[Er]J. Erickson. CPS473G: Algorithms Lecture Notes. UIUC
[Ta] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.
Introduction
 
  • R Orellana. Lecture Note on Master Theorem. Dartmouth College.
  • I. Design Techniques
     
  • D. Knuth. Art of Computer Programming, Volume 3: Sorting and Searching. Addison-Wesley, 1998.
  •  
  • D. Bertsekas. Dynamic Programming and Optimal Control, Volumes 1, 2. Athena Scientific, 2005, 2007.
  •  
  • G. Blelloch. Introduction to Data Compression. CMU, 2001.
  •  
  • M. Paterson. Progress in Selection. SWAT, 1996.
  • II. Data Structures I
     
  • R. Seidel, M. Sharir. Top-Down Analysis of Path Compression. SIAM J. on Computing, Volume 34, Issue 3, 2005.
  •  
  • R. Tarjan, J. van Leeuwen. Worst-case Analysis of Set Union Algorithms. JACM, Volume 31, Issue 2, 1984.
  •  
  • R. Tarjan. Amortized Computational Complexity. SIAM J. Alg. Disc. Meth., Volume 6, No. 2, 1985.
  • III. Graph Algorithms
     
  • B. Chazelle. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. JACM, Volume 47, Issue 6, 2000.
  •  
  • S. Pettie, V. Ramachandran. An Optimal Minimum Spanning Tree Algorithm. JACM, Volume 49, Issue 1, 2002.
  •  
  • D. Karger, P. Klein, R. Tarjan. A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. JACM, Volume 42, Issue 2, 1995.
  •  
  • K. Bryan, T. Leise. The $25,000,000,000 Eigenvector: The Linear Algebra behind Google.SIAM Review, Volume 48, Issue 3, 2006.
  • IV. Algebraic Algorithms
     
  • J. T. Schwartz. Fast Probabilistic Algorithms for Verification of Polynomial Identities. JACM, Volume 27, Issue 4, 1980.
  •  
  • A. Klivans, D. Spielman. Randomness efficient identity testing of multivariate polynomials. STOC, 2001.
  • V. Data Structures II
     
  • R. Seidel, C. R. Aragon. Randomized search trees. Algorithmica, Volume 16, 1996.
  •  
  • C. Martinez, S. Roura. Randomized binary search trees. JACM, Volume 45, Issue 2, 1998.
  •  
  • W. Pugh. Skip lists: A probabilistic alternative to balanced trees. CACM, Volume 33, Issue 6, 1990.
  •  
  • A. Broder, M. Mitzenmacher. Network Applications of Bloom Filters: A Survey. Internet Mathematics, Volume 1, Number 4, 2005.
  •  
  • H. J. Wolfson , I. Rigoutsos. Geometric Hashing: An Overview. IEEE Computational Science and Engineering, Volume 4, Issue 4, 1997.
  •  
  • P. Indyk, R. Motwani, P. Raghavan, S. Vempala. Locality-preserving hashing in multidimensional spaces. STOC, 1997.
  • page top