Asymptotic Analysis in Practice

Concepts

0_LcMMZTV76P6vD5mc

In this final article we will look at analysing the complexity of an algorithm without the use of asymptotic analysis, and in doing so showcase the benefits of using Big O Notation. Additionally we will look at the everyday practical uses of Big O when developing software applications.

screen-shot-2017-07-16-at-13-08-25.png

The above code doesn’t do anything meaningful. Given an array of integers of n size, iterate through the array, and for any element equal to 5 we simply multiply it by 6 and print it.

Without asymptotic analysis how would we go about evaluating this algorithm for efficiency without performing some kind of benchmark? Well, the simple answer would be to count the amount of instructions executed. The more instructions that have to be executed the more time its going to take for the computer to finish executing that algorithm. Therefore, knowing how many instructions the algorithm is made of seems like a good starting point.

The example can be broken down into the following: a for loop that executes n times, an if statement, a multiplication, and a print statement.

A problem arises though when trying to base our performance on the number of instructions in the algorithm, our algorithm wont always execute all of them. The multiplication and print instructions only occur if the element is 5, and we cannot be sure if, or how many elements in an array will be equal to 5.

Additionally, the code we write is broken down into something that is understood by a computer. The number of instructions it is broken down into depends on the hardware and compiler. Which means our algorithm again is only being tested against a specific hardware/software configuration.

As we have already seen then asymptotic analysis removes these dependencies, allowing us to test independent of any specific implementation. In asymptotic anlaysis the constant values are ignored, this makes sense in our case as this relates to the instuctions themselves, which like we said may be different.

Therefore, we simply need to look at the algorithm and determine its order of growth. The highest power related to its input, in this case it is simply n. We loop around all of the elements once and possibly do something if we have a value of 5.

Now we can use Big O to describe this algorithms upperbound, or worst case scenario. We can say that the algorithm f(n) is worst when every element in the array is equal to 5, as we would have to execute 2 instructions for each element along with executing the if statement. We would end up with a function f(n) = 2n + 1. As we stated though, we are not concerned with constant values and we know the order of growth is n so we can simply say that our algorithm has a growth rate O(n).

Asymptotic analysis allows us to calculate the efficiency of code based on its input. The best use case for big O is when developing scalable algorithms. An algorithm that has to perform well even when its input is huge. A good example of scaleable algorithms are those related to searching for data. These have to work well for 10 elements as well as for a 100,000. We know as n gets bigger it would take more time for the algorithm, therefore an algorithm with a low order of growth will perform a lot better with large input than one with a higher growth rate.

However, this best use case scenario, may not end up being how you use asymptotic analysis. It all depends on what you end up developing. Most developers won’t be writing scalable algorithms, and instead rely on asymptotic analysis for evaluation and decision making. That is asymptotic analysis is useful at identifying bottle necks in a piece of software, and acts as a useful tool when deciding what algorithms or data structures to use to solve a given problem. Without such knowledge you will be less able to identify performance issues and are more likely to write code that causes them.

I hope this article has provided some context on the theory previously discussed, whilst showing pratical uses of asymptotic analysis. Dont worry though as you become a more experienced programmer using Big O will become second nature.

Describing Algorithms with Big O Asymptotic Notation

Concepts

alphabet-2051685_1920.png

In the previous article we looked into techniques for determining an algorithms efficiency, specifically looking into conducting asymptotic analysis of our algorithms. Today we will look at describing our analysis using a specific type of asymptotic notation, Big O. Additionally, we will look into common classifications of algorithms in terms of describing their runtime complexity with Big O.

Asymptotic analysis can help us define the limiting behaviour of a function. For our purposes we can use it to determine the efficiency of our algorithm based on the size of the input. Asymptotic notation helps us describe the analysis of a function.

We can describe the upper bound (Big O), lower bound (Big Omega), or both with Big Theta. The focus of this article is on the discussion of Big O notation, as it is the most commonly used notation when describing algorithms in computer science.

I will save you from suffering through the formal definition of Big O, especially since its not all that helpful for our purposes. If you are interested though, you can read about it on this Wikipedia page.

Big O is a notation that describes the upperbound of our algorithm. The upperbound can be seen as the worse case scenario, measuring against some metric e.g. execution time, memory consumption, etc. The notation for Big O is written O(f(n)) read: “order n” where f(n) describes the largest term within the function.

The biggest term of a function, also known as the highest order, is simply the largest term in that function. Largest describing the term with the highest power. For example, given a function f(n) = 2n^2 + 3n + 5 we can see that the largest term is 2n^2. This means we can describe the function as having an order of growth n^2, O(n^2).

The order of growth of a function is dependent upon its largest term. If f(n) = 2n^2, and g(n) = 2n, we can say that f(n) has a larger order of growth than g(n). As the value of n increases the output of f(n) is going to be much larger than that of g(n).

There are a few things that need to be mentioned before we look at common classifications.

Firstly, just to reiterate Big O is just a form of notation for describing the upperbound of our algorithm. Asymptotic notation in general is just simply a shorthand of describing the behaviour of an algorithm. That is, if we analysed our algorithm in terms of its worst case performance we would use Big O notation denote this behaviour.

Secondly, if an algorithm is described with O(f(n)) we can assume that it will act at worse O(f(n)) but we cannot assume that it will always be of O(f(n)). Therefore, be cautious as O(f(n)) might not tell you all the information you need to know about an algorithm e.g. best/average case scenarios.

Finally, it is worth noting that Big O is a guideline and not a guarantee. For some value n with a large constant c, it might be that a quadractic algorithm may be better than a linear function in cases where n is small. For example, given f(n) = 2,000n + 50 and g(n) = 2n^2 the quadratic algorithm g(n) is more efficient than the linear algorithm f(n) despite the growth of the function being larger.

This means that asymptotic analysis only holds when the value of n is large, and if its not then you cannot assume that a function with a lower order of growth is more efficient than a larger one. Remember asymptotic analysis is only concerned with the largest term, and not its constants or any other terms

With all that out of the way we can look at how to describe certain algorithms in terms of O(f(n)). Below is a few common orders of growth. Each graph shows how execution time is affected as the value of n increases.

Screen Shot 2017-07-09 at 10.24.06.png

O(1) (constant): An algorithm that always requires the same amount of time to execute. Its order of growth is constant. Any single statement of code is constant e.g. print(“Hello World”);, int a = b – c;, etc

Screen Shot 2017-07-09 at 10.20.41

O(log n) (logarithmic): An algorithm in which the time required is dependent upon the log of the input n. Its order of growth is proportional to log n where log is to the base 2. The algorithm will typically take longer to execute as n increases, but after a certain point the input of n wont affect the execution time. An example of an algorithm of O(log n) is a binary search.

Screen Shot 2017-07-09 at 10.19.42

O(n) (linear): An algorithm in which the time required to execute is dependent upon the size of the input n. Its order of growth is proportional to n. That is, as n increases the time taken to execute the algorithm will also grow at the same rate as n. An algorithm that uses a single loop iterating n times. An example of such an algorithm is a linear search.

Screen Shot 2017-07-09 at 10.22.16

O(n^2) (quadratic): An algorithm in which time required is dependent upon the size of the input n squred. Its order of growth is proportional to n^2. That is the execution time will increase dramatically as n gets larger. A typcial exmaple is any algorithm that makes use of two loops, for instance an insertion sort.

To conclude asymptotic analysis is a means of measuring the performance of an algorithm based on its input. Big O is a form of asymptotic notation that denotes the worst case scneario of our algorithm. Hopefully this has all made some sense, but if not don’t worry, the next article will put asymptotic analysis and Big O into practice through some examples.

An introduction to Theoretically Evaluating Algorithm Efficiency with Asymptotic Notation  

Programming

speedometer-653246_1920

Don’t get scared away by the title; what we are going to talk about isn’t all that complicated. In a previous post I introduced the concept of an algorithm, and gave a brief description into how an algorithm is deemed to be efficient. This article will take this further by discussing techniques available to us for testing the efficiency of our algorithms before we go about implementing them in code.

Before we get started, lets first go back over efficiency. An algorithm can be efficient if it meets the memory or running time requirements imposed. Basically, our algorithm must use less than a maximum amount of memory, or run no slower than an amount of time specified. The restrictions imposed are dependent up on the problem we are trying to solve.

In order to test for efficiency, an algorithm must go through a theoretical analysis, using asymptotic analysis, before the algorithm is implemented.

The reason for this theoretical analysis is that simply without it our algorithms could only be tested through implementation.

Why is this bad? Well, firstly, we have to perform the implementation before we have any idea of how the algorithm will run. Meaning you could spend a long time developing something to realise that this algorithm will not run the way you want it to.

Secondly, by testing an algorithm through implementation we are making our algorithm dependent upon a specific platform, programming language, and hardware configuration. Altering any of these variables could result in a different result. Given the shear amount of variation we could never test our algorithm for all possible configurations.

Having a way of analysing our algorithm before we start implementing it allows us to save time, but more importantly allows us to judge efficiency independent of any hardware or software.

As described by Wikipedia, asymptotic analysis is the field of mathematics for describing the limiting behaviour of functions. A limit of a function is the value a function approaches as the input of that function approaches some value, usually zero or infinity.

Therefore, we are looking at the output of our function against a specific value, based on the values we are passing into the function.

If we have the function f(x) = e^x we could look at the output of that function as x tends towards infinity. Basically our function output grows exponentially as the value of x gets larger.

Asymptotic notation is a language that describes the type of behaviour of a function respective to the growth of that function. What I mean by this is that given a function f(n) = 2n^2 + 600n + 200 we are only concerned with the most significant term, n^2, because as n tends towards infinity the other terms and constants become irrelevant, as shown in the graph below.

As you can see from the graph the n^2 term results in a significantly larger output as the input size increases.

There are a few different types of notation and in the next article we will go into a lot more detail about one of them, but for now lets talk about how all this relates back to algorithms.

This idea can be applied to our algorithms, whereby the input of our function is the size of our input of the algorithm. Input is the metric we use as algorithms are designed to work with inputted data because an algorithm is useless without it. A search algorithm requires elements in which to search, as does a sorting algorithm needs input to sort.

As the input increases in size we can see that an algorithm might take longer to complete, or require more memory. It would take a lot less CPU cycles, or steps to search through a 100 items as it would do to search through 100,000.

This leads us onto the output of our function, which is what we want to measure for within our algorithm. If we are measuring the time it takes to run then we would like to see how long our algorithm takes to complete as the input amount increases. If we want to measure against memory, we would want to see how much memory is used up as the amount of input increases.

Therefore asymptotic analysis is required to measure the running time or memory capacity required by our algorithms as the input size increases. Asymptotic notation is where we describe our function as a rate of growth using the most significant term, and removing any insignificant terms or constants. We end up with an independent method for determing the efficiency of an algorithm.

In the next article we will look at a specific form of asymptotic notation, Big O notation, which is commonly used in computer science for measuring an algorithms performance.

Programming Fundamentals: Algorithms

Programming

060417_1744_Programming1.jpg

Welcome to the final article in this series on programming fundamentals. Over the last several articles we have looked at many important concepts that are applicable to any programming language you will be using. These concepts included: variables, data structures, conditions, repetition, and functions. In this last article, we look at algorithms, something that requires the use of all the concepts previously discussed.

At the most basic level we can define an algorithm as a set of steps that when finished result in the completion of a task, or the solution to a problem. The first article in this series introduced an algorithm for making a cup of tea. Under this definition though we could easily deduce that entire programs are algorithms as they are made up of a series of steps, albeit many steps, for completing a task. However, when we discuss algorithms in the realm of computer science they are generally seen as small concise steps intended to complete a specific task.

Algorithms can be classified dependent upon how they go about solving a problem. Some examples of types of algorithms include: divide and conquer, greedy, and brute force algorithms. The classifications give details with regards to how the algorithm performs. A brute force algorithm is one that will try all workable solutions until a match is given. For example, if we wanted to find out a person’s pin number we would try to enter every 4-digit combination until we entered the correct one.

Over the years, a multitude of algorithms have been developed that have been applied to solve a wide range of problem from searching, and sorting data within a data structures, to rendering realistic graphics in games. In most cases, it is up to the developer to use an existing algorithm to solve a specific problem dependent upon the problem at hand. In some situations though, you may have to modify an existing algorithm to suit your need, or even design your own.

Algorithm design involves developing a series of steps that can be reused to solve a specific problem. There is a lot that goes into designing an algorithm. We must understand the problem we are trying to solve, ensure that our algorithm works for all the values we expect to be input, and that the algorithm is efficient. Efficiency generally refers to how much memory we need to use whilst our algorithm runs, and how long it takes for our algorithm to complete.

Algorithms are essential in computer science. They are designed to solve problems, but also to be reusable, so that they can be then applied by developers for whatever they need. A search algorithm could be used, for instance, to sort a range of numbers from highest to lowest in a leaderboard, We decide how to use them, and having so many algorithms already designed for us, we are not short of options.

So there we have it, a quick overview of algorithms. I purposely left this last article light on details as algorithms are such a broad topic which cannot easily be explained in this article alone. But at least you now have some understanding of what they are.

I hope this series has provided a brief introduction, so if you look elsewhere on your journey to becoming a programmer and run into the word algorithm, variable, data structure, or anything of the other things we have discussed then you will know exactly what is going on, and a little a bit about the why.

The last point to make is that this is unfortunately only the beginning. There are a lot of concepts I haven’t discussed, some big ones such as object orientated programming, recursion, nesting, scope, and many more things. But there are plenty of helpful people out there to guide you on your way. Good Luck, and have fun!

Programming Fundamentals: Functions

Programming

050417_1955_Programming1.jpg

In the previous post that can be read here, we looked at repetition, the process of telling a computer to repeatedly execute a set of instructions based on some condition. In this article, we will delve into functions, what they are, how we use them, and how best to design functions in our programs.

Yet again, before we delve into functions, there are some things we need to know first. Mostly we need to look at statements and compound statements.

In most programming languages, the smallest element we can use to create a program is known as a statement, which up until now we have been calling an instruction. We have already looked at several different statements: if-statements, while-statements, and for-statements, but other statements exist such as assignment statement, assigning values to our variables, and expression statements, which is a statement that produces a value, for instance 5 + 5 * 2.

Often it takes more than a single statement to get something done, and that’s where compound statements, also known as blocks, come into play. If-statements, while-statements, and for-statements are all examples of compound statements. That is, they comprise of more than a single statement. In most programming languages, we define a block of code using a set of curly braces, so an if statement would look like the following:

If(condition)

{
// statements in here

}

The above example shows an if statement, and curly braces with all instructions within the curly braces being the ones that are executed if the condition evaluates to true.

There are two main benefits for using code blocks. They allow us to define scope, something I won’t be touching on in this article, and that as you have already seen, they allow us to group a set of statements. One thing we can’t do with our compound statements is use it multiple times throughout our program, which finally brings us nicely onto functions.

Functions

A function is like a named compound statement which can be referenced by its name throughout our code, and thus used multiple times. However, unlike a compound statement, our functions have additionally properties. They can accept and return data in the form of variables or data structures.

A function needs a name so we can identify it, like a variable does so we can access the memory location our data resides in, a function name is an identifier to the address were our group of statements are stored. As a function can accept and return data, we also must define this when creating our function. A name, return type and list of accepted data forms the signature of a function. Below is an example of a function:

int AddNumbers(int a, int b)

{

    int c = a + b;

    return c;

}

In the example shown we have created a function called AddNumbers which accepts two variables, also called parameters, called a and b, defined within a set of parentheses, and we have our return type defined as an int, placed before the name of the function. The idea behind this function is that it accepts two integer numbers, and then we add these two numbers together within the function and return the result.

There are no restrictions on the type of data our function returns, it can be a primitive type, or user-defined. Additionally, we can pass in any number of variables of any type, in which they don’t have to be of the same time, we also don’t have to pass in any variables at all. In most languages, we are also allowed to return nothing, which is typically done by specifying the return type as void.

void PrintHello()

{

    Print(Hello);

}

For us to use the functions we create we must call them within the parts of our program in which we want to use them.

Calling the function, is done by using the name followed by a set of parenthesis, following on from the example above we would call the function AddNumbers in the following way: AddNumbers(5,3). The values we passed in are stored in the variables a and b respectively and are then added together, return the variable c which will equal 8. In the example just given though we are calling the function but we are not doing anything with the value returned. To make use of the return value c we need to store that data somewhere, like in a variable. To call the function and store the value would look like the following:

Int d = AddNumbers(5,3)

Functions can be called from anywhere in our program, that is we can all them within loops, if statements, or even within other functions. Functions essentially point to a block of instructions that we want to execute so when we call a function you can think that we are just adding that block of instructions into our program at that point.

As you can start to see functions are a powerful concept. They allow us to reuse a set of statements as many times as we want in our program reducing the amount of instructions we need to write. They also allow us to better organise our program, making it easier to maintain, well that is if we design them properly.

Designing Functions

When deciding whether to write a function there are a few things worth considering. The first step is to decide whether the instructions you want to put into a function are going to be used more than once, if not then you might not have to put them in one.

Secondly you must decide on the return type. Do you think your function should return anything, and if so, then what? Then finally we need to figure out what parameters if anything we need to pass into the function. The specifics are all dependent on the problem you are trying to solve, or the program you are trying to write.

If we wanted to do any mathematical operations such as adding or subtracting numbers then we can assume that we would want to pass in the numbers we want to add together either as variables or as a data structure. We would also probably want to use the result of the function, and therefore should return it.

If we wanted to output something to the screen and wanted to write that into a function we would mostly likely have a parameter of the thing we want to print: a number, or word, but we would most likely not want to return anything as we simply want to output to the screen.

I think the most important thing to think of when designing functions is to remember that a function should only do one thing. If we want to write a program that adds two numbers together and then prints them out we can see that the there are two things we want to do, add numbers, and print them, and that these tasks are separate from one another, and therefore should end up in two separate functions. If we were write them into a single function, we would never be able to reuse our code as effectively as possible. We wouldn’t be able to add two numbers together without printing them, nor could we print a number without first adding it to another.

On a final note to allow functions to help us organise and improve the readability of our programs it is essential that our functions are given a meaningful name, this stems to our variables as well. We need to know what is being stored in a variable, or what a function we call does, and this is best coming across in the names we select for them.

Conclusion

In this article, we have learnt about functions. A function is a grouping of statements that can be referenced by name, that can accept and return data. Using the name of a function we can call it multiple times in different parts of our program. This results in cleaner, more organised programs, that avoid us having to write duplicate code when wanting to perform a similar task, in which only the data has changed.

After reading this article, and assuming you have been reading the rest of the series, you should have a good understanding of the major concepts that most languages are built around. In the final article in this series, we will look at combining all the concepts we have learn about so far, by introducing algorithms.

Programming Fundamentals: Repetition

Programming

043017_1840_Programming1.png

In the last article we looked at conditional statements, and how they allow for branching, the ability for a computer to decide what instructions to execute based on a set of conditions. The practice of evaluating conditions to dictate which instructions to execute or ignore, is only one application of conditions. Another way to use them is through repetition, the ability for a program to repeat instructions, in which they are repeated based on some condition.

A condition used in repetition, is used to determine how many times a computer should execute some instructions. In some cases, we know exactly how many times we want an instruction to repeat, and if it is only a few times, it is not difficult to type out the same instruction several times. Although when we want to repeat the execution of an instruction 10,000 times this would take a while to type out, and is an ideal situation where we would use repetition. Telling our program to execute the instructions under the condition that it executes them 10,000 times, which obviously saves us a whole lot of time!

In other cases, we may not know how many times we want instructions to repeat, but we know we need to execute them more than once. This maybe because we want to repeat them based on some user input, or based on the results of some other instructions, like a mathematical expression.

A good example program would be a video game. Games are very complicated programs, but the basic way in which they work involves using repetition. We start up our game, and run through the same instructions: asking for user input, updating the things that happen in the game such as characters and enemies moving or shooting, and finally displaying the game to the screen. We can play games for a matter of minutes or hours, and this straightforward process is repeated indefinitely through this time, until something occurs to cause game over. The exact condition in which game over occurs depends on the type of game, but this could be from losing all your lives, having no health left, or running out of time. Either way the game works by repeating a set of instructions until a game over condition evaluates to true, resulting in the game ending.

In terms of implementing repetition into our programs, like with conditional statements, all programming languages support repetition, using loops. There are several different types of loops but the two most common types are while, and for loops. A while loop looks like the following:

While (condition)

    Execute instructions

Looks a lot like an if statement, except we replace the word if with while. What happens is that our program executes instructions based on the condition. The important thing to remember about a while loop is that the instructions won’t be executed a single time if the condition is not met. While loops are best used when we don’t know how many times we need to iterate (pass)through a loop, for example:

While (gameOver does not equal true)

    Execute instructions

In the above example the instructions in the loop will be executed until the variable gameOver is changed to true, which could occur at any time. A for loop on the other hand looks like the following:

For (initialisation; condition; increment/decrement)

    Execute instructions

A for loop seems slightly more complicated than a while loop, but it’s not too difficult to understand. For loops are split into three parts: initialisation, condition, and increment/decrement. In the first part this is where we initialise any variables we would like to use in the loop, usually a variable that stores an integer value. Second is our condition, this obviously decides how many times we iterate through the loop, repeating instructions. Typically, this will be some comparison such as x < 10, or x equals 10. The final part relates to how we alter the variable we initialised, whether we add or subtract some value, dependent on our needs. Below is an example of a for loop.

For (integer i = 0; i < 10; i = i + 2)

    Execute instructions

In this example, we will execute our instructions 5 times. We start by initialising our i variable with the value 0 then we check if the value is less than 10, if it is then we add 2 to the variable then execute the instructions. This is repeated until i is no longer less than 10, which will occur after 5 iterations. It is best to use a for loop when we know exactly how many times we want our instructions to be repeated.

So far, we have looked at using loops as a way of allowing a computer to repeatedly execute instructions, but what types of instructions do we want to execute in a loop? Some examples include: adding or multiplying numbers, initialising variables, or even using loops to traverse through data structures.

The exact nature in which we traverse through a data structure depends on the programming language, and the type of data structure, but the general idea is that we can use a loop to traverse through all the data values we stored within a data structure. If we had a data structure that contained 100 different integer values, we could use a loop to traverse through the data structure, meaning we get access to each value, which we could then do something with, like change its value, or output it to the screen.

To conclude, repetition further enhances the capabilities of the programs we write by allowing us repeatedly execute instructions. Repeating instructions saves us from having to repeatedly type instructions in cases where we know the number of times we want an instruction to be executed. Additionally, they allow the creation of interactive applications such as games by allowing instructions to be executed several times unknown to the programmer. While and for loops are common implementations of repetition within programming languages, each tailoring to a specific situation, while loops best suited for situations where we do not know the number of times the instructions will be executed, and for loops reserved for times when we do know this information.

After reading this article you will be well on your way to understanding the fundamental principles required to write programs however there are still a few things left to learn. The next article will look at functions, what they are, and how they can be used to help us write better programs.

Programming Fundamentals: Conditions

Programming

042717_1212_Programming1.png

The first article in this series of posts talked about how programs consist of instructions written in programming languages. When we write instructions, we are telling the computer what to do, and the computer executes these instructions in the order that we write them. Our programs will be rather basic though if we don’t allow for branching, the ability to execute certain instructions based on some condition.

A conditional statement is an instruction that allows a computer to decide what to do based on a condition. A condition is anything that can be resolved to either being true or false. Many programming languages include a data type known as Boolean value that is used to store a true or false value. Any data type can usually be resolved to be either true or false, with a value of 0 representing false, and anything else equating to true.

It is not just values that are evaluated, we can also use mathematical expressions as conditions, such as checking x > 5, a + b = 6. We are also not restricted to evaluating a single condition, with the use of Boolean logic we can create complex conditions using AND, OR, and use NOT to allow a condition to be checked against something not being true. AND and OR allow us to combine multiple conditions, using the examples previously described we could write a conditional statement that states that x > 5 AND a + b = 6, which means that both x must be greater than 5 and the variables a and b must equal 6 for the condition to be true. OR on the other hand requires that only one of the conditions, x > 5, OR a + b = 6 equate to true for the whole condition to be considered true.

A programming language can be looked at in the same way as any spoken language, we must learn the words and rules that govern the language, the syntax, to use it. Each programming language will have a set of reserved words and define a structure we must follow for the computer to be able to understand the instructions we write. A conditional statement is an important concept, and is thus implemented into all languages, otherwise there would be no branching. Most languages implement a conditional statement using the word if. A conditional statement will look something like the following:

If (condition) then

    Instructions to do something

In the above case, we would test a condition and then proceed to execute some code. Additionally, another reserved word else, is associated with conditional statements.

If (condition) then

    Instructions to do something

Else

    Instructions to do something else

The inclusion of the word else means that we have the option to branch out and execute instructions dependent on the evaluation of the condition. In the first example, instructions would be executed, if and only if the condition evaluated to true. In this second example, the computer gains the ability to execute instructions if the condition does not evaluate to true. A third example shown below, makes use of the words else if.

If (condition) then

    Instructions to do something

Else if (condition) then

    Instructions to do something else

The key difference between the 2nd and 3rd examples is that instructions in the 3rd example are dependent again upon some condition evaluating to true. In the 2nd example the instructions after the else word are executed every time the if condition evaluates to false. In the 3rd example though, there is chance that both instructions in the if and else if sections aren’t executed if both conditions evaluate to false. Also, there are no restrictions upon the amount of else if conditions you can use. By this I mean we could have code that looked like the following:

If (condition) then

    Instructions to do something

Else if (condition) then

    Instructions to do something else

Else if (condition) then

    Instructions to do something else

Else if (condition) then

    Instructions to do something else


Although we can use as many else if statements as we want, we cannot use else repeatedly, as the computer would be unable to determine which else’s section of instructions to execute.

Therefore, conditions give us incredible opportunities to write more complex code by allowing us to execute instructions based on conditions defined by us whether that’s checking the value of a variable, or evaluating a mathematical expression. We can control the flow of execution of our program, and ensure instructions are only executed when we want them to be. Conditions are not strictly limited to use in conditional statements, such as if statements, and play a big role in the ability to repeat the execution of an instruction, or set of instructions. The next article will expand the use of conditions, by describing their use in relation to repetition.

Programming Fundamentals: Data Structures

Programming

041717_1636_Programming1.jpg

The last article introduced our first fundamental concept, the variable, and explained that variables are a named memory location for which we want to store a specific type of data, more on variables can be read here. Variables are useful for storing a single value, a single piece of data of some type, however you may want to store more than one piece of data, and that requires the use of a data structure.

Before describing data structures though I would like to look back briefly at data types. As discussed in the previous article I explained how we must declare a type for the data we want to store in a variable, so we can give meaning to the data, which we know is essentially a sequence of binary digits, through the operations that can be performed on that data.

For example, if we look at a common data type, an integer, which is used to store whole numbers, we can perform typical operations on these numbers such as addition, subtraction, division, and multiplication. Therefore, the type integer, states that the binary number stored represents a whole number, as well as describing the operations that can be performed, mathematical operations.

All programming languages have a set of basic types, defined within the language itself, known as primitive types such as: integers (whole numbers), float-pointing (decimal numbers), and char (characters). We frequently use these types, and the operations that go with them, but many languages also give us the opportunity to define our own types, known as user-defined types. What this means is that we can store our own data and describe what operations we can carry out on that data with the help of certain data structures.

Data structures are then in many ways like data types. They are created in an analogous way to variables, requiring a name, specifying the data structure in use (more on this later), as well as the type of data it can store. What makes them different though is that they store more than one value, for example a data structure can store one integer, or it could store 100 integers, or it could be created to store 50 floating-point values, or any number of any type, both primitive, or user-defined. The operations of data structure are also different, instead of providing us a means in which to operate on the type of data it stores, they instead provide operations that can be carried out on all the data, also known as an element, stored within the structure. The operations commonly associated with data structures include:

  • Traversing: accessing all the data elements once and only once in the data structure and doing something with that data, such as updating all elements, or outputting them to the screen.
  • Inserting: adding new data to the data structure.
  • Deleting: deleting data that already exists in the data structure.
  • Merging: merge two data structures together.
  • Searching: attempt to the find location of a data element within the data structure, if it exists.
  • Sorting: order the data within the data structure, in some way, which usually depends upon the type of data being stored, i.e. numbers arranged smallest to largest.

We use data structures to store more than one element of data, the data we store is intended to be traversed, organised, sorted, and searched, and they allow insertion and deletion in as efficient a way as possible. Efficiency is determined by the design of the data structure, but also efficiency of a program can be determined in the choice of structure we use.

There are a broad range of data structures but they typically fall into two groups: linear and non-linear, both of which affect the way we interact with the data stored in the structure.

With linear data structures the data stored with them is stored sequentially, that means if we start at the 1st element in the structure, and want to get to the 4th element we must first traverse to the 2nd, then traverse from 2nd to 3rd, then finally from 3rd to 4th.

This isn’t the case with non-linear data structures, we don’t have to traverse through the data elements linearly, one after another. Elements of data can be linked to more than one element. This is achieved by having our data type not only store the data we want but also values containing addresses to other types which hold data and addresses, also commonly known as a node. This means we don’t necessarily have a 1st, 2nd, 3rd, 4th data element instead we have a root, which is the first node in our data structure, and this could store addresses that point to many different elements.

As previously mentioned deciding what data structure to use is important, and can have a huge effect on the overall efficiency of your program. Both in how the data structure is implemented in memory, and how the data is stored in that structure, linear or non-linear.

The main thing to take away from this article is to understand how they work, so that you know in what situation you can apply each one. This requires understanding a wide variety of different data structures and how they are implemented for each programming language, which can differ. This article is just an overview on data structures, so I will forgo any details regarding specifics, in favour of discussing them in detail in future posts.

To conclude a data structure is like a data type, but instead of defining operations to be that relate to the data itself, it instead allows storing of more than one piece of data, and defines operations that relate to the data it stores. We can create a data structure much like a variable by defining the data structure we want to use, the type to be stored within it, and a name to identify the address of the memory the data will be stored.

With variables and data structures discussed the following articles will focus back on concepts related to writing programs. How we can alter the instructions being executed using conditions, repeat instructions with the help of loops, and finally the organisation of instructions using functions. The next article will focus on the conditions, and how they help expand the potential of our programs.

Programming Fundamentals: Variables

Programming

memory-1761599_1920

The previous article gave a gentle introduction to creating programs, by explaining what they are, and how to go about writing them, using a set of basic principles, which can be read here. In this article, we will look at the first concept mentioned, the variable. Hopefully by the end of this article you will know all about what they are, and why we use them.

Before looking at variables we need to know a few things about memory. Memory is what we use in computers to store data, such as audio, and images, as well as programs. There are two main types: main memory, and secondary memory. Secondary memory such as hard drives (HDDs) and solid state drives (SSDs) are used to permanently store data when our computer is not switched on.

On the other hand, main memory is used to store the data and programs that we are currently using. When we open a program on our computer such as a web browser, this program will be stored in main memory. The specifics are not important, but I will say it’s done because main memory is a lot faster than secondary memory. Either way, main memory is divided into cells whereby each cell has its own unique address. These addresses are used to locate the cell, and get access to whatever is stored in it.

When we write programs, we will often need to store data in memory, and to do this we would need to know the address of cells which are not currently holding any data, and then proceed to use that address to store the type of data we want. An address can be a large value in the range of 0 to 4,294,967,295, which is a lot of potential locations. Imagine having to remember every address we have our data stored in, and if we had to access it frequently it would be rather boring to keep writing these large values out over and over again.

Fortunately, we are lucky in that the operating system, the program that tells the hardware in our computer what to do, works out what locations are free, and stores the data for us. All we need to do is tell the computer we want to store something and provide a name that we use as an identifier to access a unique location. The operating system makes an association between an address and the name we provide. The name is then used by us, and the operating system knows which address to look for.

After telling the computer we want to store the data, and giving it a name we then need to state what type of data it is we intend to store in that location.

Again though, before going any further it seems we need to take a slight detour and look at how data is stored in a computer. When it comes down to it computers only understand what is known as binary, 0s and 1s, and nothing else. Binary numbers are a sequence of 0s and 1s, for example, 010010, 01, 0, 0100111010, etc. I know in the previous article I said that computers understand programming languages, and well in a way they kind of do. They can take instructions given in these languages, and convert them down into binary, so that they can be executed, so I only half lied!

Instructions and any type of data: images, text, words, numbers, etc, are all stored in memory as binary. By writing out the type of data we want to store we are telling the computer how to treat the binary numbers stored at that location. Taking another example 010, what does this even mean? Not a whole lot, unless we give meaning to it.

We could give this sequence any meaning, for instance, we may decide that the digit furthest to the left represents red, the second green, and the third blue. Therefore, if we had 000, this could represent black (no colour), 111 white (using all the colours), 100 red, 010 green, and 001 blue. However, we could treat these numbers any way we want, the important thing here is that binary numbers represent all the data stored in our computer.

Therefore, when we declare the type for our variable we are telling the computer what data we want to store at a specific location, and then when we go to use that data the program knows what to do with it. A variable can then be described as

A named memory location for which we want to store a specific type of data

The location of where this data is being stored is within main memory, and this means the data we want to store won’t be stored permanently. Variables are intended to store temporary data needed by the instructions in our programs.

This may seem confusing, why would we want to store data that we are only going to lose when the computer is turned off? Well when writing our instructions for a program we will want to store data which our instructions will use. All programs will have input, this could be listening to a user pressing a key, typing in text, or moving a mouse, and then we want the program to respond to us in some way, provide an output. The input passed to our program needs to be stored somewhere so other instructions can make use of it.

Additionally, the instructions we write might require the storing of data. For instance, if we want to add two numbers up we could then store the result of this in a variable. We could then use another instruction to take that variable and output it to our screen so we can see the result, think of your calculator. This means that variables allow us to temporarily store data so that we can use the data at a later date in our program, but once we close our program, the data in those variables is lost.

Finally, I think it’s worth mentioning that variables are not fixed. What I mean by this is that we are able to change the data being stored at that location. If we had the variable called number we could write an instruction that adds two numbers together, 5 + 2, storing the result of this in number, the value stored being 7. Later in our program we could then add up two new numbers 6 + 8, and then store the result in the same variable, same memory location, which will overwrite the data already stored there. If we want to keep the previous value, then we could just create a new variable, say number2, and store our result of 6 + 8 in there instead. Note you should be using better variables names than the ones I have mentioned!

To sum up then, a variable is intended to be a temporary place to store data, which is stored in main memory at a unique address. We access that data by giving our variable a name, which the operating system then uses to retrieve data from that location. Variables are used alongside instructions in the programs we write to allow us to keep hold of data input by a user, or to store data we want to use at other points in our program, by other instructions. The data stored in these variables can be overwritten, and if we want to store more data we can simply create more variables.

Sometimes when we want to store a lot of values it’s better to store them within a data structure, as opposed to creating more variables. The next article will explore the use of data structures, how they are similar, yet different from variables, and look briefly at the different types of data structures.

Programming Fundamentals: Introduction

Programming

041017_1920_Programming1.jpg

Programming can seem quite complicated, and in some cases, it is, but that doesn’t mean that only geniuses can learn to do it. Starting our journey to becoming a programmer lies in understanding the principles behind writing code, which are rather simple. Before delving into these principles though, let’s make sure we all understand what a program is.

So, what exactly is a program, and what is it that these programmers do to make all the cool apps we use on our smartphones? Well fundamentally a program is a set of instructions that tells a computer to do something. A programmer’s job is to create programs, that is to give the computer instructions so that the computer can be used to carry out a specific task. Programs can be quite complex, but it is worth keeping in mind that no matter what you are programming, the basic concept applies, write instructions to tell the computer what to do. The instructions given to the computer are communicated in a way a machine can understand, and this is done using a programming language.

There are many programming languages that allow us to create programs for a computer, but each can differ in many ways. The main reasons being the purpose of the language, what types of programs the language was built to make, and what words make up that language. Regardless of these reasons there exists a set of core principles, that extend across all languages, and are therefore important to understand if wanting to learn anyone one of them.

Before discussing what, these principles are I thought it would be best to show a simple example of a set instructions written in English that we would give to someone who wanted to make a cup of tea, and then discuss why these instructions are not useful to a computer, and how these instructions could be translated into something that could be understood by one. The instructions for making a cup of tea can be described as:

  1. Place teabag in cup
  2. Add sugar
  3. Pour hot water
  4. Leave to brew
  5. Remove tea bag
  6. Add milk
  7. Stir

As you look at these instructions you may be wondering why we cannot simply give these instructions to a computer, and well it’s because computers are too dumb to understand them. A computer needs very simple and specific instructions to do anything, and our language is just too complicated. So, if that’s the case, then how can we translate the instructions above into something the computer understands? Well let’s pick apart these instructions and find out. Although a computer isn’t very good at understanding our language they are very good at understanding certain things: data, conditions, repetition, and functions.

Data is just a word that means information that a computer can use or store. A computer can store lots of different types of data: images, numbers, audio, words, and so forth. When we want to write a program, we will want to use or store data. In the above example, we can see a lot of information that is required for us to be able to make a cup of tea. We need to be aware of the amount of tea bags, hot water, sugar, and milk we have available. We can use variables to store this type of information, a single value that represents something we would like store.

Sometimes we may want to store more than a single value. Like a cupboard in our kitchen that stores all our cups, when writing a program, we may want to store lots of values of the same type of data. Data structures are a method that allow us to store a cupboard full of cups in our program.

When referring to the example if we look at instruction 3. Pour hot water. We know ourselves that this action means to pour water from the kettle into the cup, and because we can see the size of the cup and the water filling up the space in that cup we know that once the water nears the top of the cup we should stop pouring as not to spill it everywhere. Computers cannot do this naturally, but can be told to do so. We can use conditions to tell the computer that we want to execute certain instructions based on some condition that can make use of a variable, such as if we have any sugar then add sugar to the cup.

Additionally, pouring water, milk, or stirring are all events that involve repetition of an action, which is carried out, until a condition is met. We would keep adding sugar until the brew was sweet enough for our taste, we would pour the water in until it wasn’t far of the top of the cup, we would add milk until we got the colour we wanted, and we would stir until the sugar had dissolved. Computers can be told to carry out instructions repeatedly using a condition that specifies how many times we repeat a set of instructions.

What if we wanted to make tea for 3 of our friends? We would have to repeat the set of instructions 3 times for each person, meaning we would have 21 instructions to carry out, most of these are repeating the same steps. To make it easier for us to tell the computer to carry out a repeated set of instructions, we can place them in functions. To make tea for 3 friends we would need to use repetition to call the function three times to execute all the instructions, based on the condition that all 3 of our friends had a cup of tea.

Finally, instructions provided to make a cup of tea, require that we follow them in order from step 1 to 7. At least with this example we could alter the order in which add the various components of a cup of tea: water, milk, tea, and sugar. However, we must be sure that the water is hot before we add it, and that all ingredients are placed in the cup before stirring. Writing programs works the same way, we must ensure that our instructions are written out in the correct order, otherwise things are bound to go wrong, or not work at all.

As you can see writing programs comes down to writing instructions using a programming language, where these instructions are used to tell the computer to do something. There exist many languages, which each have their purpose, but underlying all of them is a set of principles that if understood allow you to write programs no matter the language. Computers cannot understand the complexities of our language, but they are able of understanding certain things.

  • They can use and store information, as a single value, or as multiple.
  • They can be told to carry out a set of instructions based on a certain condition, and can use a condition as the basis of repeating a set of instructions multiple times.
  • Finally, instructions that we want executed multiple times can be placed in functions, removing the need to write the same instructions multiple times.

This article has provided a basic overview of a program, programming, and the fundamentals, and how they apply to a simple example of making a cup of tea. The next article will discuss more in depth the concept of variables, their uses, and their importance in the role of creating programs.