Miscellaneous

Learning Sites:

To learn Click Here

Some Problems About Linked List

Dynamic Memory Allocation:

Code Snippet:

BellmanFord Algorithm:

Take all the edge in a struct as:

Relax all the edge for (node-1)(e.g. total number of node of the vertex) number of time.

After that check one more time if all the edges are relaxed(minimized valued from source) or not.

If there found any  edge not minimized then negative cycle exists.

kadane’s algorithm:

Implementation:

For 1D array:

•  take 2 variable : max_end_here = 0 && max_so_far = 0
• for all the elements of the 1d array starting from the beginning
• add elements with max_end_here and compare it with 0 and max_so_far
• if max_end_here< 0 then assign max_end_here 0
• if max_end_here > max_so_far than update max_so_far
• after doing it for all the elements of the array return max_so_far

Code Snippet:

For 2D array:

Travelling Salesman Problem:

Let the given set of vertices be {1, 2, 3, 4,….n}. Let us consider 1 as starting and ending point of output. For every other vertex i (other than 1), we find the minimum cost path with 1 as the starting point, i as the ending point and all vertices appearing exactly once. Let the cost of this path be cost(i), the cost of corresponding Cycle would be cost(i) + dist(i, 1) where dist(i, 1) is the distance from i to 1. Finally, we return the minimum of all [cost(i) + dist(i, 1)] values. This looks simple so far. Now the question is how to get cost(i)?
To calculate cost(i) using Dynamic Programming, we need to have some recursive relation in terms of sub-problems. Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i.
We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset.

collected from geeksforgeeks.com

Topological Sort

We can modify DFS to find Topological Sorting of a graph. In DFS, we start from a vertex, we first print it and then recursively call DFS for its adjacent vertices. In topological sorting, we use a temporary stack. We don’t print the vertex immediately, we first recursively call topological sorting for all its adjacent vertices, then push it to a stack. Finally, print contents of stack. Note that a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

collected from geeksforgeeks.com

Articulation Point Finding Algorithm:

There are two ways to solve the problem.

One is using dfs on the graph excluding one vertex each time and check whether all the vertices are visited or not. If for exclusion of any vertex causes to unreachable to any vertex then that vertex is counted as articulation point. This is O(V*(V+E)) time complexity approach.

There is another approach called tarjan’s  algorithm which is a linear time approach O(V+E) time complexity algorithm.

Approach is checking the following two conditions:

1)if any vertex is root and has more than one child then its an AP.

2)if any vertex is not root then search for any of its child which has the property that rooted sub graph of that child (the sub graph where that child node is the root)  does not contain any node which has a back edge to any of the ancestors of the parent node(so if that child node is removed all of the nodes of that sub graph is got a way to be connected to the main graph).

To check this two array is kept to trace the discovery time and low of the nodes.

The implementation of the algorithms in its base form is given here.

Swapping:

Swapping without using third variable:

Swap two numbers using pointers:

Swap using call by reference:

Swap using bitwise XOR:

how to get integer from comma separated string in c++:

for learning more about this click here .