Data Structures and Algorithms — scratching the surface
Hello, Myself Gauri wankhade,
Software Developer, Bangalore, India
In this article we will be talking about basics of Data Structures and Algorithms.
What are Data structures and Algorithms?
The data structure is the way of organising data. Algorithms are way of using data structures effectively to solve a problem.
Types of data structures
There are mainly two types of data structures — linear and non-linear.
Linear data structures are way of storing data in linear manner, where we can access element by going sequentially preferably by using index.
Ex. For given Array, index resides in the range of 0 to length of Array.
NumArray = [1, 2, 3, 4, 5]
// access element at index 2elem = NumArray[2]// elem is 3
Non-linear data structures are designed to access elements in certain way where sequential access is not suitable. Ex. Tree, Graph, Heap etc
What is Tree data structure?
Well, imagine a normal tree upside down
By the look of it we can say it is not something conventional to explore just like walking down a road or traversing list of elements. In order to explore tree we need to understand its structure.
Tree is the data structure where each node stores some value and address of its left node and right node. A node which has no parent considered as root node of tree. Here, node with value 1 is the root node, which stores the address of node-2 and node-3.
Basic idea of exploring tree is considering one node at a time and exploring its child nodes (left and right nodes).
Methods to explore Tree
- Preorder traversal
- Postorder traversal
- Inorder traversal
refer for more details. https://www.educba.com/tree-traversal-in-data-structure/
What is Graph?
Graph is nothing but collection of vertices and edges joining those vertices.
How Tree is different from Graph?
In tree data structure we can move from parent node to child node but vice versa is not possible. In the graph there is no concept of parent-child relationship. If two nodes are connected by edge and the edge is undirected, that means nodes are neighbours and data flow is bidirectional.
One of the important aspect of Tree and Graph is — every tree is a graph without cycles. If you remove all the cycles from graph it will create a tree.
In the above example, we removed edge DE to convert graph into tree. Such edges are knows as Back edge. Presence of back edge indicates there is a cycle in graph. This idea gives rise to concept of spanning tree.
What is Spanning Tree?
We can say spanning tree is a tree derived from graph. When we remove all the back edges from graph all we have left is tree. Technically spanning tree is a subset of graph having all the vertices and minimum number of edges.
What is Minimum Cost Spanning Tree?
We can derive minimum cost spanning tree for weighted graph, it means each edge will have some weight/cost. If the sum of cost of edges of spanning tree is minimum of all possible spanning trees, then it is said to be minimum cost spanning tree.
Methods to find MCST
- Kruskal’s Algorithm
- Prim’s Algorithm
Algorithm analysis
In order to come up with the most effective approach to solve any problem there has to be a way to measure existing approaches and choose the best one among them.
Asymptotic notations are mathematical tools for representing performance of algorithm in terms of time complexity.
Many people relate time complexity of algorithm with time taken by computer to execute that algorithm. Which I would say partially incorrect.
Time complexity is number of times statement executed.
Arr = [4, 3, 2, 7, 8]// time complexity to find 4 in the Arr is 1
// time complexity to find 8 in the Arr is 5, because length of // Arr is 5
In above example we had to traverse only one element to find 4 in array. In case of 8, we have traversed entire array to find 8 at the end which makes time complexity of operation to 5.
There are three ways to represent time complexity using asymptotic notations
- Best-Case complexity (Omega notation)
- Worst-Case complexity (Big O notation)
- Average-Case complexity (Theta notation)
In the given list of elements there is possibility that the element we are looking for is the first element of list. That is the best-case scenario. In the worst-case scenario, element we are looking for is found at the last. Generally we consider worst-case scenario (Big O notation) in algorithm analysis.
Examples of time complexity
- O(1) constant time complexity
For a given list of the elements if the number of times the statement to be executed is not dependent on input then we can say operation has constant time complexity.
2. O(N) Linear time complexity
For a given list of elements, if number of time statement to be executed is same as number of elements in the list then operation has linear time complexity.
3. O(logn)
To understand O(logn) complexity let’s consider the example of binary search.
We are looking for 5 in the given sorted list of elements.
Arr = [1, 2, 3, 4, 5, 6]
// initially, low is 0 and high is highest index which is length of Arr minus 1low = 0
high = 6 - 1
mid = (low + high) / 2
mid = (0 + 5) / 2
check if
- Arr[mid] is equal to 5
- If yes — return mid
- If no —
- Check Arr[mid] < 5. If yes, update low = mid + 1
- Else check Arr[mid] > 5. If yes, update high = mid-1
So, by using binary search it took two iterations to find element 5 in the given list.
What would be the number of iterations if we simply check each and every element to search for 5? Since, 5 is 5th element of list, it will take 5 iterations to locate element.
In the binary search we keep on dividing Array into half. Based on conditions we decide which half to consider until we find desired element. It makes the time complexity of operation to O(logN) where N is the number of elements in array.
For Array of length N = 8
O(logN) = O(log8)
we can say, 8 = 2 * 2 * 2
i.e 8 = 2^3O(logN) = O(2^3)
O(logN) = 3 * O(2)
From the above illustration we can assume time complexity to search element in given array of length 8 is 3. That means Array will be keep on reduce to half up to three iterations.
Please do share and like if you find the article useful. Follow me on medium Gauri wankhade and on Twitter at gauri_infj.
Thanks!!!
Happy Learning…
