Given the impact of computers and computing on almost every aspect of society, the ability to develop, analyze, and implement algorithms is gaining more focus. Algorithms are increasingly important in theoretical mathematics, in applications of mathematics, in computer science, as well as in many areas outside of mathematics. In high school, however, algorithms are usually restricted to computer science courses and as a result, the important relationship between mathematics and computer science is often overlooked (Henderson, 1997). The mathematical ideas behind the design, construction and analysis of algorithms, are important for students' mathematical education. In addition, exploring algorithms can help students see mathematics as a meaningful and creative subject. This study provides a review of the history of algorithms and algorithmic complexity, as well as a technical monograph that illustrates the mathematical aspects of algorithmic complexity in a form that is accessible to mathematics instructors at the high school level.
The historical component of this study is broken down into two parts. The first part covers the history of algorithms with an emphasis on how the concept has evolved from 3000 BC through the Middle Ages to the present day. The second part focuses on the history of algorithmic complexity, dating back to the text of Ibn al-majdi, a fourteenth century Egyptian astronomer, through the 20th century. In particular, it highlights the contributions of a group of mathematicians including Alan Turing, Michael Rabin, Juris Hartmanis, Richard Stearns and Alan Cobham, whose work in computability theory and complexity measures was critical to the development of the field of algorithmic complexity. The technical monograph which follows describes how the complexity of an algorithm can be measured and analyzes different types of algorithms. It includes divide-and-conquer algorithms, search and sort algorithms, greedy algorithms, algorithms for matching, and geometric algorithms. The methods used to analyze the complexity of these algorithms is done without the use of a programming language in order to focus on the mathematical aspects of the algorithms, and to provide knowledge and skills of value that are independent of specific computers or programming languages.
In addition, the study assesses the appropriateness of these topics for use by high school teachers by submitting it for independent review to a panel of experts. The panel, which consists of mathematics and computer science faculty in high school and colleges around the United States, found the material to be interesting and felt that using a pre-programming approach to teaching algorithmic complexity has a great deal of merit. There was some concern, however, that portions of the material may be too advanced for high school mathematics instructors. Additionally, they thought that the material would only appeal to the strongest students. As per the reviewers' suggestions, the monograph was revised to its current form.
