# Algorithms, Recursion and Data-Structures

## Princeton Algorithm Courses

One of the problems I had with setting up the jar file algs4.jar was that the `CLASSPATH` variable needs to include the directory where your Java programs .class file is. You can include ‘.’ in `CLASSPATH` to indicate that the current directory should be included.  Then I followed the instructions on the book site. and modified my .bash_profile as follows.

```# Add algs.jar to classpath
set CLASSPATH=.
export CLASSPATH=\$CLASSPATH:~/algs4/algs4.jar```

## Interesting Tricks

``` // int N to binary representation
String s = "";
for (int n = N; n > 0; n /= 2)
s = (n % 2) + s;

// log base 2
public static int lg(int N) {
if (N/2 == 1) return 1;
return 1 + lg(N/2);
}```

## Recursive Algorithms

A method can call itself.  There are three important rules of thumb in developing recursive programs:

1. The recursion has a base case – always includes a conditional statements as the first statement in the program that has a return.
2. Recursive calls must address subprograms that are smaller in some sense, so that recursive calls converge to the base case.
3. Recursive calls should not address subprograms that overlap.

### Greatest Common Divisor

Euclid’s Algorithm – compute the greatest common divisor of two nonnegative integers p and q as follows: If q is 0, the answer is p.  If not, divide p by q and take the remainder r.  The answer is the greatest common divisor of q and r.

```public static int gcd(int p, int q) {
if (q-==0) return p;
int r = p % q;
return (gcd(q, r);
}```

### Binary Search

```// recursive implementation of binary search
public static int rank(int key, int[] a0) {
return rank(key, a, 0, a.length -1);
}

public static int rank(int key, int[] a, int lo, int hi) {
// index of key in a[], if present is not smaller than lo,
// and not larger than hi
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) return rank (key, a, lo, mid -1);
else if (key > a[mid]) return rank (key, a, mid + 1, hi);
else return mid;
}```

### Simple Mathematical Functions

``` // log base 2
public static int lg(int N) {
if (N/2 == 1) return 1;
return 1 + lg(N/2);
}

// natural logarithm of n factorial
// ln(xy) = ln (x) + ln (y)
public static int lnFact(int n) {
if (n == 1) return 0;
return Math.log(n) + lnFact(n-1);
}

//  n factorial
public static long nFact(int n) {
if (n == 1) return 1;
return n * nFact(n-1);
}```