Algorithms II

Algorithms_2.java

==================== Data Structures ====================
1 Linear
	1.1 Arrays
	1.2 Linked Lists
	1.3 Stack
	1.4 Queues
2 Hierarchical
	2.1 Binary Tree (O(n) time complexity)
		- BFS
		- DFS 

/**************************************************************************************
 * 									GRAPHS											  *	
 **************************************************************************************/
 
==================== GRAPH PROPERTIES ====================	
1. A finite set of vertices also called as nodes.
2. A finite set of ordered pair of the form (u, v) called as edge. The pair is ordered 
because (u, v) is not same as (v, u) in case of directed graph(di-graph). The pair of 
form (u, v) indicates that there is an edge from vertex u to vertex v. The edges may 
contain weight/value/cost.

* Nodes (Vertices)
* Edges:
	- directed: Directed edges flow in a single direction. They represent a 
	             single directional relationship between any 2 nodes.
	- Undirected: Undirected Edges are bidirectional. They flow in both directions.
	- Weighted Edges: have a cost factor
	- Unweighted Edges: no unique cost factor
A Graph may contain multiple edges between the same pair of nodes and also self loops.
Self loop is an edge beginning and ending at the same node. A graph may also consist 
of cycles that is paths beginning and ending at the same node.
==================== GRAPH REPRESENTATIONS ====================	
1. Adjacency matrix (macierz sąsiedzctwa) - boolean matrix that is used to represent 
the relationship among the various nodes in a Graph (V x V where V is the number of 
vertices in a graph.)
2. Adjacency Lists - makes use of a dynamic array for each node in the graph and the 
elements of this dynamic array are the other nodes the current node is connected to. 
3. Incidence Matrix
4.  Incidence List
==================== GRAPH vs TREE ====================
A Tree is a special form of graph. It consists of N nodes and exactly N−1 edges. 
There cannot be more than 1 edges between any two pair of nodes in a tree. 
Also a tree cannot contain self-loops. There exists exactly a single path between 
any two pair of nodes in a tree. For example, if we want to travel from Node 
A to Node B in a tree, there exists only a single path to do so.
==================== GRAPH BFS IMPLEMENTATION ====================
* similar to BFS of tree, graphs may contain cycles so 'visited' var is used
* 

// Java program to print BFS traversal from a given source vertex.
// BFS(int s) traverses vertices reachable from s.
import java.io.*;
import java.util.*;
 
// This class represents a directed graph using adjacency list
// representation
class Graph
{
    private int V;   // No. of vertices
    private LinkedList<Integer> adj[]; //Adjacency Lists
 
    // Constructor
    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }
 
    // Function to add an edge into the graph
    void addEdge(int v,int w)
    {
        adj[v].add(w);
    }
 
    // prints BFS traversal from a given source s
    void BFS(int s)
    {
        // Mark all the vertices as not visited(By default
        // set as false)
        boolean visited[] = new boolean[V];
 
        // Create a queue for BFS
        LinkedList<Integer> queue = new LinkedList<Integer>();
 
        // Mark the current node as visited and enqueue it
        visited[s]=true;
        queue.add(s);
 
        while (queue.size() != 0)
        {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s+" ");
 
            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it
            // visited and enqueue it
            Iterator<Integer> i = adj[s].listIterator();
            while (i.hasNext())
            {
                int n = i.next();
                if (!visited[n])
                {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }
 
    // Driver method to
    public static void main(String args[])
    {
        Graph g = new Graph(4);
 
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);
 
        System.out.println("Following is Breadth First Traversal "+
                           "(starting from vertex 2)");
 
        g.BFS(2);
    }
}
==================== GRAPH TRAVERSALS  ====================
DFS (Recursion) or BFS (Queue)

void dfs(int i)
{
    for(int j=0;j<number_of_nodes;j++)
    {
        if(i==j)
        {
            continue;
        }
        if(a[i][j])
        {
            dfs(j);
        }
    }
}

void bfs(int u)
{
    queue<int> q;
    q.push(u);
    while(q is not empty)
    {
          int curr=q.pop();
          visited[curr]=true;
          for(every node in adjacency list of curr)
          {
                 if(!visited[node])
                 {
                        q.push(node);
                 }
          }
    }
}


/**************************************************************************************
 * 									BINARY TREE										  *	
 **************************************************************************************/
 
==================== BINARY TREE USAGE ====================
+ providing moderate access and insert/delete operations
1. Manipulate hierarchical data.
2. Make information easy to search (see tree traversal).
3. Manipulate sorted lists of data.
4. As a workflow for compositing digital images for visual effects.
5. Router algorithms
6. Form of a multi-stage decision-making (see business chess).
==================== BINARY TREE PROPERTIES  ====================
1) The maximum number of nodes at level `i` of a binary tree is 2^(i-1).
2) Maximum number of nodes in a binary tree of height ‘h’ is 2^h – 1.
4) A Binary Tree with L leaves has at least   [Log_2_L] + 1   levels

n’th Catalan Numbers:
T(n) = SUM of T(i)*T(n-i-1)
T(n) = (2n)! / (n+1)!n!
==================== BINARY TREE TRAVERSALS  ====================
Depth First Traversals:
	(a) Inorder (Left-Root-Right)
	Algorithm Inorder(tree)
	   1. Traverse the left subtree, i.e., call Inorder(left-subtree)
	   2. Visit the root.
	   3. Traverse the right subtree, i.e., call Inorder(right-subtree)
	(b) Preorder (Root-Left-Right)
	Algorithm Preorder(tree)
	   1. Visit the root.
	   2. Traverse the left subtree, i.e., call Preorder(left-subtree)
	   3. Traverse the right subtree, i.e., call Preorder(right-subtree)
	(c) Postorder (Left-Right-Root)
	Algorithm Postorder(tree)
	   1. Traverse the left subtree, i.e., call Postorder(left-subtree)
	   2. Traverse the right subtree, i.e., call Postorder(right-subtree)
	   3. Visit the root.
Breadth First Traversals
==================== BINARY TREE TYPES  ====================
1) Full Binary Tree - A Binary Tree is full if every node has 0 or 2 children
2) 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. Practical example of Complete Binary Tree is Binary Heap.
3) 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.
4) Balanced Binary Tree -  A binary tree is balanced if height of the tree is 
O(Log n) where n is number of nodes.
5) A degenerate (or pathological) tree A Tree where every internal node has one child.
Such trees are performance-wise same as linked list.
==================== BINARY TREE IN JAVA  ====================
/* Class containing left and right child of current node and key value*/
class Node
{
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}

// A Java program to introduce Binary Tree
class BinaryTree
{
    // Root of Binary Tree
    Node root;
 
    // Constructors
    BinaryTree(int key)
    {
        root = new Node(key);
    }
 
    BinaryTree()
    {
        root = null;
    }
 
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        /*create root*/
        tree.root = new Node(1);
 
        /* following is the tree after above statement
 
              1
            /   \
          null  null     */
 
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
 
        /* 2 and 3 become left and right children of 1
               1
             /   \
            2      3
          /    \    /  \
        null null null null  */
 
 
        tree.root.left.left = new Node(4);
        /* 4 becomes left child of 2
                    1
                /       \
               2          3
             /   \       /  \
            4    null  null  null
           /   \
          null null
         */
    }
}
============================================================
// Java program for different tree traversals
 
/* Class containing left and right child of current
   node and key value*/
class Node
{
    int key;
    Node left, right;
 
    public Node(int item)
    {
        key = item;
        left = right = null;
    }
}
 
class BinaryTree
{
    // Root of Binary Tree
    Node root;
 
    BinaryTree()
    {
        root = null;
    }
 
    /* Given a binary tree, print its nodes according to the
      "bottom-up" postorder traversal. */
    void printPostorder(Node node)
    {
        if (node == null)
            return;
 
        // first recur on left subtree
        printPostorder(node.left);
 
        // then recur on right subtree
        printPostorder(node.right);
 
        // now deal with the node
        System.out.print(node.key + " ");
    }
 
    /* Given a binary tree, print its nodes in inorder*/
    void printInorder(Node node)
    {
        if (node == null)
            return;
 
        /* first recur on left child */
        printInorder(node.left);
 
        /* then print the data of node */
        System.out.print(node.key + " ");
 
        /* now recur on right child */
        printInorder(node.right);
    }
 
    /* Given a binary tree, print its nodes in preorder*/
    void printPreorder(Node node)
    {
        if (node == null)
            return;
 
        /* first print data of node */
        System.out.print(node.key + " ");
 
        /* then recur on left sutree */
        printPreorder(node.left);
 
        /* now recur on right subtree */
        printPreorder(node.right);
    }
 
    // Wrappers over above recursive functions
    void printPostorder()  {     printPostorder(root);  }
    void printInorder()    {     printInorder(root);   }
    void printPreorder()   {     printPreorder(root);  }
 
    // Driver method
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        System.out.println("Preorder traversal of binary tree is ");
        tree.printPreorder();
 
        System.out.println("\nInorder traversal of binary tree is ");
        tree.printInorder();
 
        System.out.println("\nPostorder traversal of binary tree is ");
        tree.printPostorder();
    }
}