# Simanaitis Says

On cars, old, new and future; science & technology; vintage airplanes, computer flight simulation of them; Sherlockiana; our English language; travel; and other stuff

# ALGORITHMS REDUX PART 1

BRIDGET KENDALL RECENTY observed on the BBC World Service that algorithms are “so fundamental to the way we live our lives today that one commentator has even gone as far as to say that, if every algorithm suddenly stopped working, it would be the end of the world as we know it.”

On September 16, 2021, “The Forum,” a BBC World Service regular feature, offered “Algorithms: From the Ancients to the Internet,” with Bridget Kendall chatting with three specialists. In the U.S., there’s UCLA’s Dr. Ramesh Srinivasen. Also in the U.S. is French scientist Dr. Aurélie Jean. In the U.K., there’s Warwick University’s Professor Emeritus Ian Stewart. Here are tidbits gleaned from this chat.

Etymology. The word “algorithm” comes from the name of a 9th-century Persian mathematician, Muhammad ibn Musa al-Khwarizmi, who wrote two important books of mathematics. One, written about 820 A.D., popularized the use of Hindu-Arabic numerals throughout the Middle East and Europe. Its Latin title is Algoritmi de numero Indorum,(extremely) loosely, “Al’s Hindi Numbers.”

His later treatise had the Arabic title al-Kitāb al-Mukhtaṣar fī ḥisāb al-Jabr wal-Muqābala, loosely, The Compendious Book on Calculation by Completion and Balancing. Our word “algebra” derives from “al-jabr,” literally, “the reunion of broken parts.” In today’s algebra, this relates to transforming elements from one side of an equation to the other.

Basics. An algorithm is a sequence of iterated instructions defining a process that solves a problem. These days, the process may be as simple as baking a cake, as complex as analyzing proteins.

Algorithms, though not so named, have been around for millennia. Clay tablets from 2500 B.C. Babylonia display mathematical exercises with algorithmically derived answers: Professor Stewart gives an example: “I found a stone but did not weigh it. Half the weight of the stone plus the square of the weight of the stone is 105. What does the stone weigh?”

The answer is 10. We’d think of solving the algebraic equation 1/2 X + X2 = 105.

Algorithms Today. Cell phones, credit cards, GPS, Internet search engines, e-mail, financial trades automobile software, traffic signals, and delivery vehicles all have underlying algorithms directing their operations. Specialists on “The Forum” discussed several different approaches, among them greedy, bubble sort, and brute force algorithms.

Local Optimization. Greedy algorithms seek local solutions. Wikipedia writes, “In many problems, a greedy strategy does not produce overall optimality, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.”

Greedy algorithms may be appropriate when the domain of possible choices is inordinately large: An optimized local solution may be better than none at all globally.

Tomorrow in Part 2, we’ll continue with additional tidbits gleaned from Bridget Kendall and her specialists. ds