Floyd’s cycle detection algorithm uses O(1) memory and O(n) time for cycle detection.

There are 3 activities in this algorithm.

1. Find if there is a cycle

2. Find first node of the cycle

3. Find length of cycle Read the rest of this entry »

Programming, Algorithms etc

Floyd’s cycle detection algorithm uses O(1) memory and O(n) time for cycle detection.

There are 3 activities in this algorithm.

1. Find if there is a cycle

2. Find first node of the cycle

3. Find length of cycle Read the rest of this entry »

Advertisements

Union-Find can be used to union two graph components and find the representative of each component. Below code unions the components in a certain way, so that it maintains the representative. The operations are performed in O(logn) time. Read the rest of this entry »

Diameter of a tree can be calculated by calculating two maximum lengths of children of root node and adding 2 to it. Read the rest of this entry »

Number of nodes in a tree can be calculated from any node relating to its subtree. We can use dynamic programming to store count of subtree and add values to current node. Read the rest of this entry »

Floyd-Warshall algorithm also finds shortest path similar to other algorithms like Bellman-Ford and Dijkastra. However unlike those algorithms Floyd-Warshall finds shortest paths from each node to all other nodes. In Bellman-Ford and Dijkastra shortest paths are calculated from source node to all other nodes. Floyd-Warshall algorithm’s runtime is O(n^3). Read the rest of this entry »

Like Bellman-Ford algorithm Dijkastra algorithm finds shortest path from a node to all other nodes in the tree. Dijkastra algorithm selects a node whose distance is least from all the nodes that can be currently reachable (from previous search) or from current node. For this the algorithm maintains a priority queue, that puts node with least distance at top. If a node has already been processed, it escapes processing that node. Time complexity is O(n+mlogm). For n nodes at most one distance is calculated. Initially distance to source node is set to 0 and pushed to the queue.

Bellman-Ford algorithm can be used to find shortest path from a source node to all other nodes in the graph. Time complexity of this algorithm is O(nm). Here, n-1 is number of nodes and m is number of edeges. An outer loop runs for n turns and in each of that turn all edges are evaluated, to see if they shorten the distance to a particular node. If so, distance to that node is updated with new value. All nodes except source are initialized to INF. This algorithm assumes there are no negative edges in the graph. Read the rest of this entry »

Segment Tree unlike binary index tree is little bit more complex to implement, but is more flexible and supports more range query operations. It also takes double the size of input array.

The idea is to store the array values in second half of the tree, and using that store value corresponding to the operation supported in its parent. For a node k its parent is at k/2. For node k, 2 * k and 2 * k + 1 are its children node indices. Using this information we can build and query segment tree. It is obvious from these rules, that the operation are performed in O(logn). Note, even nodes are left child and odd nodes are right child. Following is the source code for sum query.

Fenwick Tree can be used for range query operations with support for update in O(logn) time. Both of these operations can be done in O(logn) time. Another data structure that supports the operations in O(logn) time is segment tree. However, Fenwick tree is less complex data structure. Read the rest of this entry »

Backtracking problems tries to create a solution tree, once previous instances pass. If condition fails at some point, it backtracks to the previous instance where it was successful, and try other possible options.