String Algorithms

Sorting
i. Key indexed counting
ii. LSD (Least-significant-digit-first) string sorting
- Sorts equal length strings.
- uses key index counting method
iii. MSD (Most-significant-digit-first) string sorting
- Recurvise sort
- Sorst any length strings
iv. 3-way radix sort

String Search
1. R-way Tries

Sub String Searching
i. Knuth–Morris–Pratt
ii. Boyer–Moore
iii. Rabin–Karp

Arrays

Prob1: Given an array A[] and a number x, check for pair in A[] with sum as x

Prob2: Majority Element

Prob3: Find the Number Occurring Odd Number of Times

Prob4: Largest Sum Contiguous Sub array

Prob5: Find the Missing Number

Prob6: Search an element in a sorted and pivoted array

Prob7: Merge an array of size n into another array of size m+n

Graph Shortest Path

Dijkstra's algorithm:
- solves the single-source shortest-paths problem in edge-weighted digraphs with non-negative weights
 using extra space proportional to V and time proportional to E log V (in the worst case).

DAG: (acyclic edge-weighted digraph)
1. Single-source shortest paths: O(E + V)
- solves the single-source problem in linear time.
- handles negative edge weights.

2. Single-source longest paths: O(E + V)
3. Critical path method:

Shortest paths in general edge-weighted digraphs:
- the concept of a shortest path is meaningless if there is a negative cycle.
Bellman-Ford:
- solves the single-source shortest-paths problem from a given source s
- finds a negative cycle reachable from s
- time proportional to E V and extra space proportional to V

Different Type of Tree representation

Tree is an non-Linear data structure. Its way of representing hierarchical nature of data.

Different Tree Type.

- Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children.

- Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible

- Perfect Binary Tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.

- Balanced Binary Tree: A binary tree is balanced if height of the tree is O(Log n) where n     is number of node
         - AVL Tree
         - Red-Black Tree

- Binary Search Tree:
- Expression Tree:
- Threaded Binary Tree: The idea of threaded binary trees is to make inorder traversal faster and do it without stack and without recursion.
         - Single Threaded: Where a NULL right pointers is made to point to the inorder successor (if successor exists)

         - Double Threaded: Where both left and right NULL pointers are made to point to inorder predecessor and inorder successor respectively. The predecessor threads are useful for reverse inorder traversal and postorder traversal.

            The threads are also useful for fast accessing ancestors of a node.

Binary Tree Traversal

Binary Tree Traversal:

Breadth-First 
    1. Level Order traversal

Depth-First 
    1. Pre-Order. 
2. In-Order. <left> <root> <right>
3. Post-Order. <right> <left> <root>



Pre-Order: node visiting order = <root> <left> <right>
Steps:  
   1. Visit root.
2. Visit Left Sub-Tree.
3. Visit Right Sub-Tree.

Preorder traversal is used to create a copy of the tree. Preorder traversal is also used to get prefix expression on of an expression tree.


In-Order: (nodes are processed in ascending order)
Node visiting order =  <left> <root> <right>
Steps:  
   1. Visit Left Sub-Tree.
2. Visit root.
3. Visit Right Sub-Tree.

In case of binary search trees (BST), Inorder traversal gives nodes in ascending order. To get nodes of BST in descending order, a variation of Inorder traversal where Inorder itraversal s reversed, can be used.

Post-Order: 
Node visiting order =  <left> <right> <root>
Steps:  
   1. Visit Left Sub-Tree.
2. Visit Right Sub-Tree.
3. Visit root.

Postorder traversal is used to delete the tree. Postorder traversal is also useful to get the postfix expression of an expression tree.

private void PreOrder(Node node){
 if(node == null) return;
 
 System.out.println(""+node.key+", "+node.value);
 PreOrder(node.left);
 PreOrder(node.right);
}

private void inOrder(Node node){
 if(node == null) return;
 
 inOrder(node.left);
 System.out.println(""+node.key+", "+node.value);
 inOrder(node.right);
}

private void postOrder(Node node){
 if(node == null) return;
 
 postOrder(node.left);
 postOrder(node.right);
 System.out.println(""+node.key+", "+node.value);
} 

Level-Order: 

public void leveOrder() {
 Queue<Node> queue = new LinkedList<Node>();
 levelOrder(queue, root);
}

private void levelOrder(Queue<Node> queue, Node node) {
 if (node == null)
  return;

 System.out.println("" + node.key + ", " + node.value);
 if (node.left != null)
  queue.add(node.left);
 if (node.right != null)
  queue.add(node.right);
 levelOrder(queue, queue.poll());
}

Binary Tree

Binary Tree: Each node in a tree can have at most 2 children. 

Property:
Leaf Node: Node with zero child.

Strict/Proper Binary Tree: Each node can have 2 or 0 children.
Complete Binary Tree: 
Balanced Binary Tree: Difference between height of left and right subtree for 
                        every node is not more than K.
Depth of Node: Length of path from root to that node.
Height of a Tree: Length of longest path between root and any of leaf nodes.

Observations:
1. Max number of nodes at level i = 2^i.
2. Max number of nodes in a Strict Binary tree = 2^(no of levels) - 1.
3. Height of a Strict Binary Tree which has N nodes = log2(n-1) -1.

Implementation:
1. Can be implemented using dynamically created nodes.
2. Arrays.


other
Binary Search Tree: Efficient structure for storing ordered data.

Symbol Table

ST Implementation

1. Un-Ordered List
    Search Complexity: N (average N/2)
    Insert Complexity: N

2. Ordered List
    Search: N Log N
    Insert: N (average N/2)

3. BST
    Search: N (average 1.4 log N)
    insert: N (average 1.4 log N)

/*
 *  Symbol table implementation using Linked list
 */

import java.util.Iterator;

public class LinkedListST<Key, Value> implements Iterable<Key> {

 private Node root;

 public LinkedListST() {
 }

 @Override
 public Iterator<Key> iterator() {
  return new STIterator();
 }

 private class STIterator implements Iterator<Key> {

  Node current = root;

  @Override
  public boolean hasNext() {
   return current != null;
  }

  @Override
  public Key next() {
   Key key = current.key;
   current = current.next;

   return key;
  }

  @Override
  public void remove() throws UnsupportedOperationException {
   throw new UnsupportedOperationException();
  }
 }

 public class Node {
  private Key key;
  private Value value;
  private Node next;
 }

 public void put(Key key, Value value) {
  Node current = root;

  while (current != null) {
   if (current.key.equals(key)) {
    current.value = value;
    return;
   }
   current = current.next;
  }
  Node temp = new Node();
  temp.key = key;
  temp.value = value;
  temp.next = root;

  root = temp;
 }

 public Value get(Key key) {
  Node current = root;

  while (current != null) {
   if (current.key.equals(key))
    return current.value;

   current = current.next;
  }
  return null;
 }

 public boolean contains(Key key) {
  return get(key) != null;
 }
}


import java.util.Iterator;

/**
 * Liked List Symbol table test
 */

public class LinkedListSTTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  System.out.println("BinarySearchBTTest::main");

  LinkedListST<String, Integer> bsst = new LinkedListST<String, Integer>();

  bsst.put("Ramesh", 90);
  bsst.put("Suguna", 80);
  bsst.put("Haasini", 99);
  bsst.put("Saravanan", 80);
  bsst.put("Mahisa", 75);
  bsst.put("Reethu", 60);

  bsst.put("Ramesh", 50);

  Iterator<String> iterator = bsst.iterator();

  while (iterator.hasNext()) {

   String name = iterator.next();
   Integer marks = bsst.get(name);

   System.out.println("name = " + name + ", marks = " + marks);
  }

 }

}

/****
 * 
 *  Sorted symbol table implementation using array & BST
 * 
 */

import java.util.Iterator;
import java.util.NoSuchElementException;

public class BinarySearchST<Key extends Comparable<Key>, Value> implements
  Iterable<Key> {

 private static final int ST_SIZE = 10;
 
 private Key[] keys;
 private Value[] values;
 
 private int N;
 
 public BinarySearchST(){
  this(ST_SIZE);
 }
 
 private BinarySearchST(final int capacity){
  keys = (Key[]) new Object[capacity];
  values = (Value[]) new Comparable[capacity];
 }
 
 private void resize(int capacity){
  Key[] tempKeys = (Key[]) new Object[capacity];
  Value[] tempValues = (Value[]) new Comparable[capacity];
  
  for (int i = 0; i < keys.length; i++) {
   tempKeys[i] = keys[i];
   tempValues[i] = values[i];
  }
  
  keys = tempKeys;
  values = tempValues;
 }
 
 public void put(Key key, Value value){
  
  if(N == keys.length) resize(keys.length * 2);
  
  int index = search(key);
  if(index >= 0){
   values[index] = value;
   return;
  }
  
  int i = N;
  
  while(i>0 && key.compareTo(keys[i-1]) < 0){
   keys[i] = keys[i-1];
   values[i] = values[i-1];
   i--;
  }
  
  keys[i] = key;
  values[i] = value;
  N++;
  
 }
 
 public Value get(Key key){
  int index = search(key);
  if(index>=0){
   return values[index];
  }
  
  return null;
 }
 
 private int search(Key key){
  int lo = 0, hi = N-1;
  
  int mid = lo+(hi-lo)/2;
  
  while(lo<=hi){
   int val = key.compareTo(keys[mid]);
   
   if(val < 0){
    hi = mid-1;
   }else if(val > 0){
    lo = mid+1;
   }else{
    return mid;
   }
  }
  return -1;
 }
 
 @Override
 public Iterator<Key> iterator() {
  return new BSSTIterator();
 }
 
 private class BSSTIterator implements Iterator<Key>{

  private int index = 0;
  
  @Override
  public boolean hasNext() {
   return index < N;
  }

  @Override
  public Key next() {
   if(!hasNext()) throw new NoSuchElementException();
   return keys[index++];
  }

  @Override
  public void remove() throws UnsupportedOperationException{
   throw new UnsupportedOperationException();
  }
  
 }
}



/*
 *  Binary Search Symbol Table Test
 * 
 */


import java.util.Iterator;


public class BinarySearchSTTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  System.out.println("BinarySearchBTTest::main");

  LinkedListST<String, Integer> bsst = new LinkedListST<String, Integer>();

  bsst.put("Ramesh", 90);
  bsst.put("Suguna", 80);
  bsst.put("Haasini", 99);
  bsst.put("Saravanan", 80);
  bsst.put("Mahisa", 75);
  bsst.put("Reethu", 60);

  bsst.put("Ramesh", 50);

  Iterator<String> iterator = bsst.iterator();

  while (iterator.hasNext()) {

   String name = iterator.next();
   Integer marks = bsst.get(name);

   System.out.println("name = " + name + ", marks = " + marks);
  }
 }

}

/*
 * Symbol table implementation using BST
 * 
 */

import java.util.Iterator;

public class BSTSymbolTable<Key extends Comparable<Key>, Value> implements
  Iterable<Key> {

 private Node root;

 public class Node {
  private Key key;
  private Value value;
  private Node left;
  private Node right;

  public Node(Key key, Value value) {
   this.key = key;
   this.value = value;
  }
 }

 public Value get(Key key) {

  Node current = root;

  while (current != null) {
   int val = key.compareTo(current.key);
   if (val < 0) {
    current = current.left;
   } else if (val > 0) {
    current = current.right;
   } else
    return current.value;
  }

  return null;
 }

 public void put(Key key, Value value) {
  root = put(root, key, value);
 }

 private Node put(Node node, Key key, Value value) {
  if (node == null)
   return new Node(key, value);

  int index = key.compareTo(node.key);
  if (index < 0) {
   node.left = put(node.left, key, value);
  } else if (index > 0) {
   node.right = put(node.right, key, value);
  } else {
   node.value = value;
  }

  return node;
 }

 public Iterator<Key> iterator() {
  return null;
 }
}


/*
 *  BSTSymbolTableTest
 * 
 */

public class BSTSymbolTableTest {

 /**
  * @param args
  */
 public static void main(String[] args) {
  System.out.println("BSTSymbolTableTest::main");

  BSTSymbolTable<String, Integer> table = new BSTSymbolTable<String, Integer>();

  table.put("Ramesh", 90);

  table.put("Anandhan", 80);

  System.out.println(table.get("Ramesh"));

 }

}

MergeSort

Steps:
1. Divide array in to 2 halves.
2. Recursively sort each half.
3. Merge 2 halves.

Complexity: N log N, Mergesort is optimal with respect to # compare operation performed.
Space: Not optimal with respect to space usage.

public class MergeSort {

 private static void merge(Comparable a[], Comparable aux[], int lo,
   int mid, int high) {
  assert isSorted(a, lo, mid);
  assert isSorted(a, mid + 1, high);

  for (int i = lo; i <= high; i++) {
   aux[i] = a[i];
  }

  int index1 = lo;
  int index2 = mid + 1;

  for (int k = lo; k <= high; k++) {
   if (index1 > mid) {// first array integration finished
    a[k] = aux[index2++]; // just copy the second array elements to
          // input array
   } else if (index2 > high) {// second array integration finished
    a[k] = aux[index1++];// just copy the first array elements to
          // input array
   } else if (isLess(aux[index1], aux[index2])) {
    a[k] = aux[index1++];
   } else {
    a[k] = aux[index2++];
   }
  }

  assert isSorted(a, lo, high);
 }

 private static void sort(Comparable[] a, Comparable[] aux, int lo, int high) {

  if (high <= lo)
   return; // return if we reach the minimum array from input for
     // merging

  int mid = lo + (high - lo) / 2;
  sort(a, aux, lo, mid);
  sort(a, aux, mid + 1, high);

  merge(a, aux, lo, mid, high);
 }

 public static void sort(Comparable a[]) {
  Comparable aux[] = new Comparable[a.length];

  sort(a, aux, 0, a.length - 1);
 }

 private static boolean isSorted(Comparable a[], int start, int end) {

  for (int i = start + 1; i < end; i++) {
   if (isLess(a[i], a[i - 1])) {
    return false;
   }
  }

  return true;
 }

 private static boolean isLess(Comparable a, Comparable b) {
  return a.compareTo(b) < 0;
 }
}


/**
 * Merge test code
 */

import java.util.Random;

public class MergeSortTest {
 public static void main(String[] args) {
  System.out.println("MergeSortTest::main()");

  int N = 100;
  Integer[] ipArray = new Integer[N];

  Random random = new Random();

  for (int i = 0; i < ipArray.length; i++) {
   ipArray[i] = random.nextInt(N);
   // System.out.println("MergeSortTest::main() i = "+i+", val = "+ipArray[i]);
  }

  MergeSort.sort(ipArray);

  for (int i = 0; i < ipArray.length; i++) {
   System.out.println("MergeSortTest::main() Sorted ouput i = " + i
     + ", val = " + ipArray[i]);
  }
 }
}

Stack

Stack using linked list
       1. Memory: ~40N
       2. Every operation takes constant time in the worst case.
       3. Uses extra spaces and time to deal with links.
       4. Slow performance.


Stack using arrary
       1. Memory: ~8N(when full) - ~32N(when one quarter full).
       2. Every operation takes constant amortized time.
       3. Less wasted space. Faster implementation.

import java.util.Iterator;

public class Stack<Item> implements Iterable<Item> {

 private Node first;

 public class Node {
  Item item;
  Node next;
 }

 public Stack() {

 }

 public void push(Item item) {
  if (isEmpty()) {
   first = new Node();
   first.item = item;
  } else {
   Node temp = new Node();
   temp.item = item;
   temp.next = first;

   first = temp;
  }

 }

 public Item pop() {
  Node top = first;
  Item item = top.item;

  first = first.next;

  return item;
 }

 private boolean isEmpty() {
  return first == null;
 }

 public int size() {
  int size = 0;

  Node temp = first;
  while (temp != null) {
   temp = temp.next;
   size++;
  }

  return size;
 }

 @Override
 public Iterator<Item> iterator() {
  return new StackIterator();
 }
 
 private class StackIterator implements Iterator<Item>{
  
  private Node current = first;

  @Override
  public boolean hasNext() {
   return current != null;
  }

  @Override
  public Item next() {
   Item item = current.item;
   current = current.next;
   return item;
  }

  @Override
  public void remove() throws UnsupportedOperationException{
   throw new UnsupportedOperationException();
  }
 }
}

//Stack implementation using array
public class StackArray {
 private String [] data;
 private int size = 0;
   
 public StackArray(){
  data = new String[1];
 }
 
 public void push(String item){
  if(size == data.length) reSize(data.length * 2);
  
  data[size++] = item;
 }
 
 public String pop(){
  
  String item = data[--size];
  data[size] = null;
  if(size < data.length/4) reSize(data.length/2);
  
  return item;
 }
 
 private boolean isEmpty(){
  return size == 0;
 }
 
 private int size(){
  return size;
 }
 
 private void reSize(int capacity){
  String[] temp = new String[capacity];
  int temp_count =0;
  for (int i = 0; i < size; i++) {
   temp[temp_count++] = data[i];
  }
  
  data = temp;
 }
}