Volume 2, Issue 1, January 2016, Page: 15-20
Efficient Computation of Binomial Coefficients Using Splay Trees
Vinayshekhar Bannihatti Kumar, Computer Science Department, PES Institute of Technology, Bangalore, India
Karthik Radhakrishnan, Computer Science Department, PES Institute of Technology, Bangalore, India
Aman Kishore Achpal, Computer Science Department, PES Institute of Technology, Bangalore, India
Received: Jan. 7, 2016;       Accepted: Jan. 15, 2016;       Published: Jan. 29, 2016
DOI: 10.11648/j.ijdst.20160201.14      View  3823      Downloads  70
Abstract
Combinatorics is an important branch of mathematics. Binomial coefficients play an important role in the computation of permutations and combinations in mathematics. This paper describes a novel method of computing coefficients using Splay Trees. The performance in terms of space as well as time efficiency is compared, and conclusions on the technique are offered. We show how this technique is particularly effective in the expansion of a binomial expression.
Keywords
Binomial Coefficients, Splay Trees, Pascal’s Triangle, Memoization, Dynamic Programming, Combinatorics
To cite this article
Vinayshekhar Bannihatti Kumar, Karthik Radhakrishnan, Aman Kishore Achpal, Efficient Computation of Binomial Coefficients Using Splay Trees, International Journal on Data Science and Technology. Vol. 2, No. 1, 2016, pp. 15-20. doi: 10.11648/j.ijdst.20160201.14
Copyright
Copyright © 2016 Authors retain the copyright of this article.
This article is an open access article distributed under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Reference
[1]
Wikipedia, "Binomial Theorem", 2015. [Online]. Available: https://en.wikipedia.org/wiki/Binomial_theorem. [Accessed: 19- Dec- 2015].
[2]
E. Lee and C. Martel, "When to use splay trees", Softw: Pract. Exper., vol. 37, no. 15, pp. 1559-1575, 2007.
[3]
Mondal, Subrata. (2013). Study of Splay Tree for use in Cache Replacement Algorithm. (Master’s thesis, Jadavpur University, West Bengal, India.)
[4]
N. Neji and A. Bouhoula, "Dynamic Scheme for Packet Classification", Advances in Soft Computing, vol. 53, pp. 211-218, 2009.
[5]
W. Zhou, Z. Tan, S. Yao and S. Wang, "A Splay Tree-Based Approach for Efficient Resource Location in P2P Networks", the Scientific World Journal, vol. 2014, pp. 1-11, 2014.
[6]
D. Jones, "Application of splay trees to data compression", Communications of the ACM, vol. 31, no. 8, pp. 996-1007, 1988.
[7]
É. Rivièr and P. Felber, "SPLAY: Distributed Systems Evaluation Made Simple", USENIX symposium on Networked systems design and implementation, vol. 6, pp. 185-198, 2009.
[8]
P. Fenwick, "A new data structure for cumulative frequency tables", Softw: Pract. Exper., vol. 24, no. 3, pp. 327-336, 1994.
[9]
J. Zobel, S. Heinz and H. Williams, "In-memory hash tables for accumulating text vocabularies", Information Processing Letters, vol. 80, no. 6, pp. 271-277, 2001.
[10]
Wikipedia, "Splay tree", 2015. [Online]. Available: https://en.wikipedia.org/wiki/Splay_tree. [Accessed: 19- Dec- 2015].
[11]
Mount, David. "Splay Trees", University of Maryland, 2001. Lecture.
[12]
J. Grossman, K. Rosen and J. Grossman, Student's solutions guide to accompany discrete mathematics and its applications. New York: McGraw-Hill, 2012.
[13]
B. Pfaff, "Performance analysis of BSTs in system software", ACM SIGMETRICS Performance Evaluation Review, vol. 32, no. 1, p. 410, 2004.
[14]
S. Albers, "Randomized splay trees: Theoretical and experimental results", Information Processing Letters, vol. 81, no. 4, pp. 213-221, 2002.
Browse journals by subject