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

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);
 }