Prim’s Running Time With Heaps

Input: Given a graph with N nodes and M weighted edges, we want to obtain the Minimum Spanning Tree (MST) of the graph.

Note: MST is a tree that is formed in a graph which makes all the graph nodes
connected with the minimum total edges weights, also cycles isn’t allowed in the tree.

Output: Using Prim’s algorithm , we obtain a tree (collection of nodes and edges) that
satisfy the above conditions (The green edges in the figure forms the MST).

kruskalll

Algorithm Steps (Taken from Wikipedia):

  1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
  2. Grow the tree by one edge of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
  3. Repeat step 2 (until all vertices are in the tree).

To be able to put all the graph nodes to the tree, we need to iterate all over the graph nodes. So, the operation costs O(N).

In each iteration, we obtain the minimum edge weight to grow the tree. Regularly, getting the minimum value costs O(X) where X is the size of the data. Here, we have M edges. To find the minimum edge per iteration, we need to form O(M) iteration at most where M is the number of graph edges.

Combining the both, we obtain the final running time which is O(NM).

Time Improvement Proof Using Heaps:

Heap is a data structure that is popular among programming languages. Nearly all programming languages implement it in their Collections or Abstract Data Types.

H

The heap is a binary tree (each node has only 2 children), if it is a max heap then the tree sorts the values so that the direct root and parent nodes are always higher than the children, if it is a min heap then the tree sorts the values so that the direct root and parent nodes are always lower than the children.

Min-heap

The tree supports many operations with low running time compared to the naive implementations.

BH

The Improved Algorithm Steps will be:

  1. Create a Min Heap with size of N (costs O(N))
  2. Initialize the heap with a node with cost 0 as it is the root node
  3. While the heap isn’t empty, do the following
    – Extract the minimum node value
    u from the heap (costs O(1))
    – Delete the extracted node as it is visited
    (costs O(log(N)))
    – Get the adjacent nodes
    v from the extracted node (costs O(M) at most where M >= (N – 1) in the worst case)
    – For every adjacent node v, check if it is in the heap and not included in the MST
    – If it is in the heap but it can be relaxed (update the u-v weight with lower weight) and insert the new value of v (costs O(log(N)))
    Add u to the MST

 So, the final running time will be O(M log(N)), where M is the number of edges and N is the number of nodes.

References

https://en.wikipedia.org/wiki/Binary_heap

https://en.wikipedia.org/wiki/Heap_(data_structure)

https://en.wikipedia.org/wiki/Prim%27s_algorithm

 

 

 

The Unsolvability Halting Problem

Definition

Halting problem is a famous problem in computer science. The problem is simply we want to prove and know whether a computer program will be halted or terminated or it will continue running forever.

Alan Turing proved that there is known solution for the halting problem. It is impossible to determine whether a program with an input will be terminated or it will run forever.

The proof used contradiction method to prove its unsolvability.

The Proof

  • Assume that we have a program P(X) that takes X as an input
  • The output of the program will be 0 or 1 where 1 indicates the program will halt and 0 indicates the program will continue forever
  • Assume we have another program Q that takes program P as its input, Q(P(X)) that output 0 or 1 where 1 indicates P(X) will run forever and 0 indicates it will halt
  • Assume we pass the program Q to itself (Recursion) as its parameter Q(Q)
  • Now, we have 2 cases
  • Case 1: If Q(Q) halts, then P(X) returns 1, which means Q(P(X)) will return 1 which indicates P(X) runs forever. Contradiction
  • Case 2: If Q(Q) runs forever, then P(X) returns 0, which means Q(P(X)) will return 0 which indicates P(X) halts. Contradiction

References
https://en.wikipedia.org/wiki/Halting_problem
 http://www.comp.nus.edu.sg/~cs5234/FAQ/halt.html