Showing posts with label program. Show all posts
Showing posts with label program. Show all posts

Sunday, 16 June 2013

The RSA Algorithm Java code

The RSA algorithm is used for both public key encryption and digital signatures. It is the
most widely used public key encryption algorithm. The basis of the security of the RSA algorithm is that it is mathematically infeasible to factor sufficiently large integers. The RSA algorithm is believed to be secure if its keys have a length of at least 1024-bits.

History
The RSA algorithm was first published in the paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems in 1977 by Ron Rivest, Adi Shamir and Len Adleman. It is named after the initials of their surnames. The paper was published in the September 1977 issue of The Scientific American. The authors offered to send their full report to anyone who sent them a self-addressed stamped envelope. The NSA did not like the idea of distributing the crytography source code internationally and requested that it be stopped. However the distribution continued when the NSA failed to provide a legal basis for their request. The algorithm was published in The Communications of the ACM the following year.

Bully election algorithm Java Program


We start with 6 processes,all directly connected to each other.Process 6 is the leader, as it has the highest number.

Process 6 fails.
Process 3 notices that Process 6 does not respond So it starts an election, notifying those processes         with ids greater than 3.


Both Process 4 and Process 5 respond, telling Process 3 that they'll take over from here.


Process 4 sends election messages to both Process 5 and Process 6.

Saturday, 1 June 2013

Binary Tree Java Program

Introduction

We extend the concept of linked data structures to structure containing nodes with more than one self-referenced field. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root.
Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings.
  
More tree terminology:
  • The depth of a node is the number of edges from the root to the node.
  • The height of a node is the number of edges from the node to the deepest leaf.
  • The height of a tree is a height of the root.
  • A full binary tree.is a binary tree in which each node has exactly zero or two children.
  • A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.
A complete binary tree is very special tree, it provides the best possible ratio between the number of nodes and the height. The height h of a complete binary tree with N nodes is at most O(log N). We can easily prove this by counting nodes on each level, starting with the root, assuming that each level has the maximum number of nodes:
n = 1 + 2 + 4 + ... + 2h-1 + 2h = 2h+1 - 1
Solving this with respect to h, we obtain
h = O(log n)
where the big-O notation hides some superfluous details.

Advantages of trees

Trees are so useful and frequently used, because they have some very serious advantages:
  • Trees reflect structural relationships in the data
  • Trees are used to represent hierarchies
  • Trees provide an efficient insertion and searching
  • Trees are very flexible data, allowing to move subtrees around with minumum effort

Traversals

A traversal is a process that visits all the nodes in the tree. Since a tree is a nonlinear data structure, there is no unique traversal. We will consider several traversal algorithms with we group in the following two kinds
  • depth-first traversal
  • breadth-first traversal
There are three different types of depth-first traversals, :
  • PreOrder traversal - visit the parent first and then left and right children;
  • InOrder traversal - visit the left child, then the parent and the right child;
  • PostOrder traversal - visit left child, then the right child and then 

Download Program With OUTPUT


Graph Data Structures Java Program

Graphs, vertices and edges

A graph is a collection of nodes called vertices, and the connections between them, called edges.

Undirected and directed graphs

When the edges in a graph have a direction, the graph is called a directed graph or digraph, and the edges are called directed edges or arcs. Here, I shall be exclusively concerned with directed graphs, and so when I refer to an edge, I mean a directed edge. This is not a limitation, since an undirected graph can easily be implemented as a directed graph by adding edges between connected vertices in both directions.
A representation can often be simplified if it is only being used for undirected graphs, and I'll mention in passing how this can be achieved.

Neighbours and adjacency

A vertex that is the end-point of an edge is called a neighbour of the vertex that is its starting-point. The first vertex is said to be adjacent to the second.

An example

The following diagram shows a graph with 5 vertices and 7 edges. The edges between A and D and B and C are pairs that make a bidirectional connection, represented here by a double-headed arrow.


Download Program With OUTPUT



Program Doubly Linked List Java

Overall Structure of Doubly-Linked Lists

If you wish to traverse a list both forwards and backwards efficiently, or if you wish, given a list element, to determine the preceding and following elements quickly, then the doubly-linked list comes in handy. A list element contains the data plus pointers to the next and previous list items as shown in the picture below.


Of course we need a pointer to some link in the doubly-linked list to access list elements. It is convenient for doubly-linked lists to use a list header, or head, that has the same structure as any other list item and is actually part of the list data structure. The picture below shows an empty and nonempty doubly-linked list. By following arrows it is easy to go from the list header to the first and last list element, respectively.





Download Program With OUTPUT


Linked Stack Java Program

One disadvantage of using an array to implement a stack is the wasted space---most of the time most of the array is unused. A more elegant and economical implementation of a stack uses a linked list, which is a data structure that links together individual data objects as if they were ``links'' in a ``chain'' of data.
Here is a sketch of a linked-list-based ``stack'' that holds 1, then 5, and then 20 at the bottom:
          ---
top ---> | 1 |
         |---|      ---
         | o-|---> | 5 |
          ---      |---|      ----
                   | o-|---> | 20 |
                    ---      |----|
                             |null|
                              ----
The list consists of three ``cells,'' each of which holds a data object and a ``link'' to another cell. A variable, top, holds the address of the first cell in the list. An empty stack looks like this:
top ---> null
(That is, variable top holds value, null.) Each time an object is pushed, a cell is constructed, the object is inserted into the cell, and the cell is linked to the front of the chain of cells. For example, pushing 20 onto the empty stack gives us
          ----
top ---> | 20 |
  |--- | 
  |null|
          ----
After 5 and then 1 are pushed, we obtain the picture first seen.
Say that we pop an object from the stack; the picture changes to this:
                    ---
          top ---> | 5 |
            |---|      ----
                   | o-|---> | 20 |
                    ---      |----|
                      |null|
                              ----
Download Program With OUTPUT

Linked List Java Program

One disadvantage of using arrays to store data is that arrays are static structures and therefore cannot be easily extended or reduced to fit the data set. Arrays are also expensive to maintain new insertions and deletions. In this chapter we consider another data structure called Linked Lists that addresses some of the limitations of arrays.
A linked list is a linear data structure where each element is a separate object.

Each element (we will call it a node) of a list is comprising of two items - the data and a reference to the next node. The last node has a reference to null. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.
A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application which has to deal with an unknown number of objects will need to use a linked list.
One disadvantage of a linked list against an array is that it does not allow direct access to the individual elements. If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
Another disadvantage is that a linked list uses more memory compare with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.

Download Program With OUTPUT

Queue Java Program

Queues


A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. An excellent example of a queue is a line of students in the food court of the UC. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access.The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

 
Download Program With OUTPUT

Circular Queue Java Program

Given an array A of a default size (≥ 1) with two references back and front, originally set to -1 and 0 respectively. Each time we insert (enqueue) a new item, we increase the back index; when we remove (dequeue) an item - we increase the front index. Here is a picture that illustrates the model after a few steps:
As you see from the picture, the queue logically moves in the array from left to right. After several moves back reaches the end, leaving no space for adding new elements
However, there is a free space before the front index. We shall use that space for enqueueing new items, i.e. the next entry will be stored at index 0, then 1, until front. Such a model is called a wrap around queue or a circular queue
Finally, when back reaches front, the queue is full. There are two choices to handle a full queue:a) throw an exception; b) double the array size.

The circular queue implementation is done by using the modulo operator (denoted %), which is computed by taking the remainder of division (for example, 8%5 is 3). By using the modulo operator, we can view the queue as a circular array, where the "wrapped around" can be simulated as "back % array_size". In addition to the back and front indexes, we maintain another index: cur - for counting the number of elements in a queue. Having this index simplifies a logic of implementation.

Download With OUTPUT

Covert Infix to Postfix Java Program

Infix Expression : 

Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.

Postfix Expression : 

The Postfix(Postorder) form of the above expression is "23*45/-".

Infix to Postfix Conversion : 

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows :

  • Scan the Infix string from left to right.
  • Initialise an empty stack.
  • If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character tostack.
    • If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack(topStack). If topStack has higher precedence over the scanned character Popthe stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character.
    Repeat this step till all the characters are scanned.
  • (After all characters are scanned, we have to add any character that the stackmay have to the Postfix string.) If stack is not empty add topStack to Postfix stringand Pop the stack. Repeat this step as long as stack is not empty.
  • Return the Postfix string.
Example : 

Let us see how the above algorithm will be imlemented using an example. 

Infix String : a+b*c-d 

Initially the Stack is empty and our Postfix string has no characters. Now, the first character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is pushed to the stack. 


Stack

Postfix String

Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will be pushed to the stack. 


Stack

Postfix String

The next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack. 


Stack

Postfix String

Next character is 'd' which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be : 


Stack

Postfix String

End result :

  • Infix String : a+b*c-d
  • Postfix String : abc*+d-

Download Program With OUTPUT


Copy Paste File to File Java


import java.io.*; 
class FileToFile
{
 public static void main(String args[])throws Exception
  {
   char x;
   FileInputStream ip=null;
   FileOutputStream op=null;

   ip=new FileInputStream("input.txt");
   op=new FileOutputStream("output.txt");
   x=(char)ip.read();
   while(x!='.')
   {
     op.write(x);
     x=(char)ip.read();
   }
   ip.close();
   op.close();
  } 
}

Download With OUTPUT

Factorial Recursion Java

Program for Signed Multiplication using Booth's Algorithm

Booth's algorithm is a multiplication algorithm which worked for two's complement numbers. It is similar to our paper-pencil method, except that it looks for the current as well as previous bit in order to decided what to do. Here are steps

  • If the current multiplier digit is 1 and earlier digit is 0 (i.e. a 10 pair) shift and sign extend the multiplicand, subtract with previous result.
  • If it is a 01 pair, add to the previous result.
  • If it is a 00 pair, or 11 pair, do nothing.
Let's look at few examples.
           4 bits
            0110   <- 6
        x   0010   <- 2
   -------------
        00000000
     -     0110
  --------------
        11110100
     +    0110
  --------------
    (1) 00001100  <- 12     (overflow bit ignored)
         8 bits
In Booth's algorithm, if the multiplicand and multiplier are n-bit two's complement numbers, the result is considered as 2n-bit two's complement value. The overflow bit (outside 2n bits) is ignored.
The reason that the above computation works is because
      0110 x 0010 = 0110 x (-0010 + 0100) = -01100 + 011000 = 1100.
Example 2:
            0010
         x  0110
     ------------
        00000000
    -      0010
    -------------
        11111100
    +    0010
    -------------
    (1) 00001100
In this we have computed
    0010 x 0110 = 0010 x ( -0010 + 1000) = - 00100 + 0010000 = 1100

Download With OUTPUT

Program for Restoring Division.


Restoring (conventional) binary divide, twos complement 4-bit numbers

                                1 1 0 0   quotient
                       ________________
             0 1 1 1  / 0 1 0 1 0 1 0 1
                       -0 1 1 1      may subtract by adding twos complement
                        _______          - 0 1 1 1   is   1 0 0 1
   5 - 7 = -2           1 1 1 0
   negative, add 7     +0 1 1 1
   restored             _______
   next bit               1 0 1 0
                         -0 1 1 1
                          _______
   10 - 7 = 3               0 1 1 1
   quotient=1, next bit    -0 1 1 1
                            _______
   7 - 7 = 0                0 0 0 0 0
   quotient=1, next bit      -0 1 1 1
                              _______
   0 - 7 = -7                 1 0 0 1
   negative, add 7           +0 1 1 1
   quotient=0                 _______
   restored, next bit           0 0 0 1
                               -0 1 1 1
                                _______
   1 - 7 = -6                   1 0 1 0
   negative, add 7             +0 1 1 1
   quotient=0                   _______
   restored, finished           0 0 0 1   final remainder
   (8 cycles using adder)

Download With OUTPUT

Program for Implementation of Non-Restoring Algorithm.

 non-restoring binary divide, twos complement 4-bit numbers
  note: 7 = 0 1 1 1     -7 = 1 0 0 1


                                1 1 0 0   quotient
                       ________________
             0 1 1 1  / 0 1 0 1 0 1 0 1
   pre shift             +1 0 0 1         adding twos complement of divisor
                          _______
   10 - 7 = 3             0 0 1 1 1
   quotient=1              +1 0 0 1
   next bit subtract        _______
   7 - 7 = 0                0 0 0 0 0
   quotient=1                +1 0 0 1
   next bit subtract          _______
   0 - 7 = -7                 1 0 0 1 1
   quotient=0                  +0 1 1 1    adding divisor
   next bit add                 _______
   2 + 7 = 9 = -7               1 0 1 0
   quotient=0                  +0 1 1 1
   correction add               _______
   final remainder              0 0 0 1    remainder
   (5 cycles using adder)

Download With OUTPUT