From the origin of the first programming languages to the modern programming languages currently in use, computer programming has evolved quite a lot. It has now become more powerful, efficient, and advanced. However, the fundamental concepts and use of data structure and algorithms in computer programming have not changed. DSA has been the core of computer programming from the beginning.
You might have heard DSA being used mainly in the field of computer science. However, the use of DSA is not limited to the field of computing. We can also find the concept of DSA being used in day to day life. In this blog, we will discuss the common concept of DSA that is used in everyday life. But before that, let's learn the basics of Data Structure and Algorithms first.
What is Data Structure and Algorithm (DSA)?
Data structure and algorithms is a branch of computer science that deals with creating machine-efficient and optimized computer programs. The term Data Structure refers to the storage and organization of data, and Algorithm refers to the step by step procedure to solve a problem. By combining "data structure" and "algorithm", we optimize the codes in software engineering.
DSA in Software Development
Data structure and Algorithm (DSA) is applied in all disciplines of software development. DSA is the building block of the software development process. It is not limited to a single programming language. Although programming languages evolve or get dormant over time, DSA is incorporated into all of these languages.
The efficiency of software development depends on the choice of an appropriate data structure and algorithm.
There might be cases when you are provided with the most efficient data structure to work with a robust algorithm. However, if the two are not compatible with each other, the code will not produce the expected outcome. Thus, selecting an appropriate data structure for an algorithm is an essential part of software development.
Take, for example, the imperial system of measurement used in the US. Why is it so dreadful? The US has been using measuring units like inches, yard, miles, ounce, and pound for measurements. If you need to convert a yard into inches, you have to multiply it by 36. However, in the metric system, you can simply multiply by 1000 to convert meter into kilometer. It is thus easier for the mind to do the conversion in the metric system. That is why most people find the imperial system to be inconvenient. Another example of this inconvenience is that "ounce" is used for solid or liquid depending on the context.
The ease of conversion from one to another metric is the most important factor here. In this example, we can compare the measurement systems (i.e. the metric system and the Imperial system) to "data structures", while the process of conversion from one unit to another can be thought of as the algorithm. This shows that choosing the right data structure has a great impact on the algorithm, and vice-versa.
Another critical facet of DSA usage in software development is the time and space constraints. These constraints check the availability of time and space for the algorithm. An optimized algorithm addresses both of these constraints based on the availability of resources. If memory is not an issue for the hardware, DSA focuses more on optimizing the running time of the algorithm. Similarly, if the hardware has both the constraints, then DSA must address both of them. You can learn more about the representation of these complexities on Asymptotics Analysis.
How can you relate DSA to your day to day life?
Let's dive into some of the examples of the usage of DSA.
Stack Data Structure to Reverse a String
A stack is a linear data structure, "linear" meaning the elements are placed one after the other. An element can be accessed only after accessing the previous elements.
We can visualize a stack like a pile of plates placed on top of each other. Each plate below the topmost plate cannot be directly accessed until the plates above are removed. Plates can be added and removed from the top only.
Each plate is an element and the pile is the stack. In the programming terms, each plate is a variable and the pile is a data structure.
Why do we need a stack representation?
You might be wondering why a programmer needs to learn how to put a plate on a pile and take the plate out from the pile. Let's find the answer to it. You are assigned a task of reversing a string. How would you do it?
Start selecting a character from the string and copy it into the new location one by one.
Now, let us copy these items from the top into the original location.
Great, we have successfully reversed a string using the property of stack (the new memory). Inserting and removing was only allowed from the top. This way stack is used in programming.
Queue Data Structure while Boarding a Bus
A Queue is also a linear data structure in which the elements are arranged based on FIFO (First In First Out) rule. It is like the passengers standing in a queue to board a bus. The person who first gets into the queue is the one who first gets on the bus. The new passengers can join the queue from the back whereas passengers get on the bus from the front.
Why do we need a Queue representation?
You may ask where a queue is used on a computer. Assume that you are in your office and there is a network of five computers. You have connected all these computers to a single printer. Suppose an employee wants to print his documents and sends a command to the printer through his computer. The printer receives the commands and starts printing the documents. At the same time, another employee sends commands to the printer. The printer puts the second command to the queue. The second command is executed only after the execution of the first command. This follows the FIFO rule.
Graph Data Structure in Social Media and Google Map
A Graph is a network of interconnected items. Each item is known as a node and the connection between them is known as the edge.
You probably use social media like Facebook, LinkedIn, Instagram, and so on. Social media is a great example of a graph being used. Social media uses graphs to store information about each user. Here, every user is a node just like in Graph. And, if one user, let's call him Jack, becomes friends with another user, Rose, then there exists an edge (connection) between Jack and Rose. Likewise, the more we are connected with people, the nodes and edges of the graph keep on increasing.
Similarly, Google Map is another example where Graphs are used. In the case of the Google Map, every location is considered as nodes, and roads between locations are considered as edges. And, when one has to move from one location to another, the Google Map uses various Graph-based algorithms to find the shortest path. We will discuss this later in this blog.
Sorting Algorithm to Arrange Books in the Shelf
In simple terms, sorting is a process of arranging similar items systematically. For example, suppose you are arranging books on a shelf, based on the height of the books. In this case we can keep the taller books on the left followed by the shorter books or we can do vice versa.
This same concept is implemented in Sorting algorithms. Different sorting algorithms are available in DSA. Although the purpose of every algorithm remains the same, each algorithm works differently based on various criteria.
In the above example, if we want to sort the books as fast as we can then there are few points to be considered.
- Can the books be easily shuffled on the shelf? If the books are heavy, it may take us more time. Similarly, there may be other constraints. (accessibility)
- What is the number of books? (data size)
- How fast can we access them? (hardware's ability)
Algorithms are built considering all these constraints to produce an optimal solution. Some of the examples of these algorithms are Bubble Sort, Selection Sort, Merge Sort, Heap Sort, and Quick Sort.
Searching Algorithm to Find a Book in a Shelf
Searching, as its name suggests, helps in finding an item.
Suppose you want to search for a specific book on a shelf. The books in the self are not arranged in a specific way. If you need to find the book in the shortest possible time, how would you do that? The solution to this is provided by DSA.
You may be thinking "I will look for the book from the beginning and locate it". In this case, you will be searching for books one by one from the start to the end of the shelf. This same concept is implemented in Linear Search.
But, what if the book is at the other end of the shelf? The above process might take a long time and will not provide a feasible solution.
Now, let's try another procedure. Firstly, sort the books in ascending alphabetical order then search for the book in the middle. We are searching for a book that starts with J.
Since we are always looking at the middle position, the middle position between A and Z is M, not J.
Now, compare J with M. We know that J lies before M. So let's start searching for J in the middle position of A and M. G is the mid element, again J is not found.
Since J lies between G and M, let's find the mid element between them. Yeah, we have found J. Congratulations!!! ?.
And, you have just implemented Binary Search.
Shortest Path Finding Algorithms to Find the Shortest Path in Google Map
Have you ever thought about how Google Maps is able to show you the shortest path to your destination? Applications such as Google Maps are able to do that using a class of algorithms called Shortest Path Finding Algorithms.
These algorithms deal with finding the shortest path in a graph. As in the example discussed in the Graph data structure above, we can use graph algorithms to find the shortest path between two given locations on a map.
To illustrate the problem, let's find the shortest distance between A and F in the following map.
What are the possible solutions to this problem? Let's figure out the possible routes along with their path length.
We can see that the shortest path is Path-3. But, we have wasted time calculating other paths as well, which we are not going to use. In order to solve this problem without wasting time, we can start from A and check for the possible shortest neighboring paths (AC and AB). We have AC as the shortest path.
Now we are at C, again select the shortest path among its neighboring paths CE and CD, which is CD.
From D, we have a single path to F. From D, we can go to B as well but, B is already visited, so it is not considered. Select the path DF and we reach the destination.
Congratulations one more time?. You have implemented Dijkstra's Algorithm. In this way, the graph finds its use in our life.
When I was in the final year of my undergraduate studies and applying for software engineering positions, there was one thing common between the hiring procedure of all companies. They all tested me on problems that involved the use of data structures and algorithms. DSA has great importance in the recruitment process of software companies as well. Recruiters use DSA to test the ability of the programmer because it shows the problem-solving capability of the candidate.
As you can see from the above examples, we are able to relate DSA with our day to day life and make it more fun to study. For those who are from non-technical backgrounds, they can also learn the techniques used in the algorithms for solving their daily problems.
Furthermore, one cannot neglect the importance of DSA in any programming language. DSA never gets extinct, rather it is evolving because the evolving computers, in the 21st century, need evolving algorithms to solve a complex problem.
Not to mention, a programmer should know how to use an appropriate data structure in the right algorithm. There is a famous saying:
A warrior should not just possess a weapon, he must know when and how to use it.
Best wishes to all the new programmers out there. Start your learning from today.