How I learnt Data Structures and Algorithms
What is Data Structures & Algorithms?
When it comes to Computer Science, data structures and algorithms is considered as one of the most important subject. It acts as a litmus test to separate out good developers from the rest. And due to this reason you would always see big tech companies focusing on DSA while interviewing a candidate. But what are Data Structures? How can a common man understand it? Simply putting it this way: Data Structures are different types of storages in which you can keep your data. And algorithms, define how we can access and manipulate that data.
My journey to learn data structures and algorithms began almost a year ago. I have a big bold Master’s degree in Mathematics. So for me it was easy to get convinced about the “theory” of anything. But at the time I was doing my thesis, it was revealed upon me how important it is to be skilled in at least one programming language. And along with this revelation came the introduction of DSA. My learning journey started with rather easy data structure like array, and then when I dig deeper, interestingly, I started to see an undeniable connection between real life examples and these Data structures, which not only made my learning process faster but also quite interesting. I will share a glimpse of what and how I learnt about DSA in this 12 months’ period.
Stacks
Consider you are piling up your folded tees in a drawer. You know that you can only pick a shirt that is on the top. And if you want to choose the third shirt from the top you would have to remove first two to reach to the third. Otherwise you can think of the consequence, a disaster in your drawer!! So, while performing this unattractive chore you might have noticed how this pile (storage) is working. Whatever goes in last, will come out first. Congratulations! You have learnt one Data Structure, the Stack. This LIFO (last in first out) type DS comes really handy to the developers, yet you see how it is picked from the daily life experiences. To practice this DS on coding problem, I picked a website Leetcode.com. And with every accepted solution, my concepts started getting stronger. Here’s one of my first code on a problem involving stack:
Queues
One on fine evening, you are standing in a takeaway line of Mcdonald’s waiting for your turn to pick your order. As your tummy makes funny sounds you start wondering if somehow you could break the line and let yourself served first. But you know that’s not possible. You are in a queue. The one standing at the front will be served first. And yes this is how the Data structure “Queue” work. Often called as the FIFO (first in first out), this DS plays a very significant role in solving complex coding problems that we will see in a moment.
You might be wondering not all queues work like this. In a hospital emergency department, for example, a serious patient doesn’t wait for his turn to get himself treated. Well, you are right sir. In this case, we refer to the “Priority Queue”. It is a data structure in which the elements (patients in this example) will be treated according to the priority assigned to them. This interesting problem explains the use of priority queue very clearly, where two heaviest stones in a group are smashed together to get a stone whose weight is equal to the difference of smashed stones’ weights:
Trees
Searching your graduation photos on computer, you know very well, where did you keep them.
My computer -> D drive -> Pictures -> Graduation photos.
You do it every time, while searching for any folder or document on your PC. This hierarchical traversal that ease down your search process is based on the Data Structure the “Trees”. A very powerful DS which allows you to search for the keys (anything) in a moderate time very efficiently. In the following code, I applied Breadth first Search (one of my favorite search algorithm) on a Binary tree to find its minimum depth.
Binary Search
Imagine you slept while reading a novel last night, and today, you intend to finish reading it. So you open the page 213, where you left last time. But wait, did you just notice how you reached to that page 213? Did you start turning pages starting from first page? Certainly not. You would have randomly opened the page and then by looking at that page number you decide whether to turn pages forward or backward. You might do it multiple times to reach your target page. Isn’t it amazing, that how your brain makes use of the fact that the page numbers are sorted in ascending order. And instead of searching linearly, it applied another type of search. Mathematicians refined this search a little and named it “Binary search”. In which, instead of randomly opening the book in every turn you part it from the exact middle and then decide whether to move forward or backward depending upon the middle value. This Binary Search Algorithm is extensively used in the problems where you are provided with sorted data. Still not convinced with the power of the Binary search? You can find out square root of a number using a binary search. Interesting eh?
Topological Sort
You are running late from school. And you have to get ready. It is cold out there, so you have to dress in layers. First, the shirt and trousers and then you wear one sweater, a cardigan and a coat. Then you wear beanie, after that, your socks and then the boots. What if you wear your shoes before wearing your beanie? Nothing would happen right? Okay what if you put on your shoes first before you wear the trousers. Now it’s a mess. Do you see this linear ordering that you follow? It is very important. It is known as a “Topological Sort”. And you would see multiple daily life examples where different objects must be linearly (without having loops) related to each other in order to make sense. So checking whether they can be sorted topologically or not comes very handy. And one way to check that is through the Kahn’s algorithm. In computer science, it comes under the category of Graphs, the most advanced Data Structure and it has a high impact on solving the complex real life problems through programming. This example explains the similar problem of finding whether a student can pick all the given courses, when some courses have prerequisites.
That was the glimpse of my journey towards learning Data Structure and Algorithms. Reaching to the milestone of graph problems was a big achievement for me. But as Matthew McConaughey said in his Oscars winning speech;
“My hero is me in ten years. I am never going to be my hero. I am not going to attain that. And that’s completely fine. Because it keeps me with somebody to keep on chasing”.
So although one year ago my ideal was me at present. But now it’s me after one year. I have come a long way, learning DS and algorithms, gaining skills which are exceptional to have for a Math major. But I know I am not stopping. There’s a lot to learn yet. The peak is still far away. And the climb is never-ending.