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.
| Published in | International Journal on Data Science and Technology (Volume 2, Issue 1) |
| DOI | 10.11648/j.ijdst.20160201.14 |
| Page(s) | 15-20 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2016. Published by Science Publishing Group |
Binomial Coefficients, Splay Trees, Pascal’s Triangle, Memoization, Dynamic Programming, Combinatorics
| [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. |
APA Style
Vinayshekhar Bannihatti Kumar, Karthik Radhakrishnan, Aman Kishore Achpal. (2016). Efficient Computation of Binomial Coefficients Using Splay Trees. International Journal on Data Science and Technology, 2(1), 15-20. https://doi.org/10.11648/j.ijdst.20160201.14
ACS Style
Vinayshekhar Bannihatti Kumar; Karthik Radhakrishnan; Aman Kishore Achpal. Efficient Computation of Binomial Coefficients Using Splay Trees. Int. J. Data Sci. Technol. 2016, 2(1), 15-20. doi: 10.11648/j.ijdst.20160201.14
AMA Style
Vinayshekhar Bannihatti Kumar, Karthik Radhakrishnan, Aman Kishore Achpal. Efficient Computation of Binomial Coefficients Using Splay Trees. Int J Data Sci Technol. 2016;2(1):15-20. doi: 10.11648/j.ijdst.20160201.14
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.ijdst.20160201.14,
author = {Vinayshekhar Bannihatti Kumar and Karthik Radhakrishnan and Aman Kishore Achpal},
title = {Efficient Computation of Binomial Coefficients Using Splay Trees},
journal = {International Journal on Data Science and Technology},
volume = {2},
number = {1},
pages = {15-20},
doi = {10.11648/j.ijdst.20160201.14},
url = {https://doi.org/10.11648/j.ijdst.20160201.14},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ijdst.20160201.14},
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.},
year = {2016}
}
TY - JOUR T1 - Efficient Computation of Binomial Coefficients Using Splay Trees AU - Vinayshekhar Bannihatti Kumar AU - Karthik Radhakrishnan AU - Aman Kishore Achpal Y1 - 2016/01/29 PY - 2016 N1 - https://doi.org/10.11648/j.ijdst.20160201.14 DO - 10.11648/j.ijdst.20160201.14 T2 - International Journal on Data Science and Technology JF - International Journal on Data Science and Technology JO - International Journal on Data Science and Technology SP - 15 EP - 20 PB - Science Publishing Group SN - 2472-2235 UR - https://doi.org/10.11648/j.ijdst.20160201.14 AB - 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. VL - 2 IS - 1 ER -
Information
Email: