## Archive for the 'Algorithms' Category

### How to use PriorityQueue

Apr 03, 2015 in Algorithms, Java

[java]

// TestPQ.java
import java.util.Comparator;
import java.util.PriorityQueue;

public class TestPQ {
public static void main(String[] args) {
Comparator comparator = new StringLengthComparator();
PriorityQueue queue =
new PriorityQueue(10, comparator);
while (queue.size() != 0) {
System.out.println(queue.remove());
}
}
}

[/java]

[java]

// StringLengthComparator.java
import java.util.Comparator;

public class StringLengthComparator implements Comparator {
@Override
public int compare(String x, String y) {
// Assume neither string is null. Real code should
// probably be more robust
// You could also just return x.length() – y.length(),
// which would be more efficient.
if (x.length() < y.length()) { return -1; } if (x.length() > y.length()) {
return 1;
}
return 0;
}
}

[/java]

### Fibonacci algorithm iterative

Jan 28, 2015 in Algorithms

[java]

/** Method to calculate the nth Fibonacci number iteratively.
* @param n
* @return nth Fibonacci number
* precondition: n >= 1
*/
public static long ifib(long n) {
if (n &lt 2) {
return 1;
} else {
long prev = 1, current = 1, next = 0;
for (long i = 3; i &lt= n; i++) {
next = prev + current;
prev = current;
current = next;
}
return next;
}
}

[/java]

### Fibonacci algorithm recursive

Jan 28, 2015 in Algorithms

[java]

public class FibonacciNumber {
public static int fibonacci(int n) {
if (n < 2) {
return n;
}
else {
return fibonacci(n – 1) + fibonacci(n – 2);
}
}
}

[/java]

[java]

public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n – 1) + fibonacci(n – 2);
}

[/java]

### Dakini Princess ..

Nov 29, 2014 in Algorithms

A dakini (Sanskrit: “sky dancer”) is a Tantric priestess of ancient India who “carried the souls of the dead to the sky”. This Buddhist figure is particularly upheld in Tibetan Buddhism. The dakini is a female being of generally volatile temperament, who acts as a muse for spiritual practice.
. . .

. . .

### Merge two sorted arrays in Java

Oct 09, 2013 in Algorithms, Java

. . .

From: based on http://stackoverflow.com/questions/5958169/how-to-merge-two-sorted-arrays-into-a-sorted-array

[java]

public class m2a {

public static int[] merge(int[] a, int[] b) {

int[] ma = new int[a.length + b.length];
int ax = 0, bx = 0, mx = 0;
while (ax < a.length && bx < b.length) {
if (a[ax] < b[bx]) {
ma[mx++] = a[ax++];
}
else {
ma[mx++] = b[bx++];
}
}

while (ax < a.length) {
ma[mx++] = a[ax++];
}

while (bx < b.length) {
ma[mx++] = b[bx++];
}

return ma;
}

public static void main(String[] args) {
m2a om2a = new m2a();
int a[] = {1, 3, 5, 7};
int b[] = {3, 4, 6, 9};
int ma[] = om2a.merge(a, b);
for ( int mx = 0 ; mx < ma.length ; mx++ ) {
System.out.print(ma[mx] + ” “);
}
System.out.println();
}

}

[/java]

[java]

public class m2a {

public static int[] merge(int[] aa, int[] ba) {

int[] ma = new int[aa.length + ba.length];
int ax = 0, bx = 0, mx = 0;

while (ax < aa.length && bx < ba.length) {
if (aa[ax] < ba[bx])
ma[mx++] = aa[ax++];
else
ma[mx++] = ba[bx++];
}

while (ax < aa.length)
ma[mx++] = aa[ax++];

while (bx < ba.length)
ma[mx++] = ba[bx++];

return ma;
}

public static void main(String[] args) {
m2a om2a = new m2a();
int a[] = {1, 3, 5, 7};
int b[] = {3, 4, 6, 9};
int ma[];

ma = om2a.merge(a, b);
for ( int mx = 0 ; mx < ma.length ; mx++ ) {
System.out.print(ma[mx] + ” “);
}
System.out.println();
}

}

[/java]

### Entropy ..

Jul 22, 2011 in Algorithms, Linux

Entropy is the measure of the random numbers available from /dev/urandom, and if you run out, you can’t make SSL connections.

Apr 02, 2010 in Algorithms

The Squonk is of a very retiring disposition and due to its ugliness, weeps constantly. It is easy prey for hunters who simply follow a tear-stained trail. When cornered it will dissolve itself into tears.
True or False?

http://www.sing365.com/music/lyric.nsf/Squonk-lyrics-Genesis/6EF5A0D7E2CAE720482569600014CC3F

### Reversing a singly-linked list in Java .. iterative and recursive methods ..

Dec 27, 2009 in Algorithms, Java

[java]

ListNode prev = null;
ListNode next = null;

while (curr != null) {
next = curr.next;
curr.next = prev; // reverse link to previous
prev = curr;
curr = next;
}

return prev;
}

[/java]

Recursive method:

[java]

return rlist;
}
[/java]

. . .

### Breadth first search traversal algorithm..

Dec 02, 2009 in Algorithms, Java

```
BFS(G, s)
for each vertex u in V - { s } do
u.color = white
u.dist = infinity  // ''dist'' is distance from s
u.pred = nil       // ''pred'' is predecessor
s.color = gray
s.dist = 0
s.pred = nil
Q = { s }            // ''Q'' is a FIFO queue
while Q not empty do
u = Q.head         // get element on top of queue
for each v in neighbors(u) do  // visit every node u has an edge to
if v.color == white then
v.color = gray
v.dist = u.dist + 1
v.pred = u
Q.enqueue(v)   // add v to back of queue
Q.dequeue          // pop u off top of queue
u.color = black

```

And a bit more Java-ish..

[java]

BFS(root) {
cn = root;

s.push(cn.getValue()); // Save node value on stack
cn.setValue(-1); // mark node visited
q.enqueue(cn);

while(! q.isEmpty() ) {
cn = q.dequeue();
foreach v in cn.getChildren() {
if (v.getValue() != -1) {
// This node not visited yet
s.push(v.getValue()); // save node value on stack
v.setValue(-1); // mark node visited
q.enqueue(v);
}
}
}

}

[/java]

And even simpler..

[java]

BFS(root) {
cn = root;

cn.visit(); // mark node visited
q.enqueue(cn);

while(! q.isEmpty() ) {
cn = q.dequeue();

foreach v in cn.getChildren() {
if ( ! v.visited() ) {
// This node not visited yet
v.visit(); // mark node visited
q.enqueue(v);
}
}
}

}

[/java]

### Java example of basic cache (LRU) using LinkedHashMap ..

Aug 24, 2009 in Algorithms, Java, JavaUsage

[java]
import java.util.Map;

public class t1 {

final int MAX_ENTRIES = 2;

Map cache = new LinkedHashMap(MAX_ENTRIES+1, .75F, true) {
// This method is called just after a new entry has been added
public boolean removeEldestEntry(Map.Entry eldest) {
System.out.println(“eldest: ” + eldest.getKey() + “=” + eldest.getValue());
return size() > MAX_ENTRIES;
}
};

public void cacheAdd(String pkey, String pstr) {
cache.put(pkey, pstr);
}

public static void main(String[] args) {
t1 ot1 = new t1();
}

/* —
// Get object
Object o = cache.get(key);
if (o == null && !cache.containsKey(key)) {
// Object not in cache. If null is not a possible value in the cache,
// the call to cache.contains(key) is not needed
}

// If the cache is to be used by multiple threads,
// the cache must be wrapped with code to synchronize the methods
cache = (Map)Collections.synchronizedMap(cache);
— */

}

[/java]