Algorithms — A Short Introduction

Jamie
PubSquare Media
Published in
8 min readApr 4, 2018

--

Written By Jamie Taylor (@dotNetCoreBlog)

A short introduction

Hey everyone, Jamie “GaProgMan” Taylor here. I usually write for “A Journey in .NET Core”, and I’m delighted to be authoring a guest post for Rising Young Minds.

For those who don’t know, I usually write all about Microsoft’s .NET Core platform. .NET Core is a cross platform (this means it runs on many different Operating Systems) set of tools and APIs which can help developers to write applications.

A Quick Note

This article is designed to be self-contained, but it is part of a series that I’ve put together for Rising Young Minds — they are such an amazing group of people to work with.

Although it’s a self-contained post, it might be worth you taking a look back at my previous article “So You Want To Be a Developer”.

Background

Modern development practises make use of multiple programming languages, with very few projects requiring the use of a single programming language throughout. I have another post planned all about programming languages but you should know that, as a developer, you’ll be expected to know more than one language.

Aside from a set of programming languages, the next biggest thing you’ll need to know are algorithms.

Algor-who?

The word Algorithm comes from the Medieval Latin algorismus, which in turn is a mistranslation of the Arabic al-Khwarizmi, which is the surname of Abu Ja’far Muhammad ibn Musa al-Khwarizmi.

Al-Khwarizmi was a 9th century mathematician from Baghdad who wrote the treatise “al-mukhtasar fi hisab al-jabar wa al-muqabala” which is translated as “the compendium on calculation by restoring and balancing”. This same treatise is where we get the word “algebra” from (it comes from the “al-jabar” in the title).

What Does That Have To Do With Programming?

Algorithms are lists of steps required in order to do some task, and programming is all about taking a complex problem and breaking it down into small, easy to use, chunks.

Imagine that you wanted to write an algorithm for making a cup of coffee, it might go something like this:

  • Grind the coffee beans
  • Install a new filter into coffee machine
  • Pour water into the coffee machine
  • Add ground coffee beans to the machine
  • Start the machine
  • Browse Rising Young Minds whilst the coffee brews
  • Pour brewed coffee into a mug

Or:

Or, of course:

The key to a successful algorithm is breaking a problem into a set of small steps. Each step should be self contained and can either be a command (do something) or a conditional (based on the result of something, go to a different command).

Someone once said that “a picture is worth a thousand words”; with that in mind we can take the “making coffee” algorithm and create a flowchart. This flowchart will tell anyone who looks at it precisely what your algorithm does. The following image is my version of the “making coffee” algorithm:

There’s no special place you need to go to learn algorithms or a special course that you need to enroll in to learn them. They are taught in Computer Science and Software Engineering classes, though. But you don’t need to take a class in order to learn them.

There are hundreds and hundreds of books all about the most commonly used algorithms — seriously, do a quick search on Amazon (or your book store of choice) for the keyword “algorithm”. See how many there are?

Some books will be more complex than others, and some will teach algorithms with a specific programming language in mind. One of the simplest books I’ve ever found on algorithms is The Impostor’s Handbook by Rob Conroy (the other was Algorithms To Live By), but it’s up to you to find the best resource for you. Why not check on YouTube or at your local library?

Which Algorithms Do You Need To Know?

Technically, as many as you can commit to memory — the more the merrier. But there are a core few that you may need to know, depending on the types of stuff you end up working on.

You won’t be expected to know the ins and outs of Brotli if you work on industrial control systems, for instance. If you’re a web developer, then it might be worth having a little knowledge of what Brotli is and what it aims to achieve.

Most of the common algorithms that you might need to know are either related to sorting or compression.

We’ve all heard of zip files, right? But what do they do? Sure, they compress a file (or a bunch of files), but how does that work and why is 7zip better at it? If 7zip is so great, then what’s this Brotli all about?

For compression algorithms, take a look at gzip (which is what zip is based on), rar and 7zip.

And sorting? Imagine that you have a stack of books and you want to sort them into alphabetical order by the Author’s surname (using the first author listed, if there is more than one) then cross referenced by year. Think about how you would do that, now imagine trying to tell a computer to do that but in abstract enough terms so that you can apply the same logic to DVDs or video games.

For sorting, I would look into Bubble Sort, Quicksort, and Insertion Sort.

It’s useful to know some of the basic algorithms, because in real programming work we often get asked to solve very,very, similar problems. For instance, the process involved in organising our books would be (more or less) the same for organising our DVD collection.

There’s an amazing (albeit short) series of videos on the AlgoRythmics YouTube channel which are all about visualising some of the most used sorting algorithms. I would definitely give them a watch.

Big O

Just knowing an algorithm isn’t enough in order to be useful with it; you need to know its Big O notation too.

In the beginning, there was math; then came physics; then electronics; then we got Twitter, Instagram, and Netflix.

Big O notation is a way of describing, in mathematical notation, just how complex an algorithm is for a given set of input data. “Complex” here can mean how long an algorithm takes to complete or how much space (memory) it may take up while processing the input data.

The most common used Big O notation values are:

  • O(1) — read “O of one”
  • O(log n) — read “O of log n”
  • O(n) — read “O of n”
  • O(n2) — read “O of n squared”

There are many others, and I’d recommend you check out this list on Wikipedia if you want to drink the potion and fall down the rabbit hole. I’ve added them here in order of complexity from simple to complex.

O(1)

O(1) is also known as “Constant Time”, this is because anything which has a Big O notation of O(1) will always take the same amount of time, regardless of the input data set. This is considered the quickest: if you have an algorithm which can complete in O(1) time, then you’ll likely never be able to make it any more efficient.

A real world example of this would be figuring out whether a number was odd or even — it’s one or the other (except for special cases like 0), and the calculation is incredibly simple.

O(log n)

O(log n) is also known as “Logarithmic Time”, this is because the time taken to run the algorithm changed logarithmically in direct proportion to the number of items in the input array.

Normally logarithms are calculated in base 10 (or decimal), but depending on the algorithm used, this is sometimes calculated in base 10 or base 2 (or binary). Mathematically both base 10 and base 2 are similar in this case; see this answer on Stack Overflow for more (mathematical) details

The ’n’ represents the number of items in the sample data set, so an O((log n) algorithm performed on a sample data set of 100 items (maybe 100 names in a census) would have a real Big O value of log 100.

A real world example of this would be finding a given card from a sorted collection of them which are spread out on your desk. You start with your target number, find the midpoint in the collection and decide which half of the collection your target card is in, continuing this “divide and conquer” approach until you find the target card (or run out of places to search). This particular example is also called “Binary Search.”

If you prefer a more visual example, I would recommend checking out these Ikea style instructions for Binary Search or taking a look at the following gif (courtesy of Math Warehouse).

Source: http://www.mathwarehouse.com/programming/gifs/binary-search-tree.php

O(n)

O(n) is known as “Linear Time”, this is because the time taken to run an algorithm with a Big O of O(n) is directly proportional to the size of n (which is the size of the dataset).

If you have a data set of 100 items, then it will take a time of 100T (where T might be seconds, minutes, or hours) to run through the dataset with an algorithm with a Big O of O(n), and the real Big O would be O(100).

An example of this would be summing a list of numbers. Let’s say that you have 75 numbers to sum, it makes sense that you have to look at each number in turn and add its value to the current total. Which would mean that the Big O would be O(75).

This isn’t technically right, but it’s right enough for our description.

O(n2)

O(n2) is known as both “Sub-Quadratic Time”, this is because the time taken to run the algorithm with a Big O of O(n2) is the square of the size of the data set (which, as with other Big O notation, is denoted by n).

If you have a data set of 50 items, then it would take 2500T (where T might be seconds, minutes, or hours) to run through the data set with an algorithm with a Big O of O(n2), and the real Big O would be O(502).

An example of this would be using Bubble Sort on a randomly sorted collection of playing cards (let’s take clubs and ensure that we have no repeated cards, as it will be easier to deal with).

The idea is that you take the first two cards in the pile and compare them, placing the card with a lower number to the left and other card to the right. These steps are repeated until the set is sorted into two piles, then these steps are repeated on the two separate piles until the cards are laid out in order. At which point, the cards are sorted but it has taken a long time to do it.*

Conclusion

The exact list of algorithms which you will need to know will depend on the types of applications that you write. Usually scientific work will have a specific set of core algorithms, machine learning will have another set, for example.

From my own experience:

  • Web development tends to need less algorithm knowledge than platform knowledge (in this case how the HTTP, TCP and IP stacks work)
  • Games development tends to focus on physics and compression algorithms
  • Mobile development can be anywhere between no algorithms and a very specific set of algorithms (depending on what your application does)

Hopefully, you now know a little more about some of the more common basic algorithms. For a real world application of algorithmic thinking, I would check out Brandon’s earlier post on using algorithms in dating.

Want to keep up with The RYM? Like us on Facebook, follow us on Twitter, or join our mailing list below!

--

--

I’m a .NET developer specialising in .NET MVC websites and services, and I blog about .NET Core things