# Great Algorithms in Python

## Introduction

Welcome to Great Algorithms in Python!

This collection provides Python programs that implement the greatest algorithms. The collection is drawn from the algorithms described in my book Poems that Solve Puzzles: The History and Science of Algorithms. The book tales the stories of the inventors of the greatest algorithms and explains how the algorithms work. This new collection presents programs that execute the algorithms on today’s computers. The programs are written in the popular Python programming language. As well as reading the code, you can run the programs online. You can also experiment with the programs and share your programs with your online friends.

The Great Algorithms in Python collection is free. Each algorithm is listed below with a link to the related program and a reference to the section in the book. The programs are available on the Replit platform. You can read and run the programs on the Replit platform. The Replit platform is easy-to-use and free. If you are using a laptop or computer, Replit runs on your web browser (Chrome, Edge, Safari, or Firefox). There is no need to install additional software. If you are using a mobile phone or tablet, I recommend that you download and install the Mobile Replit app to your Android or iOS device.

To experiment with a program, you should sign up to Replit, copy my program to your account and modify your code. To create your own account, click on the Sign Up button and enter your details. To copy my code to your account, click on the Fork button. To change the code, click on the program's name in your account. This displays the program in the Workspace. The Files are listed to the left, the program in the Editor on the centre and a Console to the right. You can change the code in the Editor. When you are ready, you click on the Run button to execute the code. The output from the program is displayed on the Console. If there is an error, you receive a message. You make your program Public and can Publish it. You can Follow programs published by other coders. If you like the programs, please click on the Replit hearts.

You can click to my Replit profile at this link.

Enjoy the world of amazing algorithms and programs!

## 1. Simple Division by Two

A simple algorithm that divides a number by two. In the example, the program shares a packet of sweets between two friends.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Introduction, page 1.

## 2. Insertion Sort

The Insertion Sort algorithm organises lists of names or numbers into a specific order, such as alphabetical characters. The algorithm is easy to understand but is slow for sorting very large lists.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Introduction, page 3.

## 3. QuickSort

The QuickSort algorithm order lists of names or numbers very quickly. The clever algorithm was invented by the Englishman Tony Hoare in 1960.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Introduction, page 4.

## 4. The Size of a Cistern

Discovered on an ancient Old Babylonian clay tablet, the algorithm calculates the length and width of an underground cistern. It is thought that the algorithm was copied down from a textbook by a student around 3,600 years ago.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 1, page 13.

## 5. Heron’s Square Root Approximation

The algorithm approximates the square root of a number by refining estimates. It was first thought that the algorithm was originally invented 2,000 years ago by the Greek mathematician Heron of Alexandria. It is now thought that the Old Babylonians invented it 1,000 years before Heron.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 1, page 16.

## 6. Euclid’s Iterative Algorithm

Euclid’s algorithm determines the greatest common divisor (GCD) of two numbers. For example, the GSD of 18 and 12 is the number 6. The famous algorithm was invented by the great Greek mathematician around 2,300 years ago.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 1, page 20.

## 7. Euclid’s Recursion Algorithm

Euclid’s recursion algorithm also calculates the GCD of two numbers. However, the recursion version is viewed as one of the most beautiful algorithms.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 1, page 21.

## 8. Sieve of Eratosthenes

The Sieve of Eratosthenes algorithm quickly finds prime numbers. A prime is a whole number that cannot be exactly divided by any whole number other than itself and 1.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 1, page 22.

## 9. Archimedes' Pi Approximation

Archimedes, the famous Greek mathematician of shouting "Eureka!", invented an algorithm for estimating the value of Pi. Archeimedes' method stood as the best algorithm for calculating Pi for over a thousand years.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 2, page 27.

## 10. Fourier Transform

The 18th century French mathematician Jean-Baptiste Joseph Fourier invented the algorithm to split a signal into its component waveforms. The algorithm is used today in every computer and phone in the world.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 2, page 33.

## 11. Fast Fourier Transform

During the Cold War, James Cooley and John Tukey invented a fast algorithm for calculating the Fourier Transform. The algorithm was used to locate remote nuclear bomb tests from their seismic signals.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 2, page 37.

## 12. Lovelace's Bernoulli Numbers

Ada Lovelace wrote the first published program for a computer. She wrote the program for Charles Babbage's Analytical Engine. Lovelace's paper was published in 1842.

Click to read & run

The algorithm is explained in the book Poems that Solve Puzzles: The History and Science of Algorithms, Chapter 2, page 43.