International Journal on Data Science and Technology

| Peer-Reviewed |

Efficient Computation of Binomial Coefficients Using Splay Trees

Received: 07 January 2016    Accepted: 15 January 2016    Published: 29 January 2016
Views:       Downloads:

Share This Article

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.

DOI 10.11648/j.ijdst.20160201.14
Published in International Journal on Data Science and Technology (Volume 2, Issue 1, January 2016)
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), 2024. Published by Science Publishing Group

Keywords

Binomial Coefficients, Splay Trees, Pascal’s Triangle, Memoization, Dynamic Programming, Combinatorics

References
[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.
Author Information
  • Computer Science Department, PES Institute of Technology, Bangalore, India

  • Computer Science Department, PES Institute of Technology, Bangalore, India

  • Computer Science Department, PES Institute of Technology, Bangalore, India

Cite This Article
  • 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

    Copy | Download

    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

    Copy | Download

    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

    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://download.sciencepg.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}
    }
    

    Copy | Download

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

    Copy | Download

  • Sections