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.
|