The most famous algorithms in the history of mathematics and computer science

Full Text

Background. We analyze the awareness of some widely known algorithms in mathematics and computer science. Our topic is relevant to those who often ask such questions as: "is this the best way I have chosen?" We decided to test our friends: how many algorithms they know, then analyze the results and find out which algorithms are most often studied, and which are less common.

Aim. Provide a subjective list of the best-known algorithms in mathematics and computer science; determine how well-known the selected algorithms are among students.

Method. In order to conditionally identify the most frequently used algorithms, we decided to use an essay by the famous English mathematician Nicholas Higham based on the materials of the book published in 2016 [1]. The list was formed by the frequency of mentioning a certain algorithm for solving problems. The first place is occupied by Newton’s method which is referred to as the section of computational mathematics. The second place is occupied by matrix decomposition algorithms: LU, QR, Cholesky; all of them belong to the section of Computational mathematics. The next algorithm is PageRank which refers to Combinatorial algorithms. This is followed by one of the algorithms of signal processing theory — FFT. And finally, the last one on the list is Kalman’s filter, related to Computational Science

Results. We have presented the results of the survey (Fig. 1); we can see that less than half of the respondents know about 7 algorithms, while the majority knows about three. Starting from algorithm 2, it occupies the first place, because it is studied in the discipline “numerical methods” in the second year of AMI, number 5 is common among the Olympiad programmers. Everyone has seen the JPEG image format, but almost no one knows about its detailed structure. Algorithm number one is little known among the respondents, although in our opinion it is the simplest of all those presented here. The Kalman filter and the simplex algorithm are also little known because 2^nd and 1^st-year students don’t study such disciplines as computational statistics and optimization. We are very surprised by the ignorance of the algorithm PageRank, it just shows that most people don’t think about the principle of search engines.

 

Fig. 1. The results of the survey

 

This survey was conducted mostly among the students from the course of applied mathematics and computer science, there are many students from Information security and Fundamental informatics (Fig. 2). There are even students from biotechnology and rocket science. Moreover, it is the AMI students who are the most knowledgeable about the algorithms described.

 

Fig. 2. Students

 

Conclusions. We conducted a detailed awareness survey of our selected algorithms and shared our opinion on the survey results. Of course, most of the material that we have given in the presentation is not mandatory for study. Although we advise all enthusiasts of mathematics and computer science to get to know all these algorithms better as the results reveal that many of the algorithms are little known.

About the authors

Samara National Research University

Author for correspondence.
Email: beliaev.vano@gmail.com

student, group 6208, Faculty of Information Technologies

Russian Federation, Samara

Samara National Research University

Email: lazutov.mark@mail.ru

student, group 6208, Faculty of Information Technologies

Russian Federation, Samara

Samara National Research University

Email: midalina@mail.ru

PhD (Pedagogical Sciences), Associate Professor of Department of Foreign Languages and Russian as a Foreign Language

Russian Federation, Samara

References

Supplementary files