Good Ol' Algorithms

Did you know it is estimated people make 35,000 decisions per day! Most of these decisions are binary, but some of these involve a multi-step algorithm. According to Wikipedia, an algorithm “ is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation.” Following this, you may use an algorithm for how to cook the family chicken recipe or an algorithm that dictates what you wear for special occasions (don't forget the pocket square). There are several elegant computer algorithms that most of us use daily or weekly without even realizing it. How does Uber find the shortest path to your destination? Use Dijkstra’s. Ever used DocuSign to sign forms online? Check out public-key encryption and RSA. How about the optimal way to pack your grocery bags? Dynamic programming is the way to go. Can you categorize the difficulty of a problem? Big O notation to the rescue. Here are a couple of algorithms I’ve found especially interesting.

To start, here’s a problem. Given an array of sorted increasing numbers that you don't know the size of, how would you find the index of the desired number in linear time? As an example, maybe number 234,541 is at index 14,632, how do you find this? The first approach would be to start at the beginning of the list and then continue scanning the list until you reach the desired number. However, given that the list is infinite, or we don't know the end, the worst case would be that this takes an infinite amount of time. Feel free to think about this for a couple of minutes before I give you the answer…

Okay ready? 

First, we’ll use exponential search to find a sub-array that we’ll then use binary search on. To start, check index 1 to determine if this number is what we are looking for or is greater than the number we are looking for. If this is true, return the index, 1 since there is only one number. Otherwise, increment the index by a factor of two and check the element at index 2 if it is equal to or greater than the number we are looking for. If it is greater, then we will perform binary search using the previous index and the current index. However, if this is not the number we are looking for, check the element at index 4. Not the number or lower than our number? Check element at index 8, 16, 32, 64, 128, 256, 512, 1028 (2^4, 2^5, 2^6) ...etc. Once we’ve found the desired number, or a number larger, we move to binary search. This step takes O(log n) time.

FIgure 1. Exponential search on an array with number target 6

Once we’ve found an element that is larger than the number we are searching for, we perform binary search on the subarray. For example, if we looked at index 64, and the number at that location was 212 which is greater than the number we are searching for, 85. Then we know that the number 85 is between the number at the previous index 32, let’s say 50, and index 64, number 212. This gives us the lower and higher sections of the array to search by cutting each side in half until we find our desired number 85. This step takes O(log n) time as well. 

Figure 2. Binary search on an array with target 20

We just saw that exponential search takes O(log n) and binary search takes O(log n) which means the combination, O(log n) + O(log n) = O(log n)! Therefore, we can search an array that we don't know when it ends of increasing sorted numbers in sub-linear time. 

The second algorithm to briefly mention is RSA which is a form of public-key cryptography, or a way to send encrypted messages. Public-key encryption differs from private-key methods where both the sender and receiver have the same key to encode and decode a message. As an example, let’s say you wanted to send a message to your friend Mckenzie and you were going to rotate the letters two forward in the alphabet for that message. So the letter a -> c, b ->d, c ->e ...etc. The ‘private key’ in this example is that mechanism for deciphering the letters back to the original. Now the question becomes, how do you deliver this ‘private key’ to McKenzie? If you call them, someone could be listening on the other line. If you send them an email, someone could intercept the email. If you mail it, someone could read the message. Therefore, the best way to deliver this ‘private key’ would be in person.

Now, this is all well and good, but what if they live a 16-hour flight away and you need to send her a message in the next 10 minutes? Or you have 10,000 keys to manage. This is where public-key encryption comes to the rescue! The underlying assumption of public-key methods, such as RSA, is that you can generate a public key that is impossible for someone else to use to decrypt a given message even if they know what the key is. How to do this? Well, first we assume that factoring large numbers into prime numbers is hard for computers. Therefore, if we take two large prime numbers and multiply them together, we can create a public key that everyone can see but only the intended recipient can use. Then, you send this public key to your intended recipient and you can send private messages all day without worrying about who can see either the encrypted message or the public key!

Figure 3. Generating a public-key

Thanks for reading!