*This is the second article in a seven-part series on Algorithms and Computation, which explores how we use simple binary numbers to power our world. The first article, *How Algorithms Run the World We Live In*, can be found here.*

The oldest algorithms ever recorded were on ancient Babylonian tablets dating to about **1,800 BCE**, explaining the specific procedures to compute different values like square roots and other measures. We still use one of the Greek mathematician **Euclid’s** most famous algorithms—his method for finding the **greatest common divisor**, first formulated around **300 BCE**—in programming today because of its **elegant simplicity**.

It wasn’t until the age of computers however that algorithms really began to take a mathematical approach to seemingly non-mathematical problems, and these modern algorithms are some of the most important solutions to problems currently powering the world’s most widely used systems.

## PageRank

Having discussed **PageRank** briefly in the first article in this series, Google’s **PageRank** algorithm is a great place to start, since it helped turn Google into the internet giant it is today.

**RELATED: GOOGLE SEARCH TIPS AND TRICKS TO FIND EXACTLY WHAT YOU WANT**

**PageRank** was the first algorithm **Larry Page** and **Sergei Brin** developed to index and rank web pages on the internet in the late 1990s, eventually using it to power their new Google search engine.

The essential feature of **PageRank** is that it determines a score for how authoritative a page is based on the authority scores of the pages that link to it. More authoritative pages linking to a page in turn confer a greater measure of authority to that page than others, so in this way, the people who write the content on the page and link to other pages effectively tell Google which pages carry more weight than others.

**PageRank** was revolutionary when it was introduced and quickly blew other search engines out of the market. **PageRank** is so important that an entire industry developed around the algorithm itself: **Search Engine Optimization**. The **PageRank** algorithm so thoroughly established Google's dominance as the only search engine that mattered that the word *Google* officially became a verb less than **eight years** after the company was founded. Even though **PageRank** is now only one of about **200** measures Google uses to rank a web page for a given query, this algorithm is still an essential driving force behind its search engine.

## Key Exchange Encryption

How do you secure information that is effectively read out over a loudspeaker on a street corner that everyone can hear? That is the challenge when trying to protect network communication traffic transmitted over public communication lines; anyone can intercept these communications en route and read the data. Code ciphers, which convert each byte of data into a different byte of data based on some programmatic formula, are the obvious answer. But those won't work when one party doesn't know which cipher the other party is using, and most secure communications happen between parties who have had no prior contact, so have no means of agreeing to one beforehand.

The **Key Exchange Encryption algorithm** does the seemingly impossible by establishing a single, shared mathematical secret between two parties, who don't even know each other, and is used to **encrypt the data** as well as **decrypt it**, all over a **public network** and without anyone else being able to figure out the secret. Here's how it works:

***I choose a number and you choose a number and we don't share these numbers with anyone (our private keys). *One of us announces a random number over a public channel which anyone can read (the public key). *I apply my private number as the exponent to the public number and get the result, and you do the same. *We then swap our different results so that you have my result and I have yours, over the public channel. *I apply my private number as the exponent to the result you broadcast over the public channel and obtain a value, and you do the same.**

***That value will be the same for the both of us and we use that value to encrypt our communications.**

Because none of us ever publiclly discloses our own **personal private key**, it is practically impossible for anyone who sees this information being passed to determine what value we are using to **encrypt our communications**. The process that produces the shared secret relies on two basic ideas. First, **(a ^{m})^{n}** and

**(a**will give you the exact same answer. The private keys are

^{n})^{m}**m**and

**n**and the public key is

**a.**This will always work.

But what if you're watching all of this as a third party trying to intercept the messages being passed? The only **unencrypted information** being passed is the **public key,** **a,** and the **two results**, **a ^{m }**and

**a**except the

^{n},**two results**don't look this way to you; you just see two very large seemingly random numbers that you know are somehow mathematically tied to the public key

**a**. Without knowing

**m**or

**n**, which is

**never shared**on the

**public channel**, the only way to find out the two

**private keys**that

**produce the cipher**is the

**inverse**process to

**exponentiation**, which is finding the

**discrete logarithm**of either

**m**or

**n**, and there is

**no currently known**way for a

**classical computer**to do this before the Sun explodes and takes us all out in a

**few billion years**.

Why it's so hard is the subject of another article, but it genuinely is that difficult, which makes it perfect for **public encryption**. While not commonly used on its own anymore, the public-private key structure of the **Key Exchange algorithm** is an essential feature of more advanced encryption schemes like **RSA encryption**.

## Backpropagation

**Backpropagation** through a **neural network** is one of the most important algorithms invented in the **last 50 years**.

**Neural networks** operate by feeding input data into a network of **nodes** which have connections to the **next layer** of **nodes**, and **different weights** associated with these connections which determines whether to pass the information it receives through that connection to the next layer of nodes. When the information passed through the **various so-called "hidden" layers** of the network and comes to the **output layer**, these are usually different choices about what the neural network believes the **input** was. If it was fed an **image of a dog**, it might have the options **dog**, **cat**, **mouse**, and **human infant**. It will have **a probability for each** of these and the **highest probability** is chosen as the **answer**.

This is where **backpropagation** comes in. **Backpropagation** is the propagation of the error back through the neural network and over the connections that produced the incorrect answer. As it goes, it will go back and make adjustments to all of those connections and decrease the **weight** given to that connection. Over time, a **neural network** is able to learn what something is by learning what something **is not** and converging on the correct answer.

In this way, **neural networks** can be trained to recognize what a face looks like, a voice sounds like, and what movies you might like based on the movie you last watched. Without **backpropagation**, **deep-learning neural networks** wouldn’t work, and without these **neural networks**, we wouldn’t have the rapid advances in **artificial intelligence** that we’ve seen in the last decade.

## Compression

If you wanted to compress a file to make it smaller and easier to manage over a network or to save on disk space and you look at the bytes of data in front of you, where would you even begin? How do you make bytes smaller, so they take up less space but enable you to decompress it afterward to recover what you had at the start?

Several variations on **compression** exist, but they almost all rely on a **similar trick;** they use **references** and **offsets** instead of the **actual data itself** to represent the data using **less space**.

Let's say you had a string of characters you wanted to compress, **ABBCABBCABACABACABACDDDBDB**, which is **26 characters** long. Another way to write this is **ABBC2ABAC3D2DB2**, where the numbers after a string of characters tell you how many times that string needs to be printed. The compressed string is now only **15 characters** long.

That may not seem like much, but we’ve just reduced the amount of memory this string needs by just over **40 percent**. When you have files that are gigabytes in size, that **40 percent** is huge. Now, not all data can be compressed like this, and the efficiency of the compression varies, but compressing as much data as we can as often as we can keeps **communications networks** and **hard disks** from being **clogged up** with a **massive amount of repetitive bloat**. This basic idea behind **file compression** has empowered **streaming movies**, **streaming music**, **online video games**, and just about everything else, honestly. **Compression** is everywhere, and it is **essential** to the **efficient transmission** and **storage** of information.

## Searching and Sorting Algorithms

**Searches and Sorts** are a special form of algorithm in that there are many very different techniques used **to sort** a data set or **to search** for a specific value within one, and no single one **is better** than another **all of the time**. The **quicksort** algorithm might be better than the **mergesort** algorithm if **memory** is a factor, but if memory is not an issue, **mergesort** can sometimes be faster, and anything is better than **bubblesort**.

The same applies when you have **to search** through a data set for a specific value. On **a perfectly sorted list**, like a dictionary, a **binary search** is the fastest way to get what you want, but if you wanted to find **the longest word** in the dictionary or an unsorted random stream of words read in from **a million articles** downloaded from the Internet, then the **heapsort** doubles as your **search algorithm**, since **the highest value**—or **lowest**, if that's what you are looking for—in a data set **will always be** at the **top of the heap**.

The type of search needed will **always depend** on the **data structure** you're searching through (**lists, trees, graphs**, etc), but if you have a program that does anything useful with data, it is guaranteed that it will be using **a search** and **a sort algorithm** somewhere in its code. They all matter and programmers use **all of them**, **all the time**, and they form the foundation on which **data structures** and more **advanced algorithms** are built.

## Dijkstra's Shortest Path

**Dijkstra's Shortest Path algorithm** is **a search algorithm** for **graphs**, but it bears special mention, because it isn't like **other search algorithms**.

According to Dijkstra himself, in 1959 the computer scientist **Edsger Dijkstra** was sitting with his fiance somewhere in the Netherlands drinking coffee when he wrote up an algorithm that could show the power of the computer system he was working on to a general, non-computing audience in a way that they could understand.

He plotted out 64 cities on **a graph**, with each city represented by a node and drew various **paths**, which are technically known as **edges**, between them. He labeled one node **Rotterdam** and another node **Groningen** and designed an algorithm that found **the shortest path** between the **two nodes**. This is done by starting at **a source node** and having it find **the shortest path** between that node and **every other in the graph**, stopping once it reaches the **destination node**.

He almost certainly didn't think he was creating what would become one of the **most widely used algorithms** in the world, but in that **20 minutes** in **1959**, **Dijkstra** enabled everything from **GPS routing** on our phones, to **signal routing** through telecommunication networks, and any number of time-sensitive **logistics challenges **like shipping a package across country. As **a search** algorithm, **Dijkstra's Shortest Path** stands out more than the others just for **the enormity** of the technology that relies on it.

## TCP/IP Routing Protocol Algorithms

In case you've never seen it, that is **the Internet**. At least that's how **it sees itself**, anyway.

When **the Internet** began, the standards for the **transmission control protocol/Internet protocol (TCP/IP)** were basically brand new and while mathematically sound, the **algorithms** at the heart of the standard **Internet protocol** wasn't build with the unfathomable amount of traffic it has to manage in mind. One inefficient **algorithm** could have kneecapped **the Internet** before it really got going.

Fortunately for us, as **the Internet** expanded into every area of our lives, the **first initial** **decisions** that make up **TCP/IP** would turn out to be vital to the **successful operation** of the **entire network** as the **traffic exploded** beyond anyone’s wildest expectations.

One of the **most critical** of these decisions was which algorithm to use to route data packets, the actual information flowing through the Internet that we send and receive. The two most widely used by the Internet, the **Distance-Vector Routing Protocol Algorithm (DVRPA)** and the **Link-State Routing Protocol Algorithm (LSRPA)** are the **two most essential algorithms** we use **every day** as they efficiently **route data traffic** between the **billions of connected networks** that make up **the Internet**.

**DVRPA** works by finding the **shortest distance** between **the source** and **the destination** networks. It can use any **number of metrics** to calculate this but it will usually use something very simple like the number of router and server **"hops"** it must perform along the way. The simplicity is what matters in **DVRPA**.

**Routers** using this algorithm **keep a record** of **all known networks** on **a table** along with **the distance** to each one. Whenever this **router** forms a **new connection** to another network, usually called **neighbors** or **peers**, it passes them this **table** which that **peer** uses to update **its table** before passing **its updated table** to **any network** it is **already connected to** and so on. This way, changes **quickly propagate** throughout these connections so that every network knows how far it is to any other network on **the Internet**. While this doesn't guarantee the fastest connection, it is very quick and not very complicated to work out, so overall, it has operated pretty well with modifications to improve its efficiency.

**LSRPA** meanwhile operates in essentially the same way, but **routers** running the **LSRPA** **algorithm** keep **a map** the entire **Internet** that it can connect to and **routinely tests** different connections and **analyzes them** to determine the **more realistic cost** of that connection in terms of **computation**, **time**, **etc**. Like **DVRPA**, whenever it establishes a connection, it passes along **its map** to the network it connects to, so that changes to the network **propagate** throughout, giving **routers** using the algorithm a much more **realistic picture** of the various connections.

While it is more likely to find the **most efficient route more often**, it is more **computationally heavy** and isn't as well-established as **DVRPA**. As computer hardware improves, however, and **new equipment** replaces the **older network nodes**, more of **the Internet** will be able to manage running **LSRPA**, improving **the efficiency** of the entire **Internet** in the process.

The **issue of efficiency** doesn't just relate to the **hardware **however. The **efficiency of the various algorithms** can make or break a system. Fortunately, we know how to measure **the efficiency of algorithms** with mathematical precision, allowing us to find the **right algorithm** for the **right problem**.

*The thirs part of our series on Algorithms and Computation, *Time Complexity: Why Some Algorithms Run for Billions of Years*, can be found here.*