Showing posts with label Algorithm in Java. Show all posts
Showing posts with label Algorithm in Java. Show all posts

Sunday, December 17, 2017

Breadth First Search(BFS) In Java

BFS or Breadth First Search is a very well-known graph traversal algorithm. The following java program performs this algorithm using adjacency list representation of graphs. Graphs may contain a cycle. To avoid processing a node twice, we used a Boolean array, name visited.

Friday, December 15, 2017

Generate unique permutation in Java

We already saw how to generate all possible permutation in java. Today we will modify our algorithm to remove duplicate entries to keep only unique permutation.

For an example, if the given string is: 112, our program will generate:

112
121
211

Thursday, November 23, 2017

Sieve of Eratosthenes In Java

The sieve of Eratosthenes is a famous ancient algorithm to find all prime numbers up to a given limit. We are going to implement this algorithm in Java.


Steps we will follow:

a) Lets we have an array of size 25.
b) First start with 2, remove all numbers which are divisible by 2.
c) Find the next number, which is 3. Remove all numbers which are divisible by 3.
d) Next survivor is 5 and we repeat the same procedure.
e) For the given limit 25, we don't need to find anymore survivor after 5, as 5 X 5 = 25. In other words, we only process up to the square root of the limit.
 f) All survivor numbers in the array are Prime. We save those numbers in a separate array.

Generate all possible permutations in Java using recursion.

In the previous example, we drew a pyramid in java without any loop. We used recursion to achieve our goal and hopefully, you got a very clear idea how recursion works. In the following example, I will show you how to print all permutations of a given string. If the given string is "1234", then all possible permutations are:

1234
1243
1324
1342
1324
1342
1423
1432
 .
 .
 .
4321

 A total number of permutations are 24. ( 4! = 24 )

Tuesday, November 14, 2017

Pascal Triangle In Java

Pascal Triangle is one of the most interesting number pattern which is a triangular array of the binomial coefficients. The following example shows how to generate this triangle in Java.