Monthly Archives: March 2015

Introduction into Java Virtual Machine

When we are talking about Java Virtual Machine we can think of three different things: specification, implementation or instance of the JVM. Lets have a look at these things in more details. The specification describes abstract concept without any implementation details to keep interoperability. Basing on the specification we can create implementation for almost all platforms. Thus, the same Java byte code can be executed on Windows or Linux. The difference between implementations is not only based on the platform, some JVM implementations can differ by performance, vendor or by additional functionality. To run Java application we need an instance of JVM implementation. The new instance is created every time the application started and instance is destroyed when application completed. So – if we run three applications then three instances will be created.

Basically, by the specification, the Java virtual machine is described in terms of  subsystems, runtime area etc:
jvm_internlas Continue reading Introduction into Java Virtual Machine

Difference between JDK, JVM, JRE, OpenJDK and JIT

If you are a Java developer and you are going to achieve success in Java, it is very important to have clear understanding and know difference between main Java components . This knowledge will give you overall picture of what Java is, how it works and definitely will help you in developing applications.

Firstly, I would like to show you all main components in one diagram. On the diagram below you will find information on how the components related to each other and which components are parts of other components.

java_hier_1

For instance, you can see that Java Development Kit JDK includes all components . The Java Virtual Machine JVM includes Just-In-Time compiler JIT and core libraries. In fact, you can install only JRE without development tools, but in this case you will not be able to compile Java code to byte code. Continue reading Difference between JDK, JVM, JRE, OpenJDK and JIT

Prim’s Algorithm

Prim’s algorithm searches minimum spanning tree in a weighted undirected graph. In other words, it finds a sub-set of edges that forms a tree, where all vertices of a given graph are included and total weight of all edges is minimized.

Let’s consider the following example. You are an engineer and you’re going to build electrical grid to provide electricity to all houses bellow. The weight represents distance between two houses.

pa_main_1

Of course, the houses can be connected in a random way and the problem will be solved. Continue reading Prim’s Algorithm

Kruskal’s Algorithm

Kruskal’s algorithm is used to find minimum spanning tree in a weighted undirected graph. A spanning tree of a undirected graph G is a sub-graph that includes all vertices of G and satisfies conditions of a tree. On the diagram below you can find two graphs and only left graph can be considered as spanning tree.

span_tree_1

Because, the right graph has a cycle and this fact violates condition which states that a tree cannot have a cycle.  Continue reading Kruskal’s Algorithm

Johnson’s Algorithm

Johnson’s algorithm solves the all-pairs shortest path problem on a graph which may contain negative weight but has no negative weight cycle. In other words, it searches for the shortest distance between every pair of vertices in a given directed graph. The algorithm uses Bellman-Ford algorithm to prepare graph for re-weighting.

The re-weighting technique changes all negative weights to nonnegative. Thus,  once we get rid of all negative weights we can use Dijkstra’s algorithm that is faster than Bellman-Ford algorithm to obtain shortest path between all pair of vertices.

Before, we run Bellman-Ford algorithm we need to add a new vertex and connect it to all others with zero weight.

john_1

As result we have a vertex from which every node can be accessed and now it is time run Bellman-Ford algorithm from this new node. Continue reading Johnson’s Algorithm

Bellman-Ford Algorithm

The Bellman-Ford algorithm solves single-source shortest path problem in a directed graph with negative and positive  weights. Its time complexity in worst case is equal to Ο(V*E) while Dijkstra’s algorithm has Ο((V+E)log V) time complexity. Thus, if you don’t have negative weights it’s preferable to use Dijkstra’s algorithm.

The only problem that can occur during execution of Bellman-Ford algorithm is  a negative weight cycle. It is a cycle with weights that sum to a negative number. In that case the algorithm relaxes its nodes indefinitely. Fortunately, Bellman-Ford algorithm can detect negative weight cycle.

nwcg

The algorithm was discovered independently by Richard Bellman and Lester Ford, Jr. Continue reading Bellman-Ford Algorithm