Understanding how to solve an algorithm problem becomes easier when we know the underlying factors to consider when approaching a problem. These basic factors are what this article helps to understand.
First, Let’s start with what an algorithm is.
What is an Algorithm?
Algorithms are step-by-step instructions on how to solve a problem. It identifies what is to be done and(the instructions) and the order in which they should be done. It can be represented using pseudocode or flowchart.
For example:
The algorithm for making a cup of tea might look something like this:
Fill the Electric kettle with water.
Bring to boil.
Pour water into a cup.
Put the teabag in the cup.
Steep for about 3 minutes.
Remove Tea Bag.
This can be eventually translated to computer instructions using programming languages
Given a more definite example like finding the maximum value in the list of numbers say; 27, 31, 42, 26, 10, 44, 35, 19, 33, 14.
Mere scanning through this set of numbers, you can immediately see the largest value but a computer can not scan-search as humans do. Even humans will not be able to come up with the answer when the data is many.
A computer can only compare two things at a time, ie, the algorithm must be expressed in terms of binary comparison.
So then, the linear approach a computer will take to look for the largest value might look something like this:
Read first item and store value as max
Look at each other item in the list, If it is greater, then the value becomes the new max
After going through the entire list, the current max is the largest value on the list.
For a better understanding of how data structure come to play, let’s look at another example,
eg, Determining whether a list contains a given value, say 33 in the previous list of numbers.
Let come up with an algorithm to solve this, which might look something like this:
Keep the given value as the target,
Look at each value in the list,
If one is equal to the target, then we have found the value and we can stop looking.
If we go through the entire list and have not found the target, then it is not on the list.
This seems effective right?, but if the list is very long, it can take the computer a very long time to look through the entire list(this is called execution time). How much execution time it will take is what is referred to as Algorithm Complexity
Complexity is a way of expressing the number of steps or operations in an algorithm. It gives us an idea of how long it will take for an algorithm to execute.
We naturally expect an algorithm to take longer as input increases, but how much longer?
Complexity is therefore expressed as a function of the number of elements in the input data.
So, when we analyze algorithms,
We consider the number of operation that needs to be performed We also consider complexity in the worst case, so we can see the changes in operations when the input size increases For example;
We could stop when we find the target in the example above, but what happens when we have to look through every item on the list? That means if the number of items in the list increases, then we have to do more comparison through the entire list in cases where the target is not there, say 30. This is the worst case of these algorithms.
Well, what can we do better, What if the item on the list were ordered?
Consider our previous example: 27, 31, 42, 26, 10, 44, 35, 19, 33, 14.
In the ordered version, searching for 33 becomes faster
With this structure of data, searching for an item that is not in the list, say 30, becomes even easier. The computer would not have to search through the entire list, we can just stop when the next comparison value is greater than the target we are looking for. It can stop looking immediately it gets to 31 because it is greater than our target 30.
This leads us to the Data structure.
A data structure is a data organization management and storage format that enables efficient access and modification. It provides a means to manage large amounts of data efficiently. It is the way of organizing data in memory such that it is easy to access.
There are many ways to store data in software engineering. Some ways are significantly better than the other depending on the requirements, say less memory, faster access or ease of modification.
The following are some of the available data structures:
Array
List
LinkedList
ArrayList
HashTables
Dictionary
Generic Collections
Stack
Queue
Tree
Graphs
This should now give you a clearer view of algorithms and data structure even if this is the first time you heard of it.
In our subsequent article, we will look at some of these data structures, and also a better algorithm to look for our given value in our earlier example.
We searched through the list using a Linear approach. A linear algorithm is one in which the number of operations increases linearly as the increase in the input size. We shall also look at a better and faster approach called the Binary Search Algorithm.