Methodologies and principles of JAVA

METHODOLOGIES AND PRINCIPLES OF PROGRAMMING

QUESTION 1

OBJECTS:

An object has instance variables, which show its state, and instance method, which represents its behaviour. Any number of objects can be used in a program but each object belongs to some class. Object knows which class it belongs to and they can use those class data and methods.

Example:

Book mybook; // declaring a variable

Mybook = newbook(); // object creation

CLASSES:

A class is from where the objects are created. It has a name and it describes the data and methods of it objects. The classes do not know anything about their objects. Every class will have an immediate superclass and that superclass will have its own subclass and so until the root of the tree that is the object.

Example:

Public class bike

{

Public int gear;

Public int speed;

Public bike (int startgear, int start speed) // constructor

{

gear = startgear;

speed = startspeed;

}

CONSTRUCTORS:

A constructor is used in most of the classes. It is a special method, which gives the programmer over what happens at creation. The constructor has the same name of the class where it is created. The constructors will never return a value.

Example:

Public class bike // class

{

Public int gear;

Public int speed;

Public bike (int startgear, int start speed) // constructor

{

gear = startgear;

speed = startspeed;

}

INHERITANCE:

In a class there will be different types of objects. But some of the objects will have a certain amount of characteristics in common and they will have their own features in addition to that, which differentiates them from each other. Object Oriented Programming allows the subclasses to inherit the common data and methods from a super class.

Example:

Public class bike // class

{

Public int gear;

Public int speed;

Public bike (int startgear, int start speed) // constructor

{

gear = startgear;

speed = startspeed;

}

Public void setgear (int newvalue) // method

{

gear = newvalue;

}

Public void applybrake (int decrement) // method

{

speed -= decrement;

}

Public void speedup (int increment) // method

{

speed += increment;

}

}

Superclasses and subclasses:

In Java Programming Language the base class is called as a Superclass from which any number of subclasses can be derived during the flow of the program.

ENCAPSULATION:

Encapsulation refers to the way that the inner workings of an object are hidden from other objects. For example, the book class stores the name of the Author in a private variable aAuthor. However, no other code can read aAuthor directly, or even know whether it exists or not. It manages the code by breaking down the program in to smaller parts. It prevents the code from being used by unexpected ways and it makes code more reusable.

Example:

Public class book

{

Private string aTitle;

Public string Title

{

Get

{

Return aTitle;

}

Set

{

aTitle = value;

}

}

}

INTERFACES:

The word interface describes about the public view of an object but without any implementation. For example an on and off switch in a radio is an interface between the user and the electric wires inside the radio. The syntax of interface is similar to that of inheritance. Defining an interface is similar to that of creating a new class. The name of class will change and use the implements keyword in the class declaration.

Example:

Class motorbike implements bike

{

Public interface bike

{

void changegear (int newvalue)

void applybrake (int decrement)

void speedup (int increment)

}

}

POLYMORPHISM:

Two different kinds of polymorphism are overriding and overloading.

Overriding:

The keyword overriding indicates that the method has the same name as a method in base class, and is to be used instead of the base class version. An overriding method must take the same arguments as the method it overrides. Each subclass overrides the move() method in its own way.

Example:

In this example there are two classes.

The first class is plant, which has one instance method and one class method:

public class plant

{

public static void ClassMethod()

{

System.out.println("The class method in plant.");

}

public void InstanceMethod()

{

System.out.println("The instance method in plant.");

}

}

// The second class, a subclass of plant, is called Rose:

public class Rose extends plant

{

public static void ClassMethod()

{

System.out.println("The class method in Rose.");

}

public void InstanceMethod()

{

System.out.println("The instance method in Rose.");

}

public static void main(String[] args)

{

Rose myRose = new Rose();

Plant myplant = myRose;

plant.ClassMethod();

myRose.InstanceMethod();

}

}

The Rose class overrides the instance method in plant and hides the class method in plant. The main method in this class creates an instance of Rose and calls ClassMethod() on the class and InstanceMethod() on the instance.

Overloading:

In a class overloading takes place when several methods are found with a same name but with different method signatures (name + parameters). Methods declared with more than one version are called as overloaded methods. Two versions of picknum methods:

Example:

Public boolean picknum()

{

if (num == 0) return false;

num = num – 1;

return true;

}

Public Boolean picknum(int numtopick)

{

if(numtopick < 0) return false;

if(numtopick > num) return false;

num = num – numtopick;

return true;

}

Instead of writing the above two methods we can write a single method like this:

Public boolean picknum()

{

return picknum(1);

}

Public Boolean picknum(int numtopick)

{

if(numtopick < 0) return false;

if(numtopick > num) return false;

num = num – numtopick;

return true;

}

QUESTION 2

A) BUBBLE SORT

import java.io.*;

public class bubsort

{

public static void main(String arg[])

{

bubsort bs=new bubsort();

int a=10;

int data[]=new int [a];

int index;

int searchdata=1;

int i;

String indata;

BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));

System.out.println("Enter 10 data");

try

{

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

{

indata=stdin.readLine();

data[i]=Integer.parseInt(indata);

}

}

catch(IOException ioe)

{

System.out.println("number error");

}

System.out.println("The sorted numbers are");

bs.bubblesort(data,a);

}

void bubblesort (int data[] ,int N)

{

int i,j;

int temp=0;

for(i=1;i<N;i++)

{

for(j=0;j<N-i;j++)

{

if(data[j]>data[j+1])

{

temp=data[j];

data [j]= data [j+1];

data [j+1]=temp;

}

}

}

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

{

System.out.println(data[i]);

}

}

}

B) SELECTION SORT

import java.io.*;

public class selsort

{

public static void main(String arg[])

{

selsort ss=new selsort();

int a=10;

int data[]=new int [a];

int index;

int searchdata=1;

int i;

String indata;

BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));

System.out.println("Enter 10 data");

try

{

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

{

indata=stdin.readLine();

data[i]=Integer.parseInt(indata);

}

}

catch(IOException ioe)

{

System.out.println("number error");

}

System.out.println("The sorted numbers are");

ss.selectionsort(data,a);

}

void selectionsort(int data[] ,int N)

{

int i,j,min;

int temp=0;

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

{

min=i;

for(j=i+1;j<N;j++)

{

if(data[j]<data[min])

{

min=j;

}

}

if(min!=i)

{

temp=data[min];

data [min]= data [i];

data [i]=temp;

}

}

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

{

System.out.println(data[i]);

}

}

}

C) INSERTION SORT

import java.io.*;

public class insort

{

public static void main(String arg[])

{

insort is=new insort();

int a=10;

int data[]=new int [a];

int index;

int searchdata=1;

int i;

String indata;

BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));

System.out.println("Enter 10 data");

try

{

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

{

indata=stdin.readLine();

data[i]=Integer.parseInt(indata);

}

}

catch(IOException ioe)

{

System.out.println("number error");

}

System.out.println("The sorted numbers are");

is.insertsort(data,a);

}

void insertsort(int data[] ,int N)

{

int i,j;

int temp=0;

for(i=1;i<N;i++)

{

temp=data [i];

j=i;

while(j>0 && data[j-1]>temp)

{

data[j]= data [j-1];

j= j-1;

data [j]=temp;

}

}

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

{

System.out.println(data[i]);

}

}

}

D) QUICK SORT

import java.io.*;

public class qsort

{

public static void main(String arg[])

{

qsort qs=new qsort();

int a=10;

int data[]=new int [a];

int index;

int searchdata=1;

int i;

String indata;

BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));

System.out.println("Enter 10 data");

try

{

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

{

indata=stdin.readLine();

data[i]=Integer.parseInt(indata);

}

}

catch(IOException ioe)

{

System.out.println("number error");

}

System.out.println("The sorted numbers are");

qs.quick_sort(data,0,data.length-1);

}

public static void quick_sort (int[] data, int min, int max)

{

int i=min, j=max, temp;

int middle=data[(min+max)/2];

do

{

while (data[i]<middle)

i=i+1;

while (data[j]>middle)

j=j-1;

if (i<=j)

{

temp=data[i];

data[i]=data[j];

data[j]=temp;

i=i+1;

j=j-1;

}

} while (i<=j);

if (min<j)

quick_sort(data, min, j);

if (i<max)

quick_sort(data, i, max);

System.out.println("The sorted numbers are");

for(i=0; i<data.length; i++)

{

System.out.println(data[i]);

}

}

}

QUESTION 3

A) BALANCED MERGE SORT

Balanced two-way merge sort uses repeated merges to sort a data stream. By distributing the inputs into two streams, it repeatedly reads a block of input that fits in the memory, makes a run and sorting it and writing it in to the next stream. It merges the two streams repeatedly and put each merged run into one of two output streams until there is a single sorted output. If there are unsorted keys found in the list, then the list will be divided into two lists A and B almost equal length as possible. Storage space is provided for two other lists C and D for sorting. Almost the same number of merging steps is needed in both the balanced two-way merge sort and the two-way merge sort algorithms. However, the number of passes through the file for the two-way merge sort is double than that of the two-way balanced merge sort. Thus the balanced two-way merge sort algorithm is approximately twice as fast as the two-way merge sort algorithm.

Example:

The following are the numbers in a List to be sorted using the balanced two-way merge sort method.

65

23

54

76

44

32

87

55

10

90

29

The table is divided into two Lists A and B.

65

23

54

76

44

List A

32

87

55

10

90

29

List B

Now the Lists A and B are merged to get strings of length two on List C and List D

32 65

54 55

44 90

List C

23 87

10 76

29

List D

Now the Lists C and D are merged to get strings of length four on List A and List B

23 32 65 87

29 44 90

List A

10 54 55 76

List B

Now the Lists A and B are merged to get strings of length eight on List C and List D

10 23 32 54 55 65 76 87

List C

29 44 90

List D

Merge finally to get the List in the sorted order.

Algorithm:

1) Initialize the list to be sorted.

2) Read the first value in the list.

3) Use the for loop to check from the second value of the list until less than or equal to the last value in the list.

4) If the second value in the list is less than or equal to the middle value of the list.

then the address of the second value in the list is 0

else write the value of the second item in the list as it is.

5) Distribute the list in to two lists, list A and list B, by the dividing the given list by 2.

6) Use the for loop to check from the first value of list A and the first value of list B, sort and store them in the first node of list C, and check the second value of list A with the second value of list B, sort and store them in the first node of list D.

7) Continue checking until the last node in the list.

8) Now the list A and list B are empty.

9) Sort and Merge list C and list D and store the values in list A and list B, by storing the first 4 values in first node of A and the second 4 values in the first node of list B and so on.

10) Now the list C and list D are empty.

11) Sort and Merge list A and list B and store the values in list C and list D, by storing the first 8 values in first node of C and the second 8 values in the first node of list D and so on.

12) Now the list A and list B are empty.

13) Final sort and merge is done with list C and list D to get the final sorted list.

B) OSCILLATING MERGE SORT

In the merge sort methods we have seen so far all the runs are distributed initially among the working tapes, which will be followed by several passes of merge operation. We need to rewind the tapes at the beginning of each merge operation. This wills ultimately slower the merging process. So, the oscillating merge sort method was introduced to avoid this rewind time. In this method the merging process is done in both the ways, that is in the forward direction, from left to right as well as in the backward direction, right to left.

In the table shown below, five tapes, say (Ta1, Ta 2, Ta 3, Ta 4, Ta 5) are sorted with 16 initial runs. Here two notations A and D are used respectively to indicate the Ascending and the Descending runs of length R. In this method 4 initial runs are written on 4 tapes Ta1, Ta 2, Ta 3 and Ta 4. In the next pass, these runs are read in a backward direction and merged on to tape Ta5. In this pass, it will be noted that the merging is done backward producing a descending run unlike the other merge sort methods where the merging is done in a forward direction producing ascending runs. The distribution starts again, now cylindrically moved one place to the right and starts the second merge operation for the next descending run on to the tape Ta 1. This process continues until 4 descending runs are available on Ta 1, Ta 2, Ta 3 and Ta 4. When the merge process takes place after the final descending run reading backwards will produce an ascending run of relative length 16 on the tape Ta 5. This will be the sorted version of the initial 16 input runs. In all the other methods it is necessary to know the length of the input in advance whereas in the case of the oscillating merge sort method it is not necessary.

Passes

Ta 1

Ta 2

Ta 3

Ta 4

Ta 5

Remark

1

A1

A1

A1

A1

-

Initial distribution of 4 runs on to Ta 1, Ta 2, Ta 3, Ta 4

2

-

-

-

-

D4

3

-

A1

A1

A1

D4 A1

4

D4

-

-

-

D4

5

D4 A1

-

A1

A1

D4 A1

6

D4

D4

-

-

D4

7

D4 A1

D4 A1

-

A1

D4 A1

8

D4

D4

D4

-

D4

9

-

-

-

D16

-

Algorithm

1) initialize the tapes (ta), passes (m), unit, direction and j values

2) begin by checking if m=0 and if the condition is true then mark m as empty

3) else if m=1, then read one run of unit and direction

4) else use the for loop to check j=1 to ta-2

5) begin

6) now the number of runs = m / (ta-j-1)

7) m = m – runs

8) oscillating (runs, (unit + j – 2) mod ta + 2, -direction

9) MergeOneRunInto (unit, -direction) // merge backwards

10) end

11) end

C) EXTERNAL QUICK SORT

In the External quick sort method first we have to pick the middle value of the first and the last element in a file and it should be stored in the buffer. The middle value is used by the partition method, which divides the file in to file 1 and file 2. The values in the file1 will be less than or equal to the middle value and the values in the file 2 will be greater than the middle value.

The best behaviour of the external quick sort is seen when the file has even number of values. If that is the case, the first call for the external quick sort will partition the file in to two halves. The second call for the external quick sort will partition one of the halves in to two different halves and it goes on. There will be log N calls before the first data block is output. The input sequence has length N in the first call and N/2 in the second call and N/4 in the third call and so on. The sequence will have the length as N/2iin the ith call. In the final call, the sequence will have the length of N/2 (log N) before the first data block as output.

Algorithm

Extqsort

1) Initialize the variables file, first, last, pick, middle

2) Check if (first = last)

3) then the output will be Extqsort (file, first)

4) else

5) middle = pick-middle (file, (first + last) / 2)

6) partition (file, middle, file 1, file 2)

7) Extqsort (file 1, 1, |file 1|);

8) Extqsort (file 2, 1, |file 2|);

QUESTION 4

A) SEQUENTIAL ORDER

For storing data in a sequential order, a linked list is a popular data structure. For example: a list of books, a list of available jobs, a list of colleges and so on. The most typical operations of the lists are mentioned below:

(i) We can insert a new element in to a list.

(ii) We can get an element from a list.

(iii) We can delete an element from a list.

(iv) We can find the total number of elements from a list.

(v) We can find a particular element is available in a list or not.

A linked structure is made up of nodes. Each node can hold only a single element. All the nodes are connected to form a linked list. So, we can define two different classes for lists. For a clear view, we can name the class as Linked List. Array list and Linked list will have common operations but with different implementations. The common operations can be shown in the form of an interface or in the form of an Abstract class. A good way is to join the virtues of the interfaces and the Abstract classes, which give the skeletal implementation of the interface, which will ultimately reduce the effort required for the implementation of the interface.

W

X

Y

Z

Singly Linked list

B) UNIQUENESS

The linked list that we have used in the sequential order is a row like relationship between the elements. Each element in the list, except the first element will have a unique predecessor and each element in the list, except the last element will have successor and all the nodes in the list will have a unique address and values. A major problem in using the linear linked list is when a pointer is given to a node anywhere in the middle of a list, then we are able to access all the nodes that follow the pointer but we cannot access the nodes, which are behind the pointer. Because in a linear linked list structure all the pointers face in a single direction. If we want to access all the nodes then we should have the pointer at the beginning of the list.

However, we can slightly change the linear list structure by directing the pointer of the next field in the last node to the first node instead of having a NIL value in the next field of the last node. Now our linear linked list is converted in to a circular linked list. A circular linked list won't have a first node or last node. It is just a ring of list linked to each other. In a circular linked list we can start accessing from any node and still we will be able to access all the nodes without any problem. Here we can use the external pointer at any node and we will be in a position to access all the nodes since the list is in the form of a circle. In a circular linked list, we can have any number of nodes and a single node can also be used as a circular linked list by directing the pointer of its next field to the element field itself. An empty circular linked list will have a NIL value.

Circular Linked List

W

X

Y

Z

c) Hierarchical Order

In a singly linked list data structure, each node will point to another node that follows it. Thus a singly linked list is a linear structure. Each and every node in the linked list will have a unique successive node except the last node, which will have only the predecessor node and not a successive one. A tree is a nonlinear structure where each of its nodes is capable of having multiple successive nodes, which are called as the children. Each children node will have a multiple child nodes and the child nodes will also have a list of their own children nodes and so on which gives a branching structure for the tree. The root node is the starting node of the tree, which will not have predecessor since it is the starting node.

Trees are very useful to represent the hierarchical relationships among the data elements. Any node in a tree will be seen as a root of its tree. Such type of trees is called as sub tree of the original tree. This is not true in the case of the picture 2.

W

X

Y

Z

In picture 2, sub trees of W are not disjoint and there is more than one path from the root to the node Z. The node Z has two parent nodes W and X. Therefore picture 2 cannot be a tree structure.

C) HIERARCHICAL BALANCE

In a tree structure the insertion of a new node is not done when the node already exists in the tree. If a new node is inserted the tree structure will become unbalanced at any node between the nearest ancestor of the new node or the root node. In order to make the tree balanced after the insertion of the new node, the rebalancing using rotation is done with in the insert operation. After the insertion of the new node the unbalancing state of the tree happens simply when the new node is added to the sub tree. It needs a single or double rotation to retain the balance in the newly formed tree. The root pointer point to the node where the new node is inserted from the root node is called as the search path. Here the node's data are used as the keys for resemblance and it should be in ascending order.

Example: For inserting a new node and building a tree, we will start with a set of integers:

{34, 61, 6, 16, 26}

(0)

Insert 34

(+1)

(0)

Insert 61

(0)

(0) (0)

Insert 6

(-1)

(0) (0)

(0)

Insert 16

(-2)

(+2) (0) Rotate left

(+1)

(0)

Unbalanced after the insertion of 26

(-1)

(0) (0)

(0)

(0)

Balanced after Left Rotation

D) OPTIMALITY

A stored data item can be accessed by the hash table, which optimizes the speed. A hashing table data structure is normally applied in the form of a large array. We cannot simply add an item to the end of the structure. Instead the hash function will conclude the location at which a new item will be stored. The location where the new item stored is called an item's hash value. The hash value of the item should be calculated to insert or delete an item in a hash table. Once the hash value is found, then we can easily locate the specified hash value from the table. If a new item has to be inserted into hash table the location for that item should be empty for insertion, otherwise an alternative approach must be used to insert the new item. This type of incidence is called as collision.

Each location in the hash table should be used as the head of the linked list data structure, to deal with this type of collision. In the case of the linked list data structure the new item can be added to the tail end of the linked list. This method of insertion is known as open hashing because any number of items with the same hash value can be stored outside the hash table.

Another method to store the collided data inside the hash table is at a different location of their calculated hash value. That is, increase the data's hash value by one until finding an unoccupied location in the hash table. This is known as linear probing method. It is an easy way but it leads to the data crowded together, so this method is not an ideal one for handling collision.

Please be aware that the free essay that you were just reading was not written by us. This essay, and all of the others available to view on the website, were provided to us by students in exchange for services that we offer. This relationship helps our students to get an even better deal while also contributing to the biggest free essay resource in the UK!