Algorithms — Part I

Or should we call secret recipes to logical programming?

Choice is yours!

Image Source: http://bit.ly/2wSkMbO

Brief Overview

The world that we are living in is being increasingly powered by various software. We can hardly find anything being done without the use of software. Seriously, it just touches almost every aspect of our daily lives; whether keeping ourselves updated by scrolling through the news feeds, or doing office-work on spreadsheets or preparing presentations or coding, or driving in our cars or even using some smart kitchen appliances for our ease. And, have you ever wondered what powers a software? Of course, they are Algorithms.

Is ‘Algorithm’ a new term to you? Don’t worry — I am here to guide you. Algorithm can be described as processes or recipes or instructions (whatever you may want to call them) that describe the procedure to perform certain tasks. No matter what kind of applications you build, you are bound to come across certain situations that require the use of one or more algorithms to get your job done. So, all I am trying to convey is that trying to build a program without understanding the algorithms is like trying to build a car without having an understanding about the engines — hence, getting a proper understanding of the algorithms are so important.

Diving deeper into the concept of Algorithm through a hypothetical example

We would gradually dig deep and start understanding the concept of an algorithm through an example. Let us suppose that we have a collection of shapes(as shown in the picture below) and we have to group the shapes together in individual sets.

Collection of shapes: Rectangles, Squares, Circles, Triangles

Now, there are so many ways in which we can do this, but probably the easiest and the simplest way would be to write some kind of a loop function to iterate over each of the shapes, then determine what kind of shape each one is, and lastly add that shape to the correct group. So, by the time the process ends, we would have separate groups of each shape type.

The algorithm might look somewhat like this:

Algorithm for grouping the shapes in different category

And, after grouping, the final picture would be like this:

Final picture after grouping (i.e. after execution of the algorithm)

So, this complete set of steps that are taken together to solve a particular problem, forms an algorithm. Algorithms have several characteristics that could be used to describe them.

Algorithm Complexity

1. Space Complexity: Amount of memory and storage space required for the execution of the algorithm.
2. Time Complexity: Time taken to complete the algorithm, i.e. it describes how efficient the algorithm is relative to the size of the input it is given to work on.

Inputs & Outputs

1. Inputs: What does the algorithm accept?
2. Outputs: What are the results?

Classification

1. Serial/Parallel: The algorithms which are serial in nature work on their data-sets in a sequential fashion. On the other hand, a parallel algorithm can break up a data-set into smaller bits and then work on each simultaneously.
2. Exact/Approximate: An algorithm can be exact where it produces a known or predictable value. Whereas, an algorithm can be approximate too, in which case, it tries to find an answer that might or might not be exact (for example, a facial-recognition algorithm — might not produce the same result every single time).
3. Deterministic/Non-deterministic: Deterministic algorithms execute each step with exact decision. But when an algorithm seems to be non-deterministic, it attempts to produce a solution using successive guesses, which become more accurate over time, based on the data-set training (for example Machine Learning algorithms).

Common Algorithms

Some of the common algorithms used in our day-to-day life may include:

1. Search Algorithms — These algorithms are used where there is a need to find a specific piece of data inside a large data structure (for example, searching for a substring within a string or finding a file within a set of nested folders on a file system).
2. Sorting Algorithms — These are one of the most common types of algorithms used when working with ordered sets of data; be it numbers or strings. The working principle of these algorithms involve taking a set of data and then placing into a particular order.
3. Computational Algorithms — These algorithms are used to take a set of data, as input, and derive or produce another set of data. Simple examples using these algorithms can be finding out whether a number is prime or not, or finding the factorial of a particular number or converting a particular unit of measurement to another.
4. Collection Algorithms — Finally, there are collection algorithms which involve manipulating and navigating among sets of data that are stored within a particular structure. Some specific examples that can be included under these algorithms would be counting specific items, filtering out certain unwanted data based on some conditions, etc.

Understanding Algorithm Performance

As we have been discussing that algorithms are designed to work on sets of data and solve computational problems, it becomes very crucial to understand about the performance of the algorithm. The algorithm-performance is an important factor in choosing a particular algorithm to solve a programming problem as well as in understanding on how your program would perform under certain circumstances. So, measuring the change in the performance of an algorithm depends mainly on the size of the input data, and the term used to describe the algorithm performance is called the ‘Big-O notation.’

Big-O notation

This notation is used to describe how a particular algorithm performs as the size of the input data keeps on growing over the period of time. And, the reason behind using the letter O is addressing the growth-rate of an algorithm’s time complexity as the order of operation (time-scale to perform the operation). It usually describes the worst-case scenario of the duration it takes to perform the cooperation. And, one noteworthy thing is that many algorithms and data structures have more than Big-O value.

For example, if we speak about the Data Structures, we can usually perform multiple operations on a particular program, such as, inserting, searching, sorting — for values each of which have their own order of operation. So, it’s time to have a look at some of the commonly used Big-O terms.

Quotidian/Familiar Big-O Terms

So, this is just a sneak-peek of the time-complexities of the various algorithms, and we would gradually learn in details about them in due course of time. If you want to view graphically how the order of complexity becomes worse, here it is:

Image Source: http://bit.ly/2IqGNVS

We will be discussing about the complexity of algorithms in the next part of the article.