Algorithms

What to expect

This chapter looks at algorithms, and explains that an algorithm exists in its own right, independent of any attempt to represent it (e.g. as a flowchart, pseudocode or program code).

I discuss Euclid’s algorithm for finding the highest common factor, we learn that binary search features in an ancient Buddhist text, and hear about the man who gave his name to algorithms:

Al-KhwārizmīThe Islamic Golden Age from around the 8th century to the 14th century CE was a period of cultural,  economic, and scientific flourishing in the history of Islam. The caliph Harun al-Rashid (786 to 809) founded the House of Wisdom in Baghdad, which was the world’s largest city at that time. Islamic polymaths from all over the world gathered there to translate the world’s classical knowledge into Arabic and Persian. Among them was Muhammad ibn Musa al-Khwārizmī’, a Persian scholar of mathematics, astronomy, and geography. Around 820 CE, al-Khwārizmī’ was appointed the astronomer and head of the library of the House of Wisdom. He produced maps of the world, determined the circumference of the earth and compiled astronomical tables for navigation.

Al-Khwārizmī’s work on elementary algebra, Al-Kitāb al-mukhtaṣar fī ḥisāb al-jabr waʾl-muqābala (“The Compendious Book on Calculation by Completion and Balancing”), was translated into Latin in the 12th century, whereupon the phrase al-jabr in the title, meaning “balancing”, gave the world the term algebra. Another work, on Hindu-Arabic numerals and their arithmetic, was published under the title “Al-Khwārizmī: Concerning the Hindu Art of Reckoning”. Translated into Latin as Algoritmi de numero Indorum, the world now knew the word algorithm.

TL;DR.

In chapter 2 we saw that programming is not about using the correct keywords “if”, “while” and so on, rather it is the process of solving a problem with the building blocks of code: sequence, selection and iteration. In this chapter we have seen how algorithms pre-date computer science by thousands of years and derive largely from mathematics and the natural sciences. Indeed, the word algorithm comes from the name of a Persian scholar named al-Khwarizmi (circa 780-850). It’s important to understand that an algorithm exists as a concept in its own right and that a program is merely the implementation of an algorithm on a computer. The key processes involved in creating an algorithm are abstraction, decomposition and logical thinking.

Some algorithms are so useful they crop up again and again, so an understanding of searching and sorting algorithms is important in computer science. Two or more algorithms can be created to solve the same problem, and they will perform differently given the same inputs, so it’s important to choose the right algorithm for a task. Learners should be able to identify algorithms, interpret their purpose from flowcharts and pseudocode, correct errors and complete unfinished algorithms. To help with all of this, they should be able to trace an algorithm which also drives out logic errors.

References

References for this chapter

[91] https://en.wikipedia.org/wiki/Flow_process_chart

[92] https://www.sacred-texts.com/bud/j1/j1044.htm

[93] Knuth, D. The Art of Computer Programming: Sorting and Searching, 2 ed., vol. 3. Addison-Wesley, 1998.

Advertisements

[94] https://en.wikipedia.org/wiki/Timsort

[95] www.geeksforgeeks.org/comparison-among-bubble-sort-selection-sort-and-insertion-sort/ 

[96] https://youtu.be/Iv3vgjM8Pv4,

[97] https://youtu.be/RGuJga2Gl_k

[98] https://isaaccomputerscience.org/topics/searching_sorting_pathfinding.

[99] csunplugged.org/en/search/?q=binary+search

[100] https://www.instructables.com/Maze-Solving-Robot/  – uses Arduino
https://make.techwillsaveus.com/microbit/activities/microbot-maze-challenge  – uses Micro:Bit
https://www.raspberrypi.org/magpi-issues/MagPi51.pdf  (PDF) – uses a Raspberry Pi

[101] https://scratch.mit.edu/projects/248542678/