Acceleration of software execution time for operations involving sequences or matrices

Authors

DOI:

https://doi.org/10.32919/uesit.2022.03.01

Keywords:

programming, olympiad tasks, sequence, matrix, C

Abstract

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

Download data is not yet available.
Abstract views: 76 / PDF downloads: 42

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

Accepted
2022-09-01

Published

2022-09-30

How to Cite

Mitsa, O., Horoshko, Y., & Vapnichnyi, S. (2022). Acceleration of software execution time for operations involving sequences or matrices. Ukrainian Journal of Educational Studies and Information Technology, 10(3), 1–12. https://doi.org/10.32919/uesit.2022.03.01