# Data Structures and Algorithms - Part I

• Sreeraj T A
• April 30,2019

"How to learn data structures and algorithms?" is a query I have seen many of my peers making, and that is the reason I have decided to write a series of posts aiming to teach data structures and algorithms byte by byte. This is the first post in the series and in this I won't be covering "how to balance a binary search tree?" , "what is and how to implement a hash table?" or anything of that sort (which will eventually be covered in future posts), but instead an important prerequisite is discussed here , which is "What are data structures and algorithms and why learn them?"

Before moving forward let's see a quote by Linus Torvalds:

"....I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships." -Linus Torvalds

Coming from someone like Torvalds that quote should be a good motivation to study data structures and algorithms. (If not just ignore it).

Learning data structures and algorithms would definitely make you a better programmer. You could think of it as like patterns for solving problems. The more patterns you know the easier it will be to recognise it as a solution to a problem.

### What are algorithms?

As a programmer your job is to usually tell the computer what task to perform or what problem to solve and an algorithm is a detailed step-by-step instruction set or formula for solving a problem or completing a task.

So simply put an algorithm is a series of steps to be followed in order to achieve a task.  (for some formal definitions maybe you can check wikipedia or the internet, though not really necessary to follow this.)

### What are data structures?

A data structure is an orderly arrangement of data,the relationships among them and the function or operations that can be applied on the data. So in very simple terms a data structure organises data in a format that enables efficient access and modification of the data. An example would be the 'array' data structure which is a list of elements stored in consecutive memory locations. (we will cover the details in later posts)

Let's consider a simple example to illustrate how the knowledge of data structures and algorithms could aid you in solving a problem.

Suppose you want to go from your home to office in the shortest possible way and imagine the below image represents the possible routes from your home leading to your office :-

I have highlighted two possible paths you can go by. Some routes are more congested than others(I have represented the congestion of each road with a number,higher the number more congested the road is). So the aim is avoid the congested paths.
Let's see the case If you were to use a map/navigation service how it would find a solution to the problem.

Before that we got to go over a data structure and an algorithm , namely the graph data structure and the Djkstra's algorithm. I will cover both in detail in later posts but for now we will see just enough for the sake of understanding how to solve the problem.

##### The graph data structure:

Formally, a graph is a pair of sets (V, E), where V is the set of vertices and E is the set of edges, connecting the pairs of vertices.

In simpler terms a graph is a non-linear data structure consisting of nodes(vertices) and edges .The edges are lines or arcs that connect any two vertices in the graph.

Graphs is usually used to represent networks. For example a social network can be represented by a graph in which each vertex represents a person and the edges representing the connections between these people and each vertex can be a structure containing the name,age ,gender etc. of the person.

Note: Weight refers to labels assigned to edges in a graph, usually numerical values representing something like the length between two nodes,the cost of moving from one node to another etc.

##### Dijkstra's Algorithm:

Dijkstra's Algorithm allows you to calculate the shortest path between a given node(source vertex) and every other node in a graph.

The algorithm is as follows (note that is is a series of steps just like I said earlier):
step1: Set the distance to the source to 0 and the distance to the remaining nodes to infinity.
step2: Set the non-visited vertex with the smallest distance as the current vertex curr
step3: For each neighbour N of curr:

• Add the distance of the current node to the weight of the edge connecting curr to N
• If it's smaller than the current distance of N, set it as the new current distance of N

step4: Mark curr as visited
step5: If there are unvisited nodes go to step2

In the example above A is taken as the source node.Initially  the distance to A is set to zero and to the rest of the nodes at infinity . Since A is the node with the least distance value it is taken as the current node. Then step3 in the algorithm is done for each of the neighbours of A , that is B and E, resulting in distance values of 3 for B and 2 for E. Now A is marked as visited .

Choose another current node and repeat the process . The distance values obtained for each node after all the nodes are visited represents the minimum distance from that node to the source.

To obtain the paths that correspond to those minimum values, we simply need to keep track of the nodes every time we change the minimum distance of a node
We will see how it is done in later posts, for now what is to be noted is Djkstra's algorithm can be used to find the shortest path from a node to all other nodes in a graph.

Now with this knowledge coming back to our problem of shortest distance from home to office  we could simply model the problem as a graph with one vertex as the home, one vertex as the office and the intersection points of roads as other vertices. The congestion is represented by the weights of the edges. Then taking the home node as source we can apply Djkstra's algorithm to obtain the shortest distance.

So when you get a problem once you identify a pattern or identify what algorithm and data structures would be suitable to solve it, you can simply find some library implementation of the algorithm or data structure and obtain a solution to the problem . (Yup ,don't bother reinventing the wheel, but if you know enough of it's dynamics you can maybe modify it to suit your needs) .

Algorithm is omnipresent , whether the case is making a baby or finding your next f-buddy(or even your soulmate) via that dating app or finding the best route to ride to your office.

And if you ever feel like why should I take a look at all these patterns , remember:

"Every program depends on algorithms and data structures,but few programs depends on the invention of brand new ones" .

In the next post we will be taking a look at Time complexity analysis of algorithms. (simply put , the time it takes to run an algorithm, measuring helps to find the better solution when there are multiple solutions to a problem.)