Counting Sort

Counting Sort is a kind of sort which you can use, only when you have prior knowledge about the kind of data you are sorting. For counting sort, we need to know about the range of the give data eg: o – 100, 200 – 1000. We do counting sort in two steps:

1. Count the number of times an element/ integer has occured in the given list.
2. perform prefix on the count array.
2. Find the position of the element according to count of elements which are before to it.

Following is the example demostrating counting sort:

Input: 5 1 5 1 3
count:2 0 1 0 2
prefix – count: 2 2 3 3 5
Output: 1 1 3 5 5

To find the output array, we do the following:

1. pick the element from the input array. Let us pick 5 which occured first and call it X.
2. Find the integer which is placed at X in the prefix count array. i.e. position = prefixCount[X-1].
3. This is the position of the element in the output and decrement the value of in the prefix-count array.

Following is the C code for counting sort.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

void countingSort(int , int *);
void display(int, int *);
/* Main Method takes the input from the users and performs counting sort on the input_array */
void main() {
        int *input_array, size, index, ch;
        srand(time(NULL));
        printf("Enter the size of the array: ");
        scanf("%d", &size);
        input_array = (int *)malloc(sizeof(int) * size);
        printf("\n\n1. Random Number Generation\n2. User Input\nEnter choice from above: ");
        scanf("%d", &ch);
        if(ch == 1){ //Random Generation
                for(index=0; index<size; index++)
                        input_array[index] = rand()%99 + 1 ; //Will generate numbers in the range of 1 - 100.
        } else if (ch == 2) { //User Input
                printf("\nPlease enter value less than 100\n");
                for(index = 0; index<size; index++) {
                        printf("\nEnter the element to be sorted: ");
                        scanf("%d", &input_array[index]);
                        while(1) {
                                if (input_array[index] < 0 || input_array[index] > 100) {
                                                printf("Please enter only positive values and values less than 100 only:");
                                                scanf("%d", &input_array[index]);
                                }
                                else
                                        break;
                        }
                }
        }
        else {
                printf("\nPlease Enter correct Choice, re-run the program");
        }
        printf("\n\nRandomly Generated data is: ");
        display(size, input_array);
        countingSort(size, input_array);
}
void display(int size, int *array) {
        int index;
        for(index=0;index<size;index++)
                printf("%d ", array[index]);
}
void countingSort(int size, int *input_array) {
        int *count_array, *sorted_array, position, index;
        count_array = (int *)calloc(100, sizeof(int));
        sorted_array = (int *)malloc(sizeof(int) * size);

        for (index=0;index<size;index++) //Find number of times item has appeared.
                count_array[input_array[index]]++;
        for (index=1;index<100;index++) //Perform prefix sum on count_array.
                count_array[index] += count_array[index-1];
        for (index=0;index<size;index++) { //Find the position fo the element and palce element inthat position of sorted_array.
                position = count_array[input_array[index]]--;
                sorted_array[position-1] = input_array[index];
        }
        printf("\n\nSorted array is: ");
        display(size, sorted_array);
        printf("\n");
}

The code performs counting sort.
Output:
counting sort

Download code from here.

Advertisements
Posted in Algorithms, C | Tagged , , , , | Leave a comment

Dijkstras Alogrithm – Python

Dijkstras’s algorithm or shortest path algorithm is for finding the shortest path between two nodes in a graph which represents a map or distances between places.

The algorithm requires 3 inputs: distance matrix, source node and destination node. The implementation of algorimth is as follows:

1. Start from source node.
2. Check distances of all nodes which are connected from source, select the node with least distance from source.
3. Check distance from this temporary node to its all connected nodes and select the node with least distance.
4. Now repeat this process untill destination is reached.

In the following code, the list src2dist list is used for storing all the distances of the nodes which are connected to source. visited list is used to keep track of which nodes are visited which are not. 9999 specifies a infinite path from src to that particular node.

import math
def dijkstra(distances,src,dst):
	num_cities = int(math.sqrt(len(distances)))
	src2dist = [9999 for i in range(0, num_cities)]
	visited = [0 for i in range(0, num_cities)]
	tmp_start = src
	visited[src] = 1
	src2dist[src] = 0
	
	while (visited[dst] == 0):
		min_edge = 9999
		min_node = -1
		for i in range(0, num_cities):
			d = src2dist[tmp_start] + distances[(tmp_start*num_cities)+i]
			if (d < src2dist[i] and visited[i] == 0):
				src2dist[i] = d
			if (min_edge > src2dist[i] and visited[i] == 0):
				min_edge = src2dist[i]
				min_node = i
		tmp_start = min_node
		visited[tmp_start] = 1
	print ("The smallest distance between source and destination is:"src2dist[dst])
	
distances = input("Enter distance matrix separated by spaces:").split(" ")
distances = [int(x) for x in distances]
src_dst = input("Enter source and destination separated by space:").split(" ")
src = int(src_dst[0])
dst = int(src_dst[1])
dijkstra(distances,src,dst)

Output:
dijkstras
Download code from here

Posted in Python | Tagged , , , | Leave a comment

Searching Algorithms Linear, Binary in Python

Two of the basic search algorithms are Linear search and Binary search. Linear search is very straight in it’s implementation. On the other hand, binary search is something which tries to reduce the time complexity of searching for any give amount of data.

Time complexity of Linear, Binary searches are in worst case scenario: O(n), O(logn) respectively.

The implementation of Linear search is as follows: check the key with each and every element from the starting of the data. If the lenght of the give data is n and key matches with the last element of the data, then it will take n iterations to search for the key. Hence the complexity of O(n).

In case of binary search, sort the give data either in increasing order or decreasing order. Check if middle element matches the key then key is found, Else check if middle element is greater than key then we need not to search for the half of data which is greater than key, hence move the last to middle -1. If middle element is less than key then move first to middle + 1.

The following code has menu which have options for both Linear search, Binary search.

def lsearch(data, key):
	flag = 0
	for i in range(0, len(data)):
		if data[i] == key:
			flag = 1
			print("Key found at position:", i)
	if(flag == 0):
		print("Key not found in the give list")

def bsearch(data, key):
	flag = 0
	first = 0
	last = len(data) - 1
	middle = int((first + last) / 2)
	sort(data)
	while(first <= last):
		if(data[middle] == key):
			flag = 1
			print("key found")
			break;
		elif(data[middle]> key):
			last = middle - 1
			middle = int((first + last) /2)
		else: 
			first = middle + 1
			middle = int((first + last) /2)
	if(flag == 0):
		print("Key not found in the give list")

def sort(data):
	for i in range(0, len(data)):
		for j in range(i+1, len(data)):
			if(data[i] > data[j]):
				data[i], data[j] = data[j],data[i]

data = input("Enter data separated by spaces:").split(" ")

while(True):
	print("\n1. Linear Search\n2. Binary Search\n3. Exit");
	choice = int(input("\nEnter your choice from above menu:"))
	if(choice == 1):
		key = input("Enter the key to be searched:")
		lsearch(data, key)
	elif(choice == 2):
		key = input("Enter the key to be searched:")
		bsearch(data, key)
	elif(choice == 3):
		break;
	else:
		print("Please enter a correct choice")

Output:
search
Download link

Posted in Python, Uncategorized | Tagged , , , , , | Leave a comment

Sudoku – Solver

After a long time I’m writing this post. Today, I would like to explain you one of my project which I have worked on. This my programming Languages project – A 16 X 16 Sudoku Solver with a Java Driven program.

User can select any one of the language among C, Java, Python, Javascript, Prolog to solve the given sudoku. Details of this project are presented below:

1. A Java driven application is developed which takes input from the user to invoke solver in the respective language.

2. This is designed to solve 16 X 16 Sudoku given enough default values to it.

3. The logic used for solving is same in all languages. The coding part of the logic differs according to languages.

Let us see how the logic works in a language and we can figure it out in other languages.

public static boolean solve(char[] grid, int cell) //This is a recursive function which checks cell by cell for solution.
	   {
		  char[] options = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'}; 
	      while (cell < 256 && grid[cell] != '.') //Checks if cell is empty or not.
	         cell++;
	      if(cell == 256)
	         return true;

	      for(int i = 0; i < 16; i++)
	      {
	    	  grid[cell] = options[i];	//Take an option from options array and place it in the cell.
	          if(isColumnValid(grid, cell % 16)) //Now check the column of the cell and if true move forward.
	             if(isRowValid(grid, cell / 16)) //Check the row of the cell and if true check Block
	                if(isBlockValid(grid, cell % 16, cell / 16)) //The corresponding block of the cell.
	                	if(isValid(grid) && solve(grid, cell +1)) //Check if entire grid is valid or not.
	                		return true;
	       }
	      grid[cell] = '.';
	      return false;

This is a recursive solution i.e if the solution for a particular cell satisfies all the required constraints, then we call the solve function recursively with goal of finding solution for the next cell in the sudoku if it is empty. An empty cell is defined by ‘.’.

The main logic is:
1. Check if a cell is empty i.e the value of cell is == ‘.’ . If it is empty, then goto step 2.

2. Change the value of the cell from ‘.’ to a value picked up from options array using the for loop.

3. Now, check if modified grid is valid or not. For grid to be valid, it need to satisfy 3 conditions. Every column, row should have all unique values. No repetition of values in the Block. There are 16 Columns, Rows and Blocks.

4. If changing of a grid value from ‘.’ to an option value violates any of the above three condition then we should return False, and run the for loop over the same cell with value from other option.

5. If a value for a given cell satisfies all condition, then we call solve() method recursively trying to solve next cell.

In order to solve a sudoku in python language, I used process builder to create new process and execute the python command. The solution from python is returned to java as a string.

String[] cmd = new String[3];
cmd[0] = "python";
cmd[1] = "sudoku_solver.py";
cmd[2] = ip;
Process pr = Runtime.getRuntime().exec(cmd);
BufferedReader in = new BufferedReader(new InputStreamReader(pr.getInputStream())); //Gathering the output of the python program into a string
String python_output = in.readLine();

For solving the sudoku in Javascript, there is built in Script class which allow us to call Javascript Engine. Solution is returned to Java from Javascript as a string.

ScriptEngineManager factory = new ScriptEngineManager();//Creating an engine to inovke JavaScriptEngine.						ScriptEngine engine = factory.getEngineByName("JavaScript");						
engine.eval(Files.newBufferedReader(Paths.get("/import/linux/home/adesu1/plprj/sudoku_solver.js"),StandardCharsets.UTF_8));
Invocable inv = (Invocable)engine;
String Js_ret = inv.invokeFunction("solve_JS",ip).toString();

All the source files are here.

Any doubts regarding working it out can be placed in comments section.

Posted in C, Java, Python | Tagged , , , , , , , , , , , , , , | Leave a comment

Python Insertion Sort

After learning about classes in python, today in this post we shall use those concepts in making insertion sort program. Insertion sort is one of the basic sorting techniques other than, bubble sort.

It compares key element with the previous element. If the key element is less than previous element, then those two elements are swapped and again the key element is compared with previous element and process goes on.

We could sort data either in ascending order or descending order.

class insertion(object):
	"""docstring for ClassName"""
	def __init__(self, size, ch):
		self.size = size
		self.ch = ch
		self.data = []
		for i in range(size):
			self.data.append(input("Enter number into list:"))
		if(ch == 1):
			self.ascsorting()
		else:
			self.dscsorting()
	def ascsorting(self):
		for i in range(1,self.size):
			j = i
			while  j > 0 and int(self.data[j-1]) > int(self.data[j]):
				self.data[j-1], self.data[j] = self.data[j], self.data[j-1]
				j= j-1
		print ("\nSorted Data is: " + str(self.data))
	def dscsorting(self):
		for i in range(1, self.size):
			j = i
			while j>0 and int(self.data[j-1]) < int(self.data[j]):
				self.data[j-1], self.data[j] = self.data[j], self.data[j-1]
				j = j-1
		print ("\nSorted Data is " + str(self.data))

ch = int(input("Enter choice according to order of sort 1.ascending order 2. Descending order: "))
size = int(input("Enter size of the list: "))
a = insertion(size, ch)

In the above code, we have created a class called insertion to direct the sorting either in ascending order or descending order. The method __init__(self, size, ch) is constructor for insertionn class. It takes three arguments, self which is default argument used to point the class variables. “size” argument is passed during the creation of object for insertion class which says, the number of elements in the given list. “ch” argument is for either ascending order or descending order.
Output:
insertion

Download the Source Code

Posted in Python | Tagged , , , , , | Leave a comment

Object Oriented programming in python – Classes

Object Oriented programming or OOP’s concept in python is same as in any other language. Python is an object oriented language. The very same concept of classes and it’s objects as in Java can be implemented in Python. Let us recall the some of the basic terminology of Object Oriented Programming.

1. Class: A user defined data-type. It consists of set of attributes that describe the functionality of instances created to the class. Atrributes can be, data members or methods. Each of these are called using dot operation.

2. Class Variable: Some time we need to keep track of number of objects created for a particular class, in that class variables are useful. Hence, that particular data member should be common to all the instances of the class. Any instance can call the data member and can change it’s value which is reflected on every other instances.

3. Data Member: Unlike class variable it is called as instance vairable, because every instance will have it’s own data member. It can’t be accessed by the other instance of the class.

4. Methods: Each class will have it’s own set of methods which will operate on the data members of that instance and class variables also. These methods of instances are called using dot operation.

5. Function Overloading or Method Overloading: Defining two different operations for same function name is called as Function Overloading. Those two functions are differentiate by their arguments. Python does not support function overloading. The function which is defined first will be hidden and can’t be called.

6. Instance: Objects for particular class will have it’s own set of data members and methods accessing those data members. Eg: obj1. x is different from obj.2

7. Inheritance: The concept of reusing already defined class to produce more specialized classes is called as inheritance. Eg: We can inherited CAR class to create classes like JAGUAR, AUDI, PROSCHE. CAR class will define the basic requirements needed for a car(such as steering, 4 wheels etc). Child classes(JAGUAR, AUDI etc) will inherit CAR and will add more specifications.

Creating Classes:

class class_name(object):
	#define attributes and methods
	.
	.

Let us create a student class.

class Student(object):
   def __init__(self, name, age, std):
      self.name = name
      self.age = age
      self.std = std
   
   def displayDetails(self):
     print ("Name of student" + self.name)
     print ("Age of student: " + str(self.age))
     print ("Student studying in class: " + str(self.std))
     print ()

john = Student("John", 15, 10)
john.displayDetails()
john.name = "John willamson"
john.displayDetails()

1. Creating Class: In the above code we have created simple class students which contains the attributes name, age, std and methods to display the details of student.

2. Creating Instances: Now, john is called as instances of the class. When ever an instance is created __int__ method of class is invoked automatically and instance variables name, age and std as assigned their particular values.

3. Accessing data members through instances: Now using dot operator we can call method displayDetails() to print the details of the particular student. We can also access data members using dot operator, here we have renamed “John” to “John willamson”.

Output:


classes in python

Posted in Python | Tagged , , , , , , , , , , , , , | Leave a comment

Python Program to Check Armstrong Number

Python Program to Check Armstrong Number is one of the basic program in learning python programming language. The property of Armstrong number is, if the sum of the cubes of the digits of number is same as the given original number, then that number is treated as Armstrong Number. The number 153 is regarded as Armstrong number because 1^3 + 5^3 + 3^3 = 153(1+125+27). Now we shall writing a program to check whether given number is armstrong or not.

1. We need to get the input from the user using input() function.
2. Later on we need to convert the the given input to int data type using inbuilt int() function.
3. The main logic is, we need to identify every digit of the given number. This is done using / and % operator upon the given number by 10.
4. If a number is / by 10, then output is quotient i.e all digits of the given number except Last ONE.
For eg: 152/10 = 15.
5. If a number is % by 10, then output is last digit of the number.
For eg: 152%10 = 2.
6. Hence, by running a while loope until number becomes zero will gives us all the digits of the input number.

num = input("Enter number to check for Armstrong:")
result = 0;
temp = int(num)
while(temp>0):
	remainder= int(temp%10)
	temp=temp/10
	result=result+(remainder*remainder*remainder)
if(int(result) == int(num)):
	print("Given number " + num +" is an Armstrong number.");
else:
	print("Given number " + num +" is not an Armstrong number.");

Output:
armstrong

Download the Source Code

Posted in Python | Tagged , , , , , , , | Leave a comment

Python Functions

Python Functions

Functions plays an important role in simplifying the execution of a program. We can easily divide the work into different parts using functions. Main function will be in charge of calling each and every other function in the given order. Each function will perform a certain task and carry out the result of the function to the main, such that it can be given as input to the other calling function.

Rules for defining functions in python:

1. Every function should be defined with the def key word followed by function name and paranthesis() and ending with colon :.

2. Any arguments to the function should be declared in the paranthesis.

3. The comments for explaning working of the function is optional and if written should be in ” “.

4. The code should starts only after : and it should be intended.

5. The return statement is optional and return without parameters is same as return none.

def func_name( parameters) : //Declaring function and parameters
    code;
    code;
    return ; //Return statement if any

Sample function in python, addition of two numbers.

def add(num1, num2):
	num1 = int(num1)+int(num2);
	print("\n Addition of given two numbers is:" + str(num1));

num1 = input("\n Enter number 1 for addition:");
num2 = input("\n Enter number 2 for addition:");
add(num1,num2);

Output:
func
Download the Source code

Posted in Python | Tagged , , , , , , , , , , , , , , , | Leave a comment

Insertion Sort in C

What is Insertion Sort? As said Before, Insertion sort is better technique when compared to Bubble sort. But it cant handle data of large size. So we need to go for selection sort and heap sort techniques. Insertion Sort is done by comparing key element with the predecessor and sort them according to the result. If the element is larger than key element, then swap both the elements and again compare key element with the predecessor. Insertion sort in Java

#include <stdio.h>
#include <conio.h>
void sort(int);

void main(){
    int size;

    printf("\n Enter size of the array: "); //Request for size of array
    scanf("%d",&size);
    sort(size); //Invoking sorting function with size as parameter

    getch();
};

void sort(int size){
    int data[size],i,j,order,temp;

    for(i=0;i< size; i++){
        printf("\n Enter data into the array: "); //Enter the data into the array
        scanf("%d",&data[i]);
    }

    for(i=1;i<size;i++){
        	j=i;
        	while(j>0 && data[j-1] > data[j]){
        		temp = data[j-1];
        		data[j-1] = data[j];
        		data[j] = temp;
        		j--;
        	}
    }

    printf("\n Sorted data is:\n"); //Display of final sorted data
        for(i=0;i<size;i++){
            printf("\t%d",data[i]);
        }
}

Output:
insertion output

Download the Source Code

Posted in C | Tagged , , , , , , , , , , , , , , , | 1 Comment

Bubble sort in C

What is Bubble sort? Bubble sort is one of the basic and simple sorting techniques. Bubble sort is not advisable for huge amount of data. In today world, we may not be able to employ bubble sort technique because of the size of the data. But, learning a basic and easiest techniques will help us in improving our knowledge and will lay as foundation for further advanced techniques.

In this method, we sort the entire array by comparing each and every element with next element. If the next element is smaller than current element, then those two elements are swapped and if it is greater then left intact. For Bubble sort program in Java

The code below is self explanatory:

#include <stdio.h>
#include <conio.h>
void sort(int);

void main(){
    int size;

    printf("\n Enter size of the array: "); //Request for size of array
    scanf("%d",&size);
    sort(size); //Invoking sorting function with size as parameter

    getch();
};

void sort(int size){
    int data[size],i,j,order,swap;

    for(i=0;i< size; i++){
        printf("\n Enter data into the array: "); //Enter the data into the array
        scanf("%d",&data[i]);
    }

    printf("\n Enter for 1 for ascending order or 2 for descending order: "); // Ascending order or descending order
    scanf("%d",&order);

    if(order == 1){
            /*Ascending order*/
            for(i=0;i<size;i++){
                for(j=0;j<size-1;j++){
                    if(data[j] > data[j+1]){
                        swap      = data[j];
                        data[j]   = data[j+1];
                        data[j+1] = swap;
                    }
                }
            }
        }

        else {
            /*Descending order*/
            for(i=0;i<size;i++){
                for(j=0;j<size-1;j++){
                    if(data[j] < data[j+1]){
                        swap      = data[j];
                        data[j]   = data[j+1];
                        data[j+1] = swap;
                    }
                }
            }
        }

        printf("\n Sorted data is:\n"); //Display of final sorted data
        for(i=0;i<size;i++){
            printf("\t%d",data[i]);
        }
}

Output:
bubble

Download the Source Code

Posted in C | Tagged , , , , , , , , , , | 1 Comment

Java program for Insertion Sort

what is insertion sort?
Insertion sort is one of the techniques available for re-arrangement of given input variables. The efficiency of this techinique decreases with the increase in the size of the input data. That is insertion sort is advisable only if the size of the data is limited. To sort data of higher size, there are advanced techniques which can sort them with better efficiency. One of the basic sorting technique is Bubble sort.

For every single iteration in insertion sort, single element will be sorted to it’s final position in the array. Single element will be considered for every iteration and compared with before element in the array.

Let us consider, input data be 3 4 1. Insertion sort starts with 1st element of the array(If you are numbering it from 0) or starts for 2nd element of the array(If you are numbering it from 1) and will be regarded as key element of that particular iteration. Here the key element for 1st iteration is 4 and the key element will be compared with the predecessor elements of the array. If the predecessor is greater than key, then sort two elements. If predecessor is not greater than key, leave it intact. In the next round of iteration the key element will be 1 and it will be compared with 4. Since predecessor is greater than 1, those two elements are sorted and again 1 will be compared with 3. 1 and 3 are sorted and the entire array is sorted.

Insertion Sort in C

import java.io.*;
import java.util.*;

public class insertion{
	public static void main(String args[]){
		Scanner in = new Scanner(System.in);
		int i,j,temp;

		System.out.print("\n Enter size of the array: ");
		int size = in.nextInt();

		int[] data = new int[size];
		for(i=0;i<size;i++){
			System.out.print("\n Enter data into the array: ");
			data[i] =  in.nextInt();
        }

        for(i=1;i<size;i++){
        	j=i;
        	while(j>0 && data[j-1] > data[j]){
        		temp = data[j-1];
        		data[j-1] = data[j];
        		data[j] = temp;
        		j--;
        	}
        }

        System.out.println("\n\tSorted data is:\n");
        for(i=0;i<size;i++){
        	System.out.print("\t"+data[i]);
        }
	}
}

Output:
insertion

Download the source code

Posted in Java | Tagged , , , , , , , , , , , , , , , , , , , , | 1 Comment

Java program for Bubble Sort

Sorting of data can be integral part of processing the given input to produce required output. Sorting may be required to remove data objects which are far from the mean of the entire data. Currently there are many sorting techniuqes, those are used according to the size of the data and the purpose of sorting. The basic of all sorting techniques is Bubble sort.

How it works: Instead of searching entire array, it compares only the adjacent data elements. It continues it’s searching till the last of the array and after reaching end of the array, it searches for the next largest number in the array and this process continues for n times where n is the size of the array.

import java.util.*;
import java.io.*;

public class bubble {
	public static void main(String args[]){

		int i,j,swap;
		Scanner in = new Scanner(System.in);
		System.out.println("\nEnter the size of the data to be sorted:");
		int size = in.nextInt();

		//Input from User
		int[] data = new int[size];
		for(i=0;i<size;i++){
			System.out.println("\nEnter " + (i+1) +" data value:");
			data[i] = in.nextInt();
		}

		//Request for choice
		System.out.println("\n\t1.Ascending order\n\n\t2.Descending order");
		System.out.println("\nEnter your choice from the above menu:");
		int choice = in.nextInt();

		
		if(choice == 1){
			/*Ascending order*/
			for(i=0;i<size;i++){
				for(j=0;j<size-1;j++){
					if(data[j] > data[j+1]){
						swap      = data[j];
          				data[j]   = data[j+1];
          				data[j+1] = swap;
					}
				}
			}
		}

		else {
			/*Descending order*/
			for(i=0;i<size;i++){
				for(j=0;j<size-1;j++){
					if(data[j] < data[j+1]){
						swap      = data[j];
          				data[j]   = data[j+1];
          				data[j+1] = swap;
					}
				}
			}
		}

		//Display the sorted data to user
		if(choice == 1){
			System.out.println("\nData in ascending order is\n");
			for(i=0;i<size;i++)
				System.out.print("\t" + data[i]);
		}
		else if(choice == 2){
			System.out.println("\nData in descending order is\n");
			for(i=0;i<size;i++)
				System.out.print("\t" + data[i]);
		}
		else 
			System.out.print("Wrong choice");
	}
}

Output:
bubble

Download Source Code

Posted in Java | Tagged , , , , , , , , , , , , , | 2 Comments

Binary search program in Java

Binary search is the step in searching techniques. Because of the draw backs of linear search, binary search came into light. The major difference between Linear and Binary search is, in linear search we need not to sort the given array. But for binary search to be done, we need to sort the array either in ascending or descending order.

Procedure for binary search:

1. Get the input array from the user.
2. Sort the array either in ascending or descending order.
3. Now, for searching, first compare the middle term of the array with the search element.
4. If the element matches the middle term, display output.
5. If the middle term doesn’t match and if middle term is greater than searching element, then from next iteration consider only the first half of the array.
6. If the middle term is lesser, then consider second half of the given array.
7. After considering the half of the array, goto step 3.

import java.util.*;
import java.io.*;

public class binarysearch{
	public static void main(String args[]){
		
		int temp, first, last, middle,i;
		Scanner in = new Scanner(System.in);
		System.out.println("Enter size of the integer array:");
		int size = in.nextInt();
		int[] data = new int[size];
		for(i=0; i<size; i++){
			System.out.println("Enter next element of the array:");
			data[i] = in.nextInt();
		}
		
                //bubble sort in ascending order
		for(i=0; i<size; i++) {
			for(int j=0; j<i; j++){
				if(data[i] < data[j]){
					temp = data[j];
					data[j] = data[i];
					data[i] = temp;
				}
			}			
		}

		System.out.println("\nEnter the element to be searched:");
		int key = in.nextInt();
		first = 0;
		last = size-1;
		while(first <= last){
			middle = (first+last)/2;
			if(data[middle] == key){
				System.out.println("Key element found");
				break;
			}
			else if(data[middle] > key)
				last = middle-1;
			else if(data[middle] < key)
				first = middle+1;
		}
		if(first > last)
			System.out.println("Element not found");
	}
}

Output:
binarysearch

Download the source code

Posted in Java | Tagged , , , , , , | Leave a comment

Linear search program in Java

Linear search is one of the basic searching techniques used in programming. There are many other advanced techniques for searching, but to learn about searching we shoudl start with linear search. This technique is simple to learn, among all the given integers, we should match our search element and if found we shall display appropriate message.

Starting from the first element of the array we need to check each and every element with the search key element. If element does not match, it moves to the next element and checks it.

import java.util.*;
import java.io.*;

public class linearsearch{
		public static void main(String args[]){

			Scanner in = new Scanner(System.in);
			int counter;
			System.out.println("\nEnter the size of the array:");
			int size = in.nextInt();
			float[] data = new float[size];
			for(int i=0;i<size;i++){
				System.out.println("\nEnter element into the array:");
				data[i] = in.nextFloat();
			}
			System.out.println("\nEnter element you need to search:");
			float key = in.nextFloat();
			counter = 0;
			for(int i=0;i<size;i++){
				if(data[i] == key){
						System.out.println("\nKey element" + key +"is in the given array");
						System.exit(0);
				}
				counter++; //Incremented to check for element found or not.
			}
			if(counter == size )
					System.out.println("\nElement not found");
		}
}

Output:
linearsearch

Download the source code

Posted in Java | Tagged , , , , , , , , , | Leave a comment

Java Program for Calculator

In this tutorial we shall learn to create a Java powered calcultor. Just with the basic knowledge of control structures in Java, we can easily design a calculator in Java. All we need to know about using, If statement, While loop, input statement.

import java.io.*;
import java.util.*;

public class calc{
	public static void main(String args[]){
		
		Scanner in = new Scanner(System.in);
		while(true){
			System.out.println("\n\t\t1.Addition\n\t\t2.Subtraction\n\t\t3.Multiplication\n\t\t4.Division\n\t\t5.Remainder\n\t\t6.Exit");
			System.out.println("\nEnter your choice from above menu:");
			int choice = in.nextInt();
			if(choice == 6){
					System.exit(0);
			}
			System.out.println("\nEnter value 1:");
			float num1 = in.nextInt();
			System.out.println("\nEnter value 2:");
			float num2 = in. nextInt();
			float output;
			switch(choice){
				case 1: output = num1 + num2;
					System.out.println("\nAddition of above two numbers is:" + output);
					break;
				case 2: output = num1 - num2;
					System.out.println("\nSubtraction of above two numbers is:" + output);
					break;
				case 3: output = num1 * num2;
					System.out.println("\nMultiplication of above two numbers is:" + output);
					break;
				case 4: output = num1 / num2;
					System.out.println("\nDivision of above two numbers is:" + output);
					break;
				case 5: output = num1 % num2;
					System.out.println("\nRemainder for division of above two numbers is:" + output);
					break;
				}
		}
  }
}

In the above program we ask the user, what type of operation they need to perform. After getting the choice of opertaion, we need to get the input of operand 1 and operand 2. Depeding on the choice of the user switch case is executed and required operation is done and obtained output is shown to the user.
Output:
calc

Download the source code

Posted in Java | Tagged , , , , , , , | Leave a comment

Python Program to Find Factors of Numbers

I’m writing this post after a longggg gap of about 9th months. Today, we shall learn how to write a python program to find factors of given number. For this, we need to take  a number as input to the program. The input() function is used to get the number as a scanf()  statement which we use in C language.Since we are using input() function the input will be treated as string. Therefore, by using int() function we shall convert the string to int datatype.

int(input("Enter a number:"))

Now, we shall create a function and then try to find the factors of the given number. For, defining a function we need to use the keyword def and then write the name of the defining function and end the line with :. And then we can continue writing body of our function

def finding(var) :

Finding factors of a given number is easy. From 1 to n+1 we need to check which number divides the given number with zero remainder. For finding the remainder we use % operator.

# definig the function.
def finding(x):
	for i in range(1, x+1):
		if x % i == 0:
			print(i);
#Input from the user

num = int(input("\nEnter a number:"))
print("\nFactors of given number are:")
finding(num)

OUTPUT:
factors

Click here to download the source code.

Posted in Python | Tagged , , , , , | Leave a comment

Python program to generate Multiplication table

In this tutorial we shall learn about generating multiplication tables.For this program we are taking twoo integer values as input’s.One for which table to be printed and the other for limiting the table….For generating the table we need to consider a for loop.In “for” loop we use the range function to to limit the for loop.

n = int(input("\n	Enter the number to find the table:"))
limit = int(input("\n	Enter limit upto which you need the table:")) 
i = 1
for i in range(1,(limit+1)) :
	print("\n\t\t" + str(n) + "*" + str(i)+"="+str((n*i)))

Explanation:In the above program,first we are asking the user to enter the table he wants and then the limit upto which he needs the table.While taking the input we are converting it to int because the default data type for input function is string.And then in the for loop we are using the range function and giving range as limit+1.
Output:
tables

Download the source code

Posted in Python | Tagged , , , , , , , , , , | 1 Comment

Java Applet program to display the Button

In this tutorial we shall learn about buttons in applet and handling those buttons.As a simple task we shall make a program “which show the users the button which he has clicked”.For this we need button in applet.The declaration of button in applet is as follows:

Button click = new Button("Click me");

Each button has it’s role,so we need to define the role played by the button.Here we have given the button the label “click me”.Therefore a button appears with “click me” text inside it.After declaration of the button we need to add the button to the applet window.For this we use the function add() which is invoked by the object of the element.Here the element is button and the object declared is click.Hence to add the element we use “click.add(this);”.

Every action performed in the applet is heard by the actionListener method.So to listen the action performed by the button we need to add the actionListener using addActionListener(),this is invoked by the object of the respective element.

After clicking the button the control is passed to the actionPerformed() method which takes object of the ActionEvent class as a parameter.There we use the method getActionCommand() to get the text which is assigned to that button during declaration and stores it in a global string. TO display the button which is clicked we are going to use the textfield in applet and we shall set the text of the TextField to the global string.Declaration of TextField and Label is as follows

Label lb = new Label("Selected Button is");
TextField tf = new TextField(20); // size of the textfield

The program is:

import java.awt.*;
import java.awt.event.*;
import java.applet.*;
/*
<applet code = "Button_selected_displayed.class" width = 500 height = 500>
</applet>
*/
public class Button_selected_displayed extends Applet implements ActionListener
{
   String str="";
   Button b1,b2,b3;
   Label lb;
   TextField tf;
  
   public void init()
   {
	b1 = new Button("Hello world");
	b2 = new Button("Hello java");
	b3 = new Button("Exit this world");
	b1.addActionListener(this);
	b2.addActionListener(this);
	b3.addActionListener(this);
	add(b1);
	add(b2);
	add(b3);
                  lb = new Label("Selected Button  is:");
                  add(lb);
                  tf = new TextField(25);
                  add(tf);
                   
    }
public void actionPerformed(ActionEvent ob)
{
   str = ob.getActionCommand();
   tf.setText(str);
}
public void paint(Graphics g)
 {

  }
}

Output
selected_button_display

selecte_button_display_2

Download the source code

Posted in Java | Tagged , , , , , , , , , , | Leave a comment

Java Applet Background color

In our earlier post we have seen Introduction to applet in Java.In today’s post we shall learn about changing the background of the applet when a particular button in selected.

To make this program we need to learn about buttons and action listener in applets. To add a button to a applet we need to declare a button using button class in the applet package.After declaring we need to add that button the applet window.For this we use add() function.Just adding of the button to the applet window doesn’t make it function,we need to add action listener’s to each button to make it work.It is done by addActionListener() method.

Button color;                  //Declaration of button
color = new Button("Red");    //Initialization of button
add(color);                  //Adding button to the window applet
color.addActionListener(this);//Adding action Listener to the button

All the above work should be done in init() function of the applet class.Now that the button is added to the applet window.Now we need to handle the action of the button when button is clicked. For this we use a function actionPerformed(ActionEvent) to perform respective action on the window applet.

public void actionPerformed(ActionEvent ae)
{
      //body of the function
}

In the actionPerformed() function we try to find which button is clicked by the user and the corresponding value of the button.For this we use getActionCommand() function which is present in ActionEvent class.Then the control is passed to the paint method to change the background color.

In paint method we use setBackground() method to set the background which takes color class constants as parameters.Entire program is as follows….

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
/*
<applet code="colordemo" height=300 width=300>
</applet>
*/
public class colordemo extends Applet implements ActionListener
	{
		Button bcolor1,bcolor2,bcolor3,bcolor4;
		Label bcolor;
		String str;
		public void init()
		{
			bcolor = new Label("Select any of the following button to change the background colour");
			bcolor1 = new Button("Red");    //Declaring buttons
			bcolor2 = new Button("Blue");
			bcolor3 = new Button("Yellow");
			bcolor4 = new Button("Black");
			
			add(bcolor1);                  //Adding buttons to the applet window
			add(bcolor2);
			add(bcolor3);
			add(bcolor4);

			bcolor1.addActionListener(this); //Adding action listener to the button
			bcolor2.addActionListener(this);
			bcolor3.addActionListener(this);
			bcolor4.addActionListener(this);
		}
		public void actionPerformed(ActionEvent ae)
		{
			str = ae.getActionCommand();
			repaint();	   	
		}
		public void paint(Graphics g)
		 {
			if(str.equals("Red"))
				setBackground(Color.red);
			else if(str.equals("Blue"))
				setBackground(Color.blue);
			else if(str.equals("Yellow"))
				setBackground(Color.yellow);
			else if(str.equals("Black"))
				setBackground(Color.black);
		}
		
	}	

Explanation:In the above program I defined four buttons for red,blue,yellow,black and changed the background color according to it.
Output:
applet_bck_grnd_change_1

applet_bck_grnd_change_2

applet_bck_grnd_change_3

Download the source code

Posted in Java | Tagged , , , , , , , | Leave a comment

Prime number program in Python

In this post we shall learn about finding prime number program in python.If a number is only divisible by 1 and itself then that number is called as prime number.Otherwise it is not a prime number.

The following program is for finding prime number

n = int(input("\n		Enter number to find whether it is prime or not:"))
flag = 0
i = 0
for i in range(2,n-1) :
	if((n%i) == 0) :
		flag = flag +1
		break
if(flag == 0) :
	print("\n\t\tGiven number " + str(n)+" is a prime number");
else :
	print("\n\t\tGiven number " + str(n) +" is not a prime number" );

Output:
prime number

Download the Source Code

Posted in Python | Tagged , , , , , , , , , , , , , , , , , , | Leave a comment