data structures and algorithm

Understanding the Heap Datastructure

Introduction Heap(specifically binary heap) is a special data structure which can be viewed as a nearly complete binary tree. This post is mostly focused on understanding the heap datastructure The first few impressions about heap after reading the above line: The height of the binary tree would be minimum. For e.g.: if the tree has N nodes, the height would be logN. The tree can also be stored in an array, in fact it would be easier to store this tree in an array (because it is complete). This makes it an awesome data structure because the minimum height guarantees logN running ti...
Read More

Adding numbers using Linked Lists

Introduction Adding numbers has always been fascinating and you may think it to be the easiest mathematical operation possible. But believe me many a times that becomes the toughest problem to solve. Let us discuss this in more detail. It is really easy to add two numbers stored in two memory locations. The ALU provides you the option to use the ADD feature and store it on the DATA bus. This is feasible when both the numbers can fit on the DATA bus one at a time. So, what about adding excessively large numbers, I know that the limit of BigInteger, Long, Double etc is too huge. But what if ...
Read More

Reversing a Singly Linked List

Introduction Many people have asked me to explain the dynamics of how the reversing of a singly linked list works, when we do not have the liberty of creating a new linked list, may be due to limitation of memory. The Idea behind Reversing a Singly Linked List The idea is to iterate through the complete linked list and maintain three pointers as listed below: Pointer to the head of un reversed list headOfUnReversedLL. Pointer to the head of reversed list headOfReversedLL. Pointer to the node to be reversed nodeToReverse. In each iteration we follow the below four steps: The h...
Read More

Shortest Path Using Bellman Ford Algorithm

Introduction This post about Bellman Ford Algorithm is a continuation of the post Shortest Path Using Dijkstra's Algorithm. While learning about the Dijkstra's way, we learnt that it is really efficient an algorithm to find the single source shortest path in any graph provided it has no negative weight edges and no negative weight cycles. The running time of the Dijkstra's Algorithm is also promising, O(E +VlogV) depending on our choice of data structure to implement the required Priority Queue. Why Bellman Ford Algorithm? There can be scenarios where a graph may contain negative weight ...
Read More

Further Reading for Minimum Spanning Tree

Introduction This is a supplement to the posts for Minimum Spanning Tree and their Analysis. Check out the other related articles in the following section. Further Reading for Minimum Spanning Tree This section is meant to be read in conjunction to the post Minimum Spanning Tree - Prim's Algorithm The minimum spanning tree of a Graph is the union of minimum spanning trees of its connected components. This is a very important observation and it must be discussed in length and breadth because this will help us design our algorithm for MST in a better way. Why is it so important to underst...
Read More

Shortest Path using Dijkstra’s Algorithm

Introduction This is the third post in the Graph Traversals – Online Classes. After learning how to move through a graph, we might be interested in learning more. One interesting problem is determining the shortest path between two vertices of a graph. The problem can be extended and defined in many other forms. I prefer to call it "minimizing the cost". For e.g. When we measure the cost in terms of the distances between vertices, it can be called as the Shortest Path. When we measure the cost in terms of the money spent between vertices, it can be called as the Cheapest Path. Whe...
Read More

Depth First Traversal

Introduction This is the second post in the Graph Traversals – Online Classes. I Recommend you to look at the first post Breadth First Traversal as it contains more explanation and details and I will keep this post smaller just around the depth first concept. Depth First Traversal The Idea In this traversal, we choose a start vertex and keep moving forward along the length of the graph until there is no undiscovered vertex in that path. Once reaching a dead end, we back track to all the visited vertices and check if we have any vertex which has an adjacent undiscovered vertex. We kee...
Read More