Introduction to Algorithms

This series will be covering the introduction of algorithms and their application.

Why

  • Anywhere where realtime results want to be found quick. I want fassssst :)
  • Efficiently calculating and handling the vast amount of data.
  • Vast amount of twitter feed
  • Sensor data
  • Machine Learning model training
  • Database queries

If you are thinking that you are never gonna touch on these things. It might be true, but to have a basic understanding of algorithms will give much sense for dealing with for loops across anything you do.


Algorithms can be traced back to the 9th century of a famous mathematician see history of algorthms. Nowadays everyone talks about algorithms, which is a fancy name of saying a set of intructions to follow. Given today, should not computational power overcome the means to calculate anything. Previously 1000 characters were seen as "big" data. If we had let's say a string of 1 million characters; the computer today would be able to look through that in seconds. However what happens when we deal with all of the worlds roads or the blockchain of a specific cryptocurrency, suddenly efficiency becomes vital.

Study of algorithms is a combination of size of input and efficiency.

How does the algorithm actually evolve given more input, and we are talking about exponential time of execution or even worse given a specific chosen algorithm for a given problem.

Algorithms can be categorised in these topics

  • Graphs (which include Trees) - minimum number of moves for Rubik's Cube
  • Sorting - Event simulations
  • Hashing - Genome sequencing
  • Numerics - RSA, HTTPS
  • Shortests Paths
  • Dynamic Programming

Here is an example on how to find the peak of a given array

array = [0,1,2,3,4,5]

Let's look at each element and see if that is bigger than the rest.

We would call this the straightforward algorithm for this problem.

for i in range(len(array)):
    if array[i] > max_value:
        max_value = array[i]

We would therefore always have to look at all of the elements to find the peak.

Time Complexity is O(n)


How would we make this faster?

Binary Search: A recursive algorithm using Divide and Conquer strategy

Rewriting the array in elements of index 1 to n.

array = [0,1,...n/2,...,n-1,n]
  1. Take element n/2
  2. If array[n/2] > array[n/2-1]

    • look at left half array[1,...,n/2 - 1] for peak
  3. Else if array[n/2] < array[n/2-1]

    • look at right half array[n/2,...,n] for peak
  4. Else array[n/2] is peak

Given that we now "split" the input size in half each time we run the algorithm we get a time complexity of log n.

T(n) = T(n/2) + O(1)
...
T(n) = O(log n)

Time Complexity is O(log n)

This is EXPONENTIALLY faster.

Just to give you a sense of what this intails:

input time
O(n) 10^5 13 seconds
O(logn) 10^5 0.0001 seconds