Data Structures With Java By John R. Hubbard

Last week i started reading Data Structures With Java By John R. Hubbard.

I can say that this is wonderful book and i enjoyed throughly.

I wanted to share few key points in this book.

1) The binary search runs in O(lgn) time. This means that, on average, the running time is proportional to the logarithm of the number of elements in the array. So if everything else is the same, if it takes an average of T milliseconds to run on an array of n elements, then will take an average of 2T milliseconds to run on an array of n2 elements. For example, if it takes 3 ms to
search 10,000 elements, then it should take about 6 ms to search 100,000,000 elements! The following argument is a proof of that fact.

Each iteration of the loop searches a subarray that is less than half as long as the subarray on the previous iteration. Thus the total number of iterations is no more than the number of times that the length n can be divided by 2. That number is lgn. And the total running time is roughly proportional to the number of iterations that the loop makes.

2) When inserting into an sorted array a better solution is to
use an auxiliary index array to keep track of where the elements actually are. This solution requires more space (a second array) and makes the code a bit more complicated. But it eliminates the need to move the elements. It allows the elements to be stored at an arbitrary position in the array, using the auxiliary index array to locate them for ordered access.

3) Below is little clever way of removing duplicates in the array.I think the key point to understand is it is using only one array to achieve this.

private static int[] withoutDuplicates(int[] a) {
  int n = a.length;
  if (n < 2) {
   return a;
  }
  for (int i = 0; i < n-1; i++) {
   for (int j = i+1; j < n; j++) {
    if (a[j] == a[i]) {
     --n;
     System.arraycopy(a, j+1, a, j, n-j);
     print(a);
     --j;
    }
   }
  }
  int[] aa = new int[n];
  System.arraycopy(a, 0, aa, 0, n);
  return aa;
 }

4) Sieve of Eratosthenes
means In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer.

Below program achieves the aligorithm mentioned.

public class TestSieve {
  private static final int SIZE=30;
  private static boolean[] isPrime = new boolean[SIZE];

  public static void main(String[] args) {
    initializeSieve();
    printSieve();
  }

private static void initializeSieve() {
    for (int i = 2; i < SIZE; i++) {
      isPrime[i] = true;
    }
    for (int n = 2; 2*n < SIZE; n++) {
      if (isPrime[n]) {
        for (int m = n; m*n <SIZE; m++) {
          isPrime[m*n] = false;
        }
      }
    }
  }

  public static void printSieve() {
    int n=0;
    for (int i = 0; i < SIZE; i++) {
      if (isPrime[i]) {
        System.out.printf("%5d%s", i, ++n%16==0?"\n":"");
      }
    }
    System.out.printf("%n%d primes less than %d%n", n, SIZE);
  }
}

5) Charles Babbage (1792–1871) obtained the first government grant in history when in 1823
he persuaded the British government to provide £1000 to build his difference engine. In his grant proposal, Babbage gave the formula x2 + x + 41 as an example of a function that his computer would tabulate. This particular function was of interest to mathematicians because it produces an unusual number of prime numbers.Primes that have this form n = x2 + x + 41 for some integer x could be called Babbage primes.

Below program illustrate one implementation of Babbage primes.

private static void testBabbagePrimeNumbers(int n) {
   System.out.print(n + "     ");
   int babbagePrime=(int)Math.pow(n,2) + n + 41;
   System.out.println(babbagePrime + " is prime");
  
 }
 
 public static void main(String[] args) {
  for (int i = 0; i < 8; i = i + 1)
   BabbagePrimeNumbers.testBabbagePrimeNumbers(i);
 }

6) In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form
Fn=pow(2,pow(2,n)) + 1

Below program illustrate one implementation of Fermat numbers.

private static void testFermatNumbers(int n) {
  System.out.print("F" + n + "= ");
  
   double pow=Math.pow(2,Math.pow(2,n))+1;
   System.out.println(pow);
  
 }
 
 public static void main(String[] args) {
  for (int i = 0; i < 8; i = i + 1)
   FermatNumbers.testFermatNumbers(i);
 }

7) In mathematics, a Mersenne number is a number that is one less than a power of two,

Below program illustrate one implementation of Fermat numbers.

public class MersennePrimeDemo {
 
 private static final int SIZE = 1000;
 
 private static int size = SIZE;
 
 private static BitSet isPrime = new BitSet(size);
 
 private static int last = 1;
 
 static {
  for (int i = 2; i < SIZE; i++) {
   isPrime.set(i);
  }
  for (int n = 2; 2 * n < SIZE; n++) {
   if (isPrime.get(n)) {
    for (int m = n; m * n < SIZE; m++) {
     isPrime.clear(m * n);
    }
   }
  }
 }
 
 public static void setLast() {
  last = 1;
 }
 
 public static boolean isPrime(int n) {
  return isPrime.get(n);
 }
 
 public static int next() {
  while (++last < size) {
   if (isPrime.get(last)) {
    return last;
   }
  }
  return -1;
 }
 
 private static void mersennePrimes(int n) {
  
   int result=(int)Math.pow(2,n) -1;
   System.out.println(2 + "^" + n + "-" + 1 + "=" + result + " is prime");
 }

 public static void main(String[] args) {
  
  for(int i=0;i<10;i++) {
  int prime=next();
  MersennePrimeDemo.mersennePrimes(prime);
  }
 }
}

8) Christian Goldbach (1690–1764) conjectured in 1742 that every even number greater than 2 is the sum of two primes.

Below program illustrate one implementation of Goldbach primes.

private static void testGoldbach(int n) {
    StringBuffer stringBuffer=new StringBuffer();
    stringBuffer.append(n + "= ");
    for(int i=2;i<=n;i++) {
     for(int j=i;j<=n;j++) {
       if(isPrime(j) && isPrime(i)) {  // write prime number logic 
        int sum=i+j;
        if(sum==n) {
         stringBuffer.append(i + "+" + j + ",");
        }
       }
     }
    }
    if(stringBuffer.toString().charAt(stringBuffer.length()-1)==',')
    stringBuffer.delete(stringBuffer.length()-1,stringBuffer.length());
    System.out.println(stringBuffer.toString());
   }
   
   public static void main(String[] args) {
    for(int i=2;i<20;i=i+2)
    TestGoldbach.testGoldbach(i);
  }

9) Two consecutive odd integers that are both prime are called Twin primes. The twin primes conjecture is that there are infinitely many twin primes

Below program illustrate one implementation of Twin primes.

private static void twinPrimeConjecture(int n) {
  
  for (int i = 3; i < 3*n; i = i + 2) {
   int j=i+2;
   if(isPrime(i) && isPrime(j)) {
    System.out.println(i + "    " + j);
   }
  }
 }
 
 public static void main(String[] args) {
  TwinPrimeConjecture.twinPrimeConjecture(10);
 }

10) Below program is a simple implementation of Circular LinkedList.

Prints: Head1 Head1 Tail1

public class LinkedQueue<E> implements Queue<E> {
  private Node<E> head = new Node<E>();  // dummy node
  private int size;

  public static void main(String[] args) {
 LinkedQueue linkedQueue=new LinkedQueue();
 linkedQueue.add("Head1");
 linkedQueue.add("Tail1");
 
 System.out.println(linkedQueue.element());
 System.out.println(linkedQueue.remove());
 System.out.println(linkedQueue.element());
  }
  
  public void add(E element) {
    head.prev = head.prev.next = new Node<E>(element, head.prev, head);
    ++size;
  }

  public E element() {
    if (size == 0) {
      throw new java.util.EmptyStackException();
    }
    return head.next.element;  // front of queue  // next  <-->  prev
  }

  public boolean isEmpty() {
    return (size == 0);
  }

  public E remove() {
    if (size == 0) {
      throw new java.util.EmptyStackException();
    }
    E element = head.next.element;  // next  <-->  prev
    head.next = head.next.next;     // next  <-->  prev
    head.next.prev = head;          // next  <-->  prev
    --size;
    return element;
  }

  public int size() {
    return size;
  }

  private static class Node<E> {
    E element;
    Node<E> prev;
    Node<E> next;

    Node() {
      this.prev = this.next = this;
    }

    Node(E element, Node<E> prev, Node<E> next) {
      this.element = element;
      this.prev = prev;
      this.next = next;
    }
  }
}

11) A binary tree is either the empty set or a triple T = (x, L, R), where x is a node and L
and R are disjoint binary trees, neither of which contains x.

12) A forest is a disjoint of ordered trees.

13) In a B-tree, searching, inserting, and deleting all run in O(lgn) time.

14) Well i could not understand AVL trees code from this book but only after understanding this code i could successfully understand.

Hope you also will enjoy reading this book.