DIGITAL CLOCK APPLET PROGRAM

import java.util.*;

import java.awt.*;

import java.applet.*;

public class MyClock extends Applet implements Runnable

{

    Thread t;

    int hh,mm,ss;

    Font myf=new Font("Arial",Font.BOLD,50);

    public void init()

    {

            t=new Thread(this);

            t.start();

    }

    public void run()

    {

        for(;;)

        {

            Calendar tm=Calendar.getInstance();

            hh=tm.get(Calendar.HOUR);

            mm=tm.get(Calendar.MINUTE);

            ss=tm.get(Calendar.SECOND);

            try

            {

                t.sleep(1000);

                repaint();

            }

            catch(Exception e)

            {

            }

        }

    }

    public void paint(Graphics s)

    {

        String now="";

        s.setColor(Color.BLUE);

        s.setFont(myf);

        now=String.valueOf(hh)+":"+String.valueOf(mm)+":"+String.valueOf(ss);

        s.drawString(now,100,100);

    }

}

BELLMAN-FORD ALGORITHM

Bellman-Ford algorithm solves the single-source shortest-path problem in the general case in which edges of a given digraph can have negative weight as long as G contains no negative cycles.

GIVEN DIGRAPH

START BY SOURCE NODE(0)

FINALLY AFTER N-1 STEPS

FOR MORE INFO http://en.wordpress.com/tag/bellman-ford/

JAVA PROGRAM TO IMPLEMENT BELLMAN-FORD ALGORITHM

import java.io.*;

import java.util.*;

public class BellmanFord {

    LinkedList<Edge> edges;

    int d[];

    int n,e,s;

    final int INFINITY=999;

    private static class Edge  {

          int u,v,w;

          public Edge(int a, int b, int c)     {

                u=a;

                v=b;

                w=c;

           }

    }

    BellmanFord() throws IOException    {

        int item;

        edges=new LinkedList<Edge>();

        DataInputStream in= new DataInputStream(System.in);

        System.out.print("Enter number of vertices ");

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

        System.out.println("Cost Matrix");

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++)   {

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

                if(item!=0)

                    edges.add(new Edge(i,j,item));

            }

        e=edges.size();

        d=new int[n];

        System.out.print("Enter the source vertex ");

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

   }

    void relax() {

        int i,j;

        for(i=0;i<n;++i)

                    d[i]=INFINITY;;

                d[s] = 0;

                for (i = 0; i < n - 1; ++i)

                     for (j = 0; j < e; ++j)

                         if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v])

                            d[edges.get(j).v] = d[edges.get(j).u] + edges.get(j).w;

    }

    boolean cycle() {

       int j;

       for (j = 0; j < e; ++j)

                         if (d[edges.get(j).u] + edges.get(j).w < d[edges.get(j).v])

                     return false;

       return true;

    }

    public static void main(String args[]) throws IOException   {

            BellmanFord r=new BellmanFord();

            r.relax();

            if(r.cycle())

             for(int i=0;i<r.n;i++)

               System.out.println(r.s+" ==> "+r.d[i]);

            else

                System.out.println(" There is a nagative edge cycle ");

    }

}

Heap sorting

Aim: - Implementation of Heap sort algorithm using Linked list as a data structure

The heap data structure is a special type of binary tree. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. The heap data structure can also be used for an efficient implementation of a priority queue. There are two types of heap

1.      Max-heap: All nodes of heap satisfy the relation that the key value at each node is at least as large as the value at its children

2.      Min-heap: All nodes of heap satisfy the relation that the key value at each node is at least as small as the value at its children

Heap sorting algorithm first organizes the data to be sorted into a heap. It does this with the following steps for sorting with max-heap

1.  Remove the topmost item (the largest) and replace it with the rightmost leaf

2.  Re-establish the heap

3.  Repeat steps 1 and 2 until there are no more items left in the heap 

     The following example shows the steps after heap as been constructed how sorting will work and how it adjust the heap.

Summary:- The complexity of the heap sort is O(nlog(n)). Heap sort is better option for large data sets. Unlike mergesort, heapsort requires no extra space. On the other hand, heapsort is not stable. A sorting algorithm is stable, if it leaves the order of equal elements unchanged.

Java Program to implement Heap sort algorithm using Linked list as a data structure

import java.util.*;

import java.io.*;

class Heap {

    LinkedList list= new LinkedList();

    int n;

    Heap(int x)  {

        n=x;

    }

    public void insert() throws IOException {

        DataInputStream in=new DataInputStream(System.in);

        int item;

        System.out.print("Enter any "+n+" integer elements");

        for(int i=0;i<n;i++)

        {

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

            list.addLast(item);

        }

    }

    public void disp() throws IOException   {

            System.out.println(" "+list);

    }

    public void construct(int num) throws IOException   {

        int i,j,k,v;

        boolean heap;

        list.addFirst(0);

        for(i=num/2;i>0;i--)

        {

        k=i;

        v=Integer.valueOf(list.get(k).toString());

        heap =false;

        while(!heap && 2*k<=num) {

            j=2*k;

            if(j<num)

                if(Integer.valueOf(list.get(j).toString())<Integer.valueOf(list.get(j+1).toString()))

                    j++;

            if(v>=Integer.valueOf(list.get(j).toString()))

                    heap=true;

            else

           {

                list.set(k,list.get(j));     

                   k=j;

            }

        }

        list.set(k,v);

        }

        list.removeFirst();

    }

    public void sort() throws IOException {

      construct(n);

      for(int i=1;i<=n;i++)  {

           Object temp=list.get(n-i);

           list.set(n-i, list.getFirst());

           list.set(0, temp);

           construct(n-i);

      }

   }

}

public class Sorting {

public static void main(String args[]) throws IOException {

    try{

        DataInputStream in=new DataInputStream(System.in);

        int count;

        System.out.println("Enter how many elements to be inserted");

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

        Heap h1=new Heap(count);

        h1.insert();

        System.out.print(" Before sorting the list is ");

        h1.disp();

        h1.sort();

        System.out.print("\n After sorting the list is ");

        h1.disp();

       }

    catch(Exception e)   {

            System.out.println("Exception ="+e);

        }

    }

}

 

 

OUTPUT:

Enter how many elements to be inserted 8

Enter any 8 integer elements

8

7

6

5

4

4

3

2

 Before sorting the list is  [8, 7, 6, 5, 4, 4, 3, 2]

 After sorting the list is  [2, 3, 4, 4, 5, 6, 7, 8]

Merge Sort Java Program

Java Program to implement Merge sort algorithm using Linked list as a data structure

import java .io.*;

import java.util.*;

class Sorter {

    LinkedList <Integer> merge(LinkedList <Integer>list1, LinkedList <Integer>list2)   {

        LinkedList <Integer> list = new LinkedList <Integer>();

        while((!list1.isEmpty())&&!list2.isEmpty())   {

           if(list1.getFirst().compareTo(list2.getFirst())<0)

               list.add(list1.removeFirst());

           else    list.add(list2.removeFirst());

       }

       list.addAll(list1);       list.addAll(list2);

       return list;

   }

   LinkedList <Integer> mergesort(LinkedList <Integer>list)   {

                LinkedList <Integer> leftlist = new LinkedList <Integer>();

                LinkedList <Integer> rightlist = new LinkedList <Integer>();

                if(list.size()<=1)

                    return list;

                int middle=list.size()/2;

                split(list,leftlist,rightlist,middle);

                leftlist=mergesort(leftlist);

                rightlist=mergesort(rightlist);

                list=merge(leftlist,rightlist);

                return list;

  }

  void split(LinkedList<Integer> list, LinkedList<Integer> leftlist, LinkedList<Integer> rightlist, int  mid) 

  {

        for(int i=1;i<=mid;i++)

            leftlist.addLast(list.removeFirst());

        rightlist.addAll(list);

  }

}

 

public class Mergesort {

    public static void main(String args[]) throws IOException   {

                Sorter s=new Sorter();

                LinkedList <Integer> list=new LinkedList <Integer> ();

                DataInputStream in=new DataInputStream(System.in);

                System.out.print("Enter how many numbers");

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

                  System.out.print("Enter any "+n+" integer elements");

                for(int x=1;x<=n;x++)

                     list.add(Integer.parseInt(in.readLine()));

                System.out.println("Berfore Sorting "+list);

                System.out.println("After Sorting "+s.mergesort(list));

    }   

}

 

 OUTPUT:

Enter how many numbers 6

Enter any 6 integer elements

8  6 4 2 1 3

Berfore Sorting [8, 6, 4, 2, 1, 3]

After Sorting [1, 2, 3, 4, 6, 8]

Merge Sort

Aim: - Implementation of Merge sort algorithm using Linked list as a data structure

Mergesort is a divide and conquer algorithm. The sorting elements are stored in a collection. This collection is divided into two sub-collections and these are again sorted via merge sort. Once the two collections are sorted then the result is combined.

Conceptually, a merge sort works as follows

1.      If the list is of length 0 or 1, then it is already sorted. Otherwise;

2.      Divide the unsorted list into two sub-lists of about half the size.

3.      Sort each sub-list recursively by re-applying merge sort.

4.      Merge the two sub-lists back into one sorted list.

Example:- List (8,3,2,9,7,1,5,4)

 

 

Summary:- Merge sort is relatively a simple to code, fast, stable sorting routine with guaranteed O(n log n) efficiency. When sorting arrays, merge sort requires additional scratch space proportional to the size of the input array

Linked List in Java

Linked List is a Dynamic Data Structure, allocates memory for any data item at run-time.  An array allocates memory for all its elements lumped together as one block of memory. In contrast, a linked list allocates space for each element separately in its own block of memory called a "linked list element" or "node".

Each node contains two fields:  a "data" field to store item data and a "next" field which is a pointer used to link one node to the next node. It can be represented as

       

In Java, Linked list can be implemented with the help of creating objects  of LinkedList class. LinkedList class implements the List interface for list operations, and permits all type elements (including null)  to be inserted. In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack and queue.

To create LinkedList object the following statement is used

LinkedList myList=new LinkedList();

The above statement creates an empty List then we can use the following functions

void add(int index,Object element): Inserts the specified element at the specified position in the list.

boolean add(Object o): Appends the specified element to the end of list

void addFirst(Object o): Inserts the given element at the beginning

void clear(): Removes all of the elements from the list.

Object get(int index): Returns the element at the specified position.

Object getFirst(): Returns the first element in the list

Object getLast(): Returns the last element in the list

Object remove(int index):Removes the element at the specified position