Acceleration of software execution time for operations involving sequences or matrices
DOI:
https://doi.org/10.32919/uesit.2022.03.01Keywords:
programming, olympiad tasks, sequence, matrix, CAbstract
The article describes three methods for lowering program runtime that are solutions to computer science Olympiad problems involving sequences or matrices. The first method relies on the representation of some sequences as matrices, after which the program for calculating the sequence's members will have asymptotics equivalent to the exponentiation algorithm's time complexity and be O(log (n)). The second strategy is to improve the existing code in order to significantly shorten program runtime. For scientists who create code for scientific inquiries and deal with matrix multiplication operations, understanding this approach is crucial. The author's challenge is presented and solved using the third strategy, which is based on minimizing temporal complexity by looking for regularities.
Downloads
References
Barry, P. (2003). Triangle Geometry and Jacobstahl Numbers. Irish Mathematical Society Bulletin, 51, 45–57. DOI: https://doi.org/10.33232/BIMS.0051.45.58
Čerin, Z. (2007). Sums of Squares and Products of Jacobsthal Numbers. Journal of Integer Sequences, 10(2), Art. 07.2.5.
Ermolaev, I. (2019). Umnozhenie matritc: effektivnaia realizatciia shag za shagom (Matrix multiplication: effective implementation step by step). Retrieved from https://habr.com/ru/post/359272/.
Graham, R. L., Knuth, D. E., & Patashnik, O. (1994). Concrete Mathematics (2nd ed.). Boston: Addison-Wesley.
Horoshko, Y. V., Mitsa, O. V., & Melnyk, V. I. (2019). Methodological approaches to solving olympiad tasks on computer science. Information Technologies and Learning Tools, 71(3), 40–52. DOI: https://doi.org/10.33407/itlt.v71i3.2482. DOI: https://doi.org/10.33407/itlt.v71i3.2482
Knuth, D. E. (2011). The Art of Computer Programming (vol. 1-4), A Boxed Set (3rd ed.). Boston: Addison-Wesley.
Stetsyuk, P. I. (2014). Ellipsoid methods and r-algorithms. Chisinau: Evrika.
The last number. (2013). EOlymp. Retrieved from https://www.e-olymp.com/uk/problems/2808.
Zhukovsky, S. S. (2015). Methodical Aspects of Preparing Gifted Schoolchildren for Informatics Olympiads. Problems of modern pedagogical education, 47(V), 62–69.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Oleksandr Mitsa, Yurii Horoshko, Serhii Vapnichnyi
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons «Attribution» 4.0 License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
