String Matching Algorithms (Robin-Karp)

/**
 *
 * @author Lakshman
 */
import java.io.*;
public class RobinKarp
{
    String text = null, pattern = null;
    int m,n,p,q;
    public void preprocessing()
    {
        m=pattern.length();
        n=text.length();
        q=10;
        p=Integer.parseInt(pattern)%q;
        System.out.println("n = "+n+"   m = "+m+"   q = "+q+"   p = "+p+" \n");
    }
    public void string_match() throws IOException
    {
        System.out.print("\nEnter the Numeric string  : ");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    text = br.readLine();
    System.out.print("\nEnter the pattern to be searched : ");
    pattern = br.readLine();
    preprocessing();
        int i=0,rem;
    for(int s=0;s<=n-m;s++)
    {
            i=0;
            rem=Integer.parseInt(text.substring(s, s+m))%q;
            System.out.println(text.substring(s, s+m)+" --- "+rem);
            if(p==rem)
            {
                while(i<m&&text.charAt(s+i) == pattern.charAt(i))
                    i++;
                if(i==m)
                {
                    System.out.println("\t  The pattern  is found at "+(s+1)+"th location");
                    return;
                }
                else
                    System.out.println("\t Spurious hit");
            }
    }
    System.out.println("The pattern "+pattern+" is not found in the text :"+text);
    }
    public static void main(String args[]) throws IOException
    {
        RobinKarp r=new RobinKarp();
                r.string_match();
    }
}

String Matching Algorithms (Naive)

import java.io.*;
public class Naive {
    public static void main(String args[]) throws IOException  {
        System.out.print("\nEnter the Text string : ");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String text = null,pattern = null;
                        text = br.readLine();
            System.out.print("Enter the pattern to be searched : ");
            pattern = br.readLine();
        int n = text.length();
        int m = pattern.length();
        int i = 0;
        for(int s=0;s<=n-m;s++)
        {
            i=0;
                        while(i<m&&text.charAt(s+i) == pattern.charAt(i))
                   i++;
                       if(i==m)
            {
                System.out.println("The pattern "+pattern+" is found at "+(s+1)+"th location");
                return;
            }
        }
        System.out.println("The pattern "+pattern+" is not found in the text :"+text);
    }
}

String Matching Algorithms (Knuth-Morris-Pratt)

import java.io.*;
public class KMP2
{
    String text = null, pattern = null;
    int m,n,p,q=0,k;
    int pie[];
    KMP2() throws IOException{
        System.out.print("\nEnter the string  : ");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    text = br.readLine();
    System.out.print("\nEnter the pattern to be searched : ");
    pattern = br.readLine();
        n=text.length();
        m=pattern.length();
        pie=new int[m+1];

    }
    public void compute_prefix()throws IOException
    {
    pie[0]=0;
    k=0;
    for(q=1;q<m;q++)
        {
               while(k>0 && pattern.charAt(k) !=pattern.charAt(q))
                    k=pie[k-1];
               if(pattern.charAt(k)==pattern.charAt(q))
                    k=k+1;
                pie[q]=k;
    }
    }
    public void find_string() throws IOException
    {
    compute_prefix();
        System.out.print(" PI values :  ");
        for(int i=0;i<m;i++)
      System.out.print("  "+pie[i]);
        q=0;
    for(int i=0;i<n;i++)
    {
            while(q>0 && pattern.charAt(q)!=text.charAt(i))
         q=pie[q-1];
            if(pattern.charAt(q)==text.charAt(i))
        q=q+1;
            if(q==m){
        System.out.println("\nPattern occurs at "+(i-m+1)+" position");
                return;
           }
      }
    System.out.println("\nPattern not found");
    }
    public static void main(String args[]) throws IOException
    {
            KMP2 r=new KMP2();
            r.find_string();
    }
}

Analog Clock Demonstration using Java Applets

Java Applet program to demo Analog Clock

import java.applet.*;
import java.awt.*;
import java.util.*;
public class AnalogClock2 extends Applet implements Runnable {
   int width, height;
   Thread t = null;
   boolean threadSuspended;
   int hours=0, minutes=0, seconds=0;
   String timeString = "";
   public void init() {
      resize(300,300);
      width = getSize().width;
      height = getSize().height;
      setBackground( Color.BLACK);
   }
   public void start() {
         t = new Thread( this );
         t.start();
   }
   public void run() {
      try {
         while (true) {
            Calendar cal = Calendar.getInstance();
            hours = cal.get( Calendar.HOUR_OF_DAY );
            if ( hours > 12 )
                hours -= 12;
            minutes = cal.get( Calendar.MINUTE );
            seconds = cal.get( Calendar.SECOND );
            repaint();
            t.sleep(995);  // interval given in milliseconds
         }
      }
      catch (InterruptedException e) { }
   }
   void drawHand( double angle, int radius, Graphics g ) {
      angle -= 0.5 * Math.PI;
      int x = (int)( radius*Math.cos(angle) );
      int y = (int)( radius*Math.sin(angle) );
      g.drawLine( width/2, height/2, width/2 + x, height/2 + y );
   }
   void drawWedge( double angle, int radius, Graphics g ) {
      angle -= 0.5 * Math.PI;
      int x = (int)( radius*Math.cos(angle) );
      int y = (int)( radius*Math.sin(angle) );
      angle += 2*Math.PI/3;
      int x2 = (int)( 5*Math.cos(angle) );
      int y2 = (int)( 5*Math.sin(angle) );
      angle += 2*Math.PI/3;
      int x3 = (int)( 5*Math.cos(angle) );
      int y3 = (int)( 5*Math.sin(angle) );
      g.drawLine( width/2+x2, height/2+y2, width/2 + x, height/2 + y );
      g.drawLine( width/2+x3, height/2+y3, width/2 + x, height/2 + y );
   }
   public void paint( Graphics g ) {
      g.setColor( Color.red );
      for(int i=1;i<=12;i++)
        g.drawString(""+i,width/2+(int)(140*Math.sin(2*Math.PI * i / 12)), height/2-(int) (140*Math.cos(2*Math.PI * i / 12)) );
      boolean flag=true;
      g.setColor( Color.blue );
      g.setColor( Color.PINK);
      g.drawOval(WIDTH, WIDTH, width, height);
      g.drawOval(WIDTH+30, WIDTH+30, width-60, height-60);
      g.drawOval(width/2-5, height/2-5, 10, 10);
      g.setColor( Color.darkGray );
      drawWedge( 2*Math.PI * (hours/12.0+minutes/720.0 ), width/6, g );
      g.setColor( Color.BLUE );
      drawWedge( 2*Math.PI * minutes / 60, width/4, g );
      g.setColor( Color.MAGENTA );
      drawHand( 2*Math.PI * seconds / 60, width/3+10, g );
      g.setColor( Color.white );
      g.drawString( timeString, 10, height-10 );
   }
}

AVL Trees

Aim: - Implementation of AVL Tree for a given list of elements

An AVL tree is balanced binary search tree. Named after their inventors, Adelson, Velskii and Landis, they were the first dynamically balanced trees to be proposed.

The balance factor of a node is the height of its left subtree minus the height of its right subtree and a node with balance factor 1, 0, or −1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

There are four rotations to rebalance the AVL Tree based on the balance factor of a tree. These rotations come in two flavors

Single rotation 

 

 

Java program to implement AVL Tree

 

import java.io.*;

class BinarySTree{

    private Node root;

    private static class Node{

        Node left;

        Node right;

        int bal;

        int data;

         public Node(int cdata){

            left=null;

            right=null;

            data=cdata;

            bal=0;

         }

    }

    public BinarySTree()throws Exception {

            root=null;

    }

    public Node rotate(Node node) throws Exception {

         switch(node.bal)

        {

            case -2:

                 if(node.right.bal==-1){

                     System.out.println("  Left rotation    ");

                      return(rot_Left(node));

     }

                  System.out.println(" Right-Left rotation    ");

                  return(rot_RightLeft(node));

             case 2:

                if(node.left.bal==1){

                    System.out.println("  Right rotation    ");

                    return(rot_Right(node));

    }

                System.out.println("  Left-Right rotation    ");

                return(rot_LeftRight(node));

         }

         return node;

    }

    public Node rot_Left(Node node)  {

        Node temp=node.right;

        node.right=temp.left;

        temp.left=node;

        return temp;

    }

    public Node rot_Right(Node node)  {

        Node temp=node.left;

        node.left=temp.right;

        temp.right=node;

        return temp;

    }

 

    public Node rot_RightLeft(Node node)   {

        Node temp=node.right;

        node.right=temp.left.left;

        temp.left.left=node;

        return rot_Right(temp);

    }

    public Node rot_LeftRight(Node node)    {

        Node temp=node.left;

        node.left=temp.right.right;

        temp.right.right=node;

        return rot_Left(temp);

    }

    public Node findbal(Node node)throws Exception    {

        if(node!=null)

        {

          node.left=findbal(node.left);

          node.right=findbal(node.right);

          node.bal=height(node.left)-height(node.right);

          if(node.bal>1||node.bal<-1)

              node=rotate(node);

          return(node);

        }

        return node;

    }

    public void insert(int data)throws Exception    {

        root=insert(root,data);

        root=findbal(root);

    }

    public Node insert(Node node,int data){

    if(node==null)

                node=new Node(data);

    else

 if(data<=node.data)

                                node.left=insert(node.left, data);

    else

                node.right=insert(node.right, data);

    return(node);

    }

    public void Disp()throws Exception {

        if(root==null)

           System.out.println(" No Elements in the Tree ") ;

        else

        {

            System.out.println("\n Balanced Nodes in the AVL-Tree ") ;

            findbal(root);

            inorder(root);

            System.out.println("\n Height of the tree ===> "+height(root));

        }

    }

    public int height(Node node){

            if(node==null)

                  return(0);

             return max( height(node.left)+1, height(node.right)+1);

    }

 

    int max(int a,int b)   {

        return(a>b?a:b);

    }

  

 public void inorder(Node node){

        if(node!=null){

            inorder(node.left);

            System.out.println("   "+node.data+" bal("+node.bal+") ");

            inorder(node.right);

         }

    }

}

 

public class AVL {

    public static void main(String agrs[]) throws Exception  {

        BinarySTree B= new BinarySTree();

        int n, item,i=0;

        DataInputStream in= new DataInputStream(System.in);

        System.out.print("  Enter number of items to be inserted ");

        n=Integer.parseInt(in.readLine());

        while(i<n)

        {

             System.out.print("  Enter node "+(i+1)+":   ");

            item=Integer.parseInt(in.readLine());

            B.insert(item);

           i++;

        }

        B.Disp();

    }

}

 

 

OUTPUT:

Enter number of items to be inserted 7

  Enter node 1:  5

  Enter node 2:  6

  Enter node 3:  8

 Left rotation   

  Enter node 4:  3

  Enter node 5:  2

 Right rotation   

  Enter node 6:  4

 Left-Right rotation   

  Enter node 7:  7

 Right-Left rotation   

Balanced Nodes in the AVL-Tree

   2 bal(0)

   3 bal(0)

   4 bal(0)

   5 bal(0)

   6 bal(0)

   7 bal(0)

   8 bal(0)

Height of the tree ===> 3