## 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

- https://github.com/kevin-wayne/algs4/tree/master/src/main/java/edu/princeton/cs/algs4
- Princeton Algs 4 course with Sedgewick – http://algs4.cs.princeton.edu

## 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:

- The recursion has a
**base case**– always includes a conditional statements as the first statement in the program that has a return. - Recursive calls must address subprograms that are
**smaller**in some sense, so that recursive calls converge to the base case. - 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); }