Reading
Reference Books & Lecture Notes
[AHU] A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley 1974.
[CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2009.
[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.
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/2010.
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.
IV. 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.
