Murat Durmus

10
Algorithms
That Dominate
The World
(with code samples)
“All models are wrong,
but some are useful.”
George E. P. Box
Preface ................................................................ xii
1. PageRank Algorithm ..........................................1
How PageRank Works .........................................2
Impact and Applications .....................................2
Challenges and Future Developments ................4
Advantages and Disadvantages ..........................4
Example Code: ....................................................5
2. RSA Algorithm .................................................10
How RSA Works ................................................11
Impact and Applications ...................................11
Challenges and Future Developments ..............12
Advantages and Disadvantages ........................13
Example Code: ..................................................14
3. Linear Programming ........................................20
How Linear Programming Works ......................21
Impact and Applications ...................................21
Challenges and Future Developments ..............22
Advantages and Disadvantages ........................23
Example Code: ..................................................24
4. Monte Carlo Algorithm ...................................29
How the Monte Carlo Method Works ...............30
Impact and Applications ...................................30
Challenges and Future Developments ..............31
Advantages and Disadvantages ........................32
Example Code: ..................................................33
5. Genetic Algorithm ...........................................38
How Genetic Algorithms Work .........................39

vi
 10 Algorithms That Dominate The World

Impact and Applications .................................. 39

Challenges and Future Developments .............. 40
Advantages and Disadvantages ........................ 41
Example Code: ................................................. 42
6. Fast Fourier Transform Algorithm .................. 49
How the Fast Fourier Transform Works ........... 50
Impact and Applications .................................. 50
Challenges and Future Developments .............. 51
Advantages and Disadvantages ........................ 51
Example Code: ................................................. 53
7. Support Vector Machine Algorithm ............... 57
How Support Vector Machines Work ............... 58
Impact and Applications .................................. 58
Challenges and Future Developments .............. 59
Advantages and Disadvantages ........................ 59
Example Code: ................................................. 61
8. Backpropagation Algorithm ........................... 65
How Backpropagation Works ........................... 66
Impact and Applications .................................. 66
Challenges and Future Developments .............. 67
Advantages and Disadvantages ........................ 67
Example Code: ................................................. 69
9. k-means Algorithm ......................................... 74
How the k-means Algorithm Works ................. 75
Impact and Applications .................................. 75
Challenges and Future Developments .............. 76
Advantages and Disadvantages ........................ 77

vii
10 Algorithms That Dominate The World

Example Code: ..................................................78

10. Apriori Algorithm ..........................................82
How the Apriori Algorithm Works .....................83
Impact and Applications ...................................83
Challenges and Future Developments ..............84
Advantages and Disadvantages ........................84
Example Code: ..................................................86
The Algorithmic Mirror: Reflections on Bias, Transparency, and
Humanity.............................................................91
The Path Forward: Towards an Ethical Algorithmic Future 92
Appendix: The Historical Backgrounds ................95
PageRank Algorithm ............................................96
RSA Algorithm ...................................................100
Linear programming ..........................................105
MONTE CARLO ALGORITHM .............................109
Genetic Algorithm .............................................113
The Fast Fourier Transform (FFT) Algorithm .....118
The Support Vector Machine (SVM) Algorithm.122
The Backpropagation Algorithm .......................127
k-means algorithm ............................................131
Apriori Algorithm ..............................................135
Glossary .............................................................141
References.........................................................145

viii
More Books by the Author: .............................. 151
Critical Thinking is Your Superpower ............... 152
Beyond the Algorithm: An Attempt to Honor the Human Mind
in the Age of Artificial Intelligence (Wittgenstein Reloaded)
.......................................................................... 153
The Cognitive Biases Compendium .................. 154
MINDFUL AI ...................................................... 155
INSIDE ALAN TURING: QUOTES & CONTEMPLATIONS 156

ix
Preface

Preface

In an era where data flows continuously and technology sets the

pace of progress, algorithms quietly orchestrate the modern
world. From directing our quest for knowledge to securing
communications to optimizing everyday decisions, algorithms
form the backbone of our digital society. This book invites readers
to explore the ingenious designs and profound impacts of ten of
the most influential algorithms of our time.

You'll encounter the brilliance of the PageRank algorithm that

revolutionized web search, the precision of RSA encryption
essential to securing digital transactions, and the practicality of
linear programming used to optimize various industries, among
many others. In addition, you will discover the stochastic insights
of Monte Carlo simulations, the biological inspiration behind
genetic algorithms, and the transformative power of machine
learning tools such as support vector machines and
backpropagation. Each algorithm represents a significant
achievement in human ingenuity, with applications across various
fields, including finance, healthcare, and artificial intelligence.
These algorithms come with practical code examples. The code
snippets serve as educational tools and provide a foundation for
further experimentation.

This book aims to demystify these technological marvels and

reflect on their implications. How do these algorithms shape our
daily lives, influence decision-making, and embody human values?
Equally important are the ethical considerations they raise –

xii
 Preface

questions of fairness, transparency, and possible unintended

consequences.

*10 Algorithms That Rule the World* is for anyone interested in

the mechanisms that drive the digital age. It offers insights into
the fundamental algorithms that have quietly revolutionized our
world. By exploring their workings and applications, you may gain
a deeper appreciation for the science behind the everyday
wonders of our connected society.

Murat Durmus (January 2025)

Note:

Transformers are not an algorithm but an architecture that relies on

foundational algorithms (like backpropagation and gradient descent)
for training. They represent a blueprint for how neural networks can be
structured to handle complex tasks effectively, particularly those
involving sequential data. Their innovation lies in their ability to capture
global relationships within data efficiently, making them the backbone
of modern AI advancements.

xiii
 6. Fast Fourier Transform Algorithm

6. Fast Fourier Transform Algorithm

The Fast Fourier Transform (FFT) is an efficient

algorithm to compute the Discrete Fourier Transform
Definition (DFT) and its inverse, enabling the transformation of
a signal from the time domain to the frequency
domain.

Signal Processing, Communications, Image

Main Domain
Processing, and Scientific Computing.

Numerical data, typically represented as discrete

Data Type
sequences of time-domain or spatial-domain signals.

Deterministic algorithm; applies a divide-and-

Learning
conquer strategy to reduce computational
Paradigm
complexity.

High explainability; the underlying mathematical

Explainability principles (Fourier transforms) are well-understood,
and the algorithm's steps are clear and interpretable.

The Fast Fourier Transform (FFT) is an algorithm that computes

the Discrete Fourier Transform (DFT) of a sequence or its inverse
(IDFT) 20. The DFT decomposes a sequence of values into

49
 6. Fast Fourier Transform Algorithm

components of different frequencies, which is helpful in many

fields, including signal processing, image analysis, and data
compression. The FFT significantly reduces the computational
complexity of computing the DFT, making it practical for real-
world applications 21.

How the Fast Fourier Transform Works

The FFT achieves its speed by factorizing the DFT matrix into a
product of sparse (mostly zero) factors 20. This factorization
reduces the computations required to compute the DFT from
O(n²) to O(n log n), where n is the data size. This difference in
speed can be enormous, especially for long data sets where n may
be in the thousands or millions.

Impact and Applications

● Signal Processing: Analyzing and processing signals in audio,

video, and communication systems. This involves decomposing
signals into their frequency components to identify patterns,
filter noise, and extract meaningful information.
● Image Analysis: Analyzing and processing images in medical
imaging, computer vision, and pattern recognition. This
involves transforming images into the frequency domain to
enhance features, remove noise, and perform image
compression.
● Data Compression: Compressing audio, video, and image files
for efficient storage and transmission. This involves removing
redundant information and representing the data more
compactly.

50
 6. Fast Fourier Transform Algorithm

● Scientific Computing: Solving differential equations, simulating

physical systems, and analyzing scientific data. This involves
using the FFT to perform efficient calculations and analyze
data in the frequency domain.

Challenges and Future Developments

● Non-stationary Signals: The FFT is most effective for stationary

signals, where the statistical properties do not change over
time. Analyzing non-stationary signals, where the frequency
content changes over time, requires more sophisticated
techniques.
● Real-time Processing: Performing FFT in real-time requires fast
hardware and optimized algorithms, especially for high data
rates or large FFT sizes. This can be challenging in applications
where latency is critical.
● Memory Requirements: Storing and processing large datasets
for FFT can require significant memory resources. This can be a
limiting factor in applications with limited memory capacity.

Advantages and Disadvantages

Advantages Disadvantages
1. Efficiency: Reduces the 1. Requires Power-of-Two Length:
computational complexity of Many FFT implementations require
calculating the Discrete Fourier the input size to be a power of two,
Transform (DFT) from O(n²) to which may necessitate padding and
O(n log n) introduce inefficiencies.
2. Widely Used: Applicable in 2. Fixed Frequency Resolution: The
diverse fields such as signal resolution is determined by the

51
6. Fast Fourier Transform Algorithm

Advantages Disadvantages
processing, image processing, length of the input signal, limiting
and scientific computing. flexibility.
3. Accurate: Provides high 3. Assumes Periodicity: Assumes the
precision for transforming input signal is periodic, which can
signals between time and introduce artifacts (e.g., spectral
frequency domains. leakage) for non-periodic signals.
4. Versatile: Can be applied to
4. Sensitivity to Noise: FFT can
a variety of transformations,
amplify noise present in the signal,
including 1D, 2D, and
leading to less reliable results for
multidimensional Fourier
noisy data.
transforms.
5. Parallelizable: Well-suited 5. Complex Number Output:
for parallel computation, Produces complex numbers in the
further speeding up large-scale frequency domain, requiring
transformations. additional steps for interpretation.
6. Real-Time Processing: Ideal
6. Memory Intensive: Requires
for applications requiring real-
significant memory for large
time signal analysis, such as
datasets, especially for
audio and communications
multidimensional FFTs.
systems.
7. Easy to Implement: Standard 7. Boundary Effects: Can introduce
libraries and tools make it edge effects when analyzing finite-
straightforward to use in most length signals without proper
programming languages. windowing.
8. Handles Large Data 8. Specialized Hardware May Be
Efficiently: Capable of Needed: Real-time applications
processing large datasets in often require dedicated hardware
manageable timeframes. like DSPs (Digital Signal Processors).

52
 6. Fast Fourier Transform Algorithm

Example Code:
import numpy as np
import matplotlib.pyplot as plt

def generate_signal(frequencies, sampling_rate,

duration):
"""
Generate a signal with given frequencies.

Parameters:
frequencies (list): List of frequencies to include in
the signal.
sampling_rate (int): Number of samples per second.
duration (float): Duration of the signal in seconds.

Returns:
tuple: (time, signal) where time is the time array
and signal is the combined signal.
"""
time = np.linspace(0, duration, int(sampling_rate *
duration), endpoint=False)
signal = np.sum([np.sin(2 * np.pi * freq * time) for
freq in frequencies], axis=0)
return time, signal

def plot_signal(time, signal, title="Signal"):

"""
Plot a time-domain signal.

Parameters:
time (numpy.ndarray): Time array.
signal (numpy.ndarray): Signal array.
title (str): Title of the plot.
"""
plt.figure(figsize=(10, 4))
plt.plot(time, signal, label="Signal")
plt.title(title)
plt.xlabel("Time [s]")
plt.ylabel("Amplitude")
plt.grid()

53
6. Fast Fourier Transform Algorithm

plt.legend()
plt.show()

def plot_fft(signal, sampling_rate):

"""
Plot the FFT of a signal.

Parameters:
signal (numpy.ndarray): Signal array.
sampling_rate (int): Sampling rate of the signal.
"""
# Perform FFT
fft_result = np.fft.fft(signal)
fft_freqs = np.fft.fftfreq(len(signal),
d=1/sampling_rate)

# Only take the positive half of the spectrum

positive_freqs = fft_freqs[:len(fft_result)//2]
positive_magnitude =
np.abs(fft_result[:len(fft_result)//2])

# Plot the FFT

plt.figure(figsize=(10, 4))
plt.plot(positive_freqs, positive_magnitude,
label="FFT Magnitude")
plt.title("Fast Fourier Transform (FFT)")
plt.xlabel("Frequency [Hz]")
plt.ylabel("Magnitude")
plt.grid()
plt.legend()
plt.show()

if __name__ == "__main__":
# Parameters
frequencies = [5, 50, 120] # Frequencies in Hz
sampling_rate = 1000 # Sampling rate in Hz
duration = 2 # Duration in seconds

# Generate the signal

time, signal = generate_signal(frequencies,
sampling_rate, duration)

54
 6. Fast Fourier Transform Algorithm

# Plot the time-domain signal

plot_signal(time, signal, title="Time-Domain Signal")

# Plot the frequency-domain signal using FFT

plot_fft(signal, sampling_rate)

Explanation:

1. Signal Generation:

o A time-domain signal is created by summing sine

waves of specified frequencies.

o The generate_signal function uses numpy to create

the time array and calculate the signal.

2. Fast Fourier Transform (FFT):

o The FFT is used to convert the time-domain signal

into its frequency-domain representation.

o numpy.fft.fft computes the FFT, and

numpy.fft.fftfreq calculates the corresponding
frequencies.

3. Plotting:

o Time-Domain Plot: Shows the original signal over

time.

55
6. Fast Fourier Transform Algorithm

o Frequency-Domain Plot: Displays the magnitude of

the FFT, which highlights the frequencies present in
the signal.

56
 The Algorithmic Mirror: Reflections on Bias, Transparency, and Humanity

The Algorithmic Mirror: Reflections on Bias,

Transparency, and Humanity

We stand at the precipice of a new era, where algorithms,

intricate webs of logic and code, are increasingly shaping the
contours of our world. These digital constructs hold immense
promise, offering the potential to revolutionize fields from
healthcare to finance, ushering in unprecedented advancements.
Yet, as we entrust more of our lives to these invisible architects,
we must pause and contemplate the profound ethical implications
that arise from their pervasive influence. Algorithms, while
seemingly neutral in their mathematical essence, are far from
value-free; they are, in essence, a reflection of ourselves,
mirroring our biases, our prejudices, and our aspirations.

One of the most pressing concerns is the potential for these

powerful tools to exacerbate existing social inequalities. Like a
distorting lens, algorithms trained on historical data can
inadvertently amplify the inequities embedded within that data,
perpetuating cycles of discrimination. In the hallowed halls of
employment, algorithms meant to streamline hiring may unfairly
disadvantage certain groups in their cold calculation, echoing the
biases that have long haunted the workplace. Similarly, in the
realm of finance, the very algorithms designed to assess risk may,
in their reliance on past patterns, deny opportunities to
individuals from marginalized communities, further entrenching
economic disparities.

91
The Algorithmic Mirror: Reflections on Bias, Transparency, and Humanity

Beyond social justice, algorithms cast a long shadow over the

fundamental right to privacy. These digital entities often thrive on
a voracious diet of personal data, raising profound questions
about surveillance, data security, and the potential for
manipulation. We must ask ourselves: how can we ensure that in
our pursuit of efficiency and progress, we do not sacrifice the
sanctity of individual privacy at the altar of algorithmic
optimization? How do we safeguard sensitive information from
misuse, ensuring that the digital tapestry woven by algorithms
does not ensnare us in a web of control?

We must be wary of the subtle yet insidious curating of our feeds,

which can inadvertently construct echo chambers, feeding us only
information confirming the ways in which algorithms can shape
our perceptions and manipulate our choices. Social media,
governed by algorithms that curate our feeds, can inadvertently
construct echo chambers, feeding us only information that
confirms our existing beliefs. While seemingly innocuous, this
"filter bubble" effect can lead to intellectual isolation, societal
polarization, and a profound erosion of informed nuanced
discourse.

The Path Forward: Towards an Ethical Algorithmic Future

The challenges posed by this new era are as multifaceted as the

algorithms themselves. We are called upon to navigate this
uncharted territory with wisdom, foresight, and a deep
commitment to ethical principles. Our task is to forge a path that
allows us to harness the transformative power of algorithms while
mitigating their potential harms. This necessitates:

92
PageRank Algorithm

PageRank Algorithm

The PageRank algorithm, the foundational technology behind

Google's search engine dominance, has a surprisingly rich and
somewhat contested history. While often attributed solely to
Google's founders, Larry Page and Sergey Brin, its roots lie in
earlier work on citation analysis and social network analysis.

Early Influences (Mid-20th Century):

• Citation Analysis (1950s-1960s):

o Eugene Garfield (Science

Citation Index): Garfield pioneered
the field of bibliometrics with the
Science Citation Index (SCI) in the
1960s. The SCI tracked citations
between scientific papers, and the
idea that highly cited papers are more important is
a fundamental precursor to PageRank.

o Impact Factor: Garfield's work led to the

development of the "impact factor," a metric for
assessing the importance of academic journals
based on the frequency with which their articles are
cited. This concept of using citations to measure
influence is a clear predecessor to PageRank's link-
based ranking.

• Social Network Analysis (Sociometry):

96
 PageRank Algorithm

o Jacob Moreno (1930s):

Moreno's work on sociometry
involved mapping social
relationships and influence within
groups. His techniques for
analyzing social networks, though
not directly linked to PageRank,
share the concept of using relationships (links) to
determine importance or authority.

o Katz Centrality (1953): Developed by Leo Katz, this

measure of a node's influence in a network
considers not only direct connections but also
indirect connections, weighted by a decay factor.
This idea of influence propagating through a
network is similar to how PageRank works.

Precursors to PageRank (1970s-1990s):

• Hypertext Search Engines (Early 1990s): Before Google,

early search engines like Archie, Veronica, and Jughead
primarily relied on keyword matching and directory
structures. They lacked sophisticated methods for ranking
the relevance of web pages.

• The Hyper Search Engine (1996): Massimo Marchiori

developed the "Hyper Search" engine while at the
University of Padua. His algorithm used the relationship
between individual pages on a website to rank the
website's overall importance. Marchiori later argued that

97
 The Fast Fourier Transform (FFT) Algorithm

• Unpublished Manuscript: The earliest known

explicit description of an FFT algorithm was found
in the unpublished work of Carl Friedrich Gauss in
1805. He developed it to interpolate the orbits of
asteroids from sample observations. His method
was quite similar to the later Cooley-Tukey
algorithm but was not published during his
lifetime and was only rediscovered after the widespread
adoption of the FFT in the 1960s. This work also predated
Fourier's publication on harmonic analysis in 1807.

19th and Early 20th Century Developments:

• Fourier's Work (1807-1822): Joseph Fourier's

groundbreaking work on the analytical theory of
heat introduced the concept of representing
functions as a sum of trigonometric functions
(Fourier series). This laid the mathematical
foundation for the later development of the FFT.

• Limited Practical Use: While the theoretical groundwork

was in place, the practical application of Fourier analysis
remained limited due to the substantial computational
effort required for calculating the Fourier coefficients. The
discrete Fourier transform (DFT), though conceptually
known, was computationally very expensive for large
datasets.

• Runge and König (1924): Carl Runge, along with his

student, contributed improvements to the efficiency of
calculating Fourier series, foreshadowing the FFT.

119
 Glossary

Glossary

Algorithm: A step-by-step procedure for solving a problem or

performing a task, often implemented in software.

PageRank: An algorithm developed by Larry Page and Sergey Brin

to rank web pages by their importance, based on the number and
quality of backlinks.

RSA Algorithm: A cryptographic algorithm named after Rivest,

Shamir, and Adleman. It uses public and private keys for secure
data transmission.

Linear Programming: A mathematical optimization technique

used to achieve the best outcome in a system modeled with linear
relationships, subject to constraints.

Monte Carlo Algorithm: A method using random sampling to

solve problems that might be deterministic in principle but are
computationally complex.

Genetic Algorithm: An optimization algorithm inspired by the

process of natural selection, involving mutation, crossover, and
selection.

Fast Fourier Transform (FFT): An efficient algorithm to compute

the Discrete Fourier Transform (DFT), widely used in signal
processing.

141
Glossary

Support Vector Machine (SVM): A supervised machine learning

algorithm used for classification and regression by finding the
optimal hyperplane.

Backpropagation: A key algorithm for training neural networks by

propagating error gradients backward to update weights.

k-means Algorithm: An unsupervised machine learning algorithm

for clustering data points into groups based on proximity to
cluster centroids.

Apriori Algorithm: A popular algorithm used in data mining for

finding frequent itemsets and deriving association rules.

Damping Factor: In PageRank, the probability of continuing to

follow links rather than jumping randomly to another page.

Public-Key Cryptography: A cryptographic system using a pair of

keys—one public and one private—for secure data transmission.

Hyperplane: A decision boundary in SVMs that separates data

points into different classes.

Centroids: Points representing the center of clusters in k-means

clustering.

Fitness Function: In genetic algorithms, a function that evaluates

how close a solution is to the optimal solution.

Elbow Method: A technique for determining the optimal number

of clusters in k-means clustering by analyzing the variance
explained.

142
 References

References

1. PageRank - Wikipedia, accessed December 28, 2024,

https://en.wikipedia.org/wiki/PageRank

2. Page Rank – The History and Evolution of Google's Website Ranking Algorithm -
Copymate, accessed December 28, 2024, https://copymate.app/blog/multi/page-
rank-the-history-and-evolution-of-googles-website-ranking-algorithm/

3. PageRank Algorithm: How Does it Work and What is Its Impact on SEO?, accessed
December 28, 2024, https://www.internallinkjuicer.com/hub/seo/pagerank/

4. Promise and Pitfalls of Extending Google's PageRank Algorithm to Citation

Networks - PMC, accessed December 28, 2024,
https://pmc.ncbi.nlm.nih.gov/articles/PMC6671494/

5. RSA (cryptosystem) - Wikipedia, accessed December 28, 2024,

https://en.wikipedia.org/wiki/RSA_(cryptosystem)

6. www.veritas.com, accessed December 28, 2024,

https://www.veritas.com/information-center/rsa-
encryption#:~:text=It%20allows%20the%20encryption%20and,signature%20using%2
0a%20public%20key.

7. Linear programming - Wikipedia, accessed December 28, 2024,

https://en.wikipedia.org/wiki/Linear_programming

8. Linear Programming: Definition, Formula, Examples, Problems - GeeksforGeeks,

accessed December 28, 2024, https://www.geeksforgeeks.org/linear-programming/

9. corporatefinanceinstitute.com, accessed December 28, 2024,

https://corporatefinanceinstitute.com/resources/career-map/sell-side/capital-
markets/what-are-algorithms-
algos/#:~:text=Algorithms%20are%20introduced%20to%20automate,timing%2C%20
and%20other%20mathematical%20models.

10. 10 Algorithms that Have Changed the World | by Seattle Web Design, accessed
December 28, 2024, https://webdesignseattle.medium.com/10-algorithms-that-
have-changed-the-world-541ee82adcc6

145
References

11. What Is The Algorithmic Economy - Ian Khan "The Futurist" - CNN, BBC,
Bloomberg Featured Keynote Speaker covering AI, Innovation, Leadership, accessed
December 28, 2024, https://www.iankhan.com/what-is-the-algorithmic-economy/

12. Economic Implications of Algorithmic Trading, accessed December 28, 2024,

https://gjle.in/2024/03/31/economic-implications-of-algorithmic-trading/

13. Monte Carlo method - Wikipedia, accessed December 28, 2024,

https://en.wikipedia.org/wiki/Monte_Carlo_method

14. Monte Carlo Simulation: What It Is, How It Works, History, 4 Key Steps -
Investopedia, accessed December 28, 2024,
https://www.investopedia.com/terms/m/montecarlosimulation.asp

15. Monte Carlo simulations will change the way we treat patients with proton
beams today - PMC, accessed December 28, 2024,
https://pmc.ncbi.nlm.nih.gov/articles/PMC4112394/

16. How Medical Treatment Algorithms Are Shaping the Healthcare Industry - IRIS
retinal screening, accessed December 28, 2024,
https://retinalscreenings.com/blog/medical-treatment-algorithms/

17. Genetic algorithm - Wikipedia, accessed December 28, 2024,

https://en.wikipedia.org/wiki/Genetic_algorithm

18. Genetic Algorithm Applications in Machine Learning - Turing, accessed December

28, 2024, https://www.turing.com/kb/genetic-algorithm-applications-in-ml

19. Genetic algorithms and deep learning strengths and limits - Lumenalta, accessed
December 28, 2024, https://lumenalta.com/insights/genetic-algorithms

20. Fast Fourier transform - Wikipedia, accessed December 28, 2024,

https://en.wikipedia.org/wiki/Fast_Fourier_transform

21. Fast Fourier Transform Explained | Built In, accessed December 28, 2024,
https://builtin.com/articles/fast-fourier-transform

22. Support Vector Machine (SVM) Algorithm - GeeksforGeeks, accessed December

28, 2024, https://www.geeksforgeeks.org/support-vector-machine-algorithm/

146