The Algorithm Series: Introduction to Algorithms

In a previous article, 'The Algorithm Series', I mentioned that this series would consist of what I learned about algorithms and data structures from freeCodeCamp's tutorial - 'Algorithms and Data Structures Tutorial - Full Course for Beginners'and that in doing so, I hope to provide a guide for understanding these topics as a beginner. I advise all you baby developers to take a look at the tutorial so it's easy to follow along with the article.

Contents

In this article, we'll cover what is:

• algorithms (definition)
• algorithmic thinking
• the measure of the efficiency of algorithms
• the practical application of algorithms

We won't be covering any code implementations yet so this article is just more of a short, theoretic background.

Defining Algorithms

An algorithm is defined as a set of steps used to complete a task, or more elaborately, a set of steps taken to solve a computational problem. The second definition is better because it gives a more precise look into what an algorithm is.

For each data structure, there are different ways to store data and different ways to compute the data, and that different way of computation is the algorithm. So, before we define an algorithm we need to start by defining a problem and breaking it down to find a solution, which brings us to the section.

Algorithmic thinking

It is considered an approach to problem-solving that covers breaking a problem down to clearly defined input and output as well as a distinct set of steps that goes from input to output. A solution can be described as an algorithm if it meets the following conditions:

• it has a clearly defined problem statement, an input as well as an output: We need to know what the problem is - what our algorithm has to do, we need to know what our input data, and we need to know what sort of output we expect from the algorithm.

• the steps are in a specific order and distinct from one another: If our problem was to figure out how to sort a list of n unsorted elements, we know what the expected out is and we know what the algorithm needs to do. Next, we have to define the steps to reach that solution, in other words, we have to implement the algorithm.

• it produces a result/output: Once we've figured out what steps our algorithm will take we can test our algorithm by running it with the input we have and see if it will produce the sorted list.

• it completes in a finite amount of time: If the algorithm terminates after sorting the n number of elements in our list, it completes in a finite amount of time it is correct.

Each time we encounter a problem, it is best to consider these conditions before finding a solution.

Measure of efficiency

To test an algorithm on its efficiency, we need to measure its ' correctness'. Algorithms are considered correct if (a) for any possible input of our problem we get the expected output and (b) for any possible input we get, the program should end/terminate. If these two conditions are not met then the algorithm is not correct.

There are two ways we can measure efficiency in algorithms:

• time and
• space

Time refers to time complexity, and we can define it as a measure of how long it takes an algorithm to run or as the time taken by an algorithm to solve a problem. It defines how the actual number of steps taken to solve a problem is dependent on the size of the input. For example, if we use a loop to print 'hello world!' i < n times, if each iteration counts as a step, as n increases so will the number of steps taken to complete the loop, and as a result, the time taken to print 'hello world' increases proportionally.

Space refers to space complexity which is a measure of how much space is taken up on the computer by an algorithm. It's the amount of storage we need as an algorithm grows. Consider a list of size n, if we use an algorithm to keep adding elements in the list(depending on the language) the size of the list may increase exponentially if the list keeps growing larger than its initial size.

Good algorithms need to balance these two measures to be considered useful.

Practical application

A crucial part of understanding algorithms is understanding what works best in a given context i.e what algorithm is most efficient for the problem you want to solve.

Let's consider two algorithms: a binary search and linear search algorithm, for the devies who never encountered these algorithms, they are used for searching through lists. Giving an example, if we were to search a dictionary book to look for the section of words starting with 'P', using linear search we would start at section 'A' and look through each page one by one until we get to 'P'.

However, with binary search, we would half the search by halving the number of sections/pages in the dictionary to search through. For example, we first look for the mid-section of the entire dictionary, which is (M and N but we'll go for the lower element-- which is what happens when we find the midpoint of a list with floor division-- but more on that later) 'M', we check if the letter 'P' comes after 'M', and if it does, we go to the upper half of the dictionary sections ranging from sections 'N' to 'Z' and halve it again. We look at the mid-section 'T', we check to see if it comes after 'P' - which it does not, so we look at sections 'N' to 'S' and the midpoint here, which would be 'P' and 'Q' but we choose the lower element which is 'P' and thus we have found our target without having to go through each page from 'A' until we got to 'P'. With binary search, we just keep halving the list until we get to our target.

In this example, it would be more efficient to use binary search to find the section we're looking for which makes it the most efficient algorithm for this particular problem. However, these are both good algorithms. Each works differently depending on the context so, it may be that for some problems linear search is more efficient than binary search.

Other Practical Applications

Similar to the dictionary example previously used. There are lots of real-life applications of algorithms that we aren't aware of, to name a few let's think of searching through a list of class names to find a particular student or sorting a record collection alphabetically. These are actions that require steps for the former example, you would check to see if the class list is sorted if it is not you have to go through the list elements one by one to find the name you're looking for. If it is sorted you know you can reduce your search time in half by finding the section for the first letter of the student's name.

In sorting a record collection, you would at the first record in your collection and compare it to the one next to it, if the first letter in the first record's name comes first then you keep it in the same position then compare the second record to the forth and so forth only switching if the following records come before the previous once.

Try to see which other problems in life can be solved using algorithms and see if you can identify the steps needed to solve them. This is the type of algorithmic thinking required to approach problem-solving. Break everything down to simple executable steps which eventually add up to the final solution - an efficient algorithm.

Conclusion

I hope you enjoyed the article. After reading this article you should know what algorithms are, what defines an algorithm, and how the efficiency of algorithms is measured and how we use algorithms to solve problems in real-life. In the next article, we'll cover Big O and more theory on the time and space complexity of algorithms.