Sunday 16 October 2016

Using Divide and Conquer Strategies design a function for Binary Search using java

For binary search, the array should be arranged in ascending or descending order. Binary search relies on divide and conquer strategy in a sorted list.

Program logic: Take elements in an array called n[]. Then apply bubble sorting algorithm on it. After that a search value has taken. The desired elements is compared with the middle most elements of the array. If the search element is smaller to the middle most elements then process is repeated with the first half of the array. If the search element is greater to the middle most elements then process is repeated with the second half of the array. If the search element is equal to the middle most elements search is completed and position is return in ‘pos’  variable.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

import java.io.*;

public class BinarySearch {

    public static void main(String args[]) throws IOException {
        int n[] = new int[10];
        int i, s, f = 0, t, j;
        int low, high, mid, pos;
        InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(in);
        System.out.println("Enter elements in array:");
        for (i = 0; i < 10; i++) {
            n[i] = Integer.parseInt(br.readLine());
        }
        System.out.println("Enter element to Search:");
        s = Integer.parseInt(br.readLine());
        // Sorting of array
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9 - i; j++) {
                if (n[j] > n[j + 1]) {
                    t = n[j];
                    n[j] = n[j + 1];
                    n[j + 1] = t;
                }
            }
        }
        System.out.println("Sorted array:");
        for (i = 0; i < 10; i++) {
            System.out.print(n[i] + " ");
        }
        // Binary Search
        high = 10;
        low = 0;
        pos = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            if (s < n[mid]) {
                high = mid - 1;
            } else if (s > n[mid]) {
                low = mid + 1;
            } else if (s == n[mid]) {
                pos = mid + 1;
                break;
            }
        }
        System.out.println("\n Search result");
        System.out.println(s + " is located at position " + pos);
    }
}

Sample Output
Enter elements in array:
5
7
8
4
5
6
9
1
2
3
Enter element to Search:
4
Sorted array:
1 2 3 4 5 5 6 7 8 9
Search result
4 is located at position 4
SN
Variables
Type
Description
1.
main()
Function
This is the main entry point of the program
2.
n[]
int
To store the values in an array
3.
i , j
int
For running the loop
4.
s
int
To store the input (element to be searched)
5.
t
int
For temporarily storing a value
6.
low
int
To store the value in the lowest position
7.
mid
int
To store the value in the middle position
8.
high
int
To store the value in the highest position
9.
pos
int
To store the position of the value which was searched(only if exists)
10.
in
InputStreamReader
To instantiate the InputStreamReader class which exists in java.iopackage
11.
br
BufferedReader
To instantiate the BufferedReader class which exists in java.iopackage using the above variable as passing parameter
Analysis of binary search:
In this algorithm every time we are reducing the search area. So number of comparisons keep on decreasing. In worst case the number of comparison is most log ( N + 1 ). So it is an efficient algorithm when compared to linear search.
  

Using Divide and Conquer Strategies design a function for Binary Search using Scala-2

object BinarySearch
{
def binarySearchRecursive(list: Array[Int], target: Int)
(start: Int=0, end: Int=list.length-1): Int = {
if (start>end) return -1
val mid = start + (end-start+1)/2
if (list(mid)==target)
return mid
else if (list(mid)>target)
return binarySearchRecursive(list, target)(start, mid-1)
else
return binarySearchRecursive(list, target)(mid+1, end)
}
def main(args: Array[String]) {
println(“Enter Array Elements: “)
val l = readLine.split(” “).map(_.toInt)
println(“\nEnter the element to be Searched”)
val s : Int = readLine.toInt
val st: Int = binarySearchRecursive(l,s)()
if(st!= -1)
println(“Element found at position:”+st);
else println(“Sorry Element not Found”);
}
}
========================OUTPUT=======================
ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$ scalac BinarySearch.scala
ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$ scala BinarySearch
Enter Array Elements:
10 20 30 40
Enter the element to be Searched
20
Element found at position:1
ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$ scala BinarySearch
Enter Array Elements:
10 20 30 40
Enter the element to be Searched
50
Sorry Element not Found
ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$


Using Divide and Conquer Strategies design a function for Binary Search using Scala-1


PROGRAM

file name: a1.scala


import scala.util.control._


object a1

{
def main(args: Array[String])
{
 var n=0
 println("Enter size of array:")
 n=Console.readInt()
 var arr=new Array[Int](n)
 var ch=1
 println("Enter array elements:")
 for(i <- 0 to n-1)
 arr(i)=Console.readInt()
 var temp=0
 for(i <- 0 to n-1)
 {
  for(j <- i+1 to n-1)
  {
   if(arr(i)>arr(j))
   {
    temp=arr(i)
    arr(i)=arr(j)
    arr(j)=temp
   }
  } 
 }
 while(ch!=0)
 {
  var flag=binary(arr,n)
  if(flag== -1)
    println("Number not found")
  else
   println("Number found at index: "+flag)
  println("1. to continue  0. to exit")
  ch=Console.readInt()
 }
}

def binary(arr:Array[Int],n:Int):Int=

{
 println("Sorted array is:")
  for(i <- arr)
 println(i)
 println("Enter number to search")
 var s=Console.readInt()
 var loop= new Breaks;
 var result= -1
 var lb=0
var ub=n-1
var mid=(lb+ub)/2
loop.breakable

while(lb<=ub)
 {
mid=(lb+ub)/2
 if(s<arr(mid)) 
  ub=mid-1
 else if(s>arr(mid))
  lb=mid+1
 else
  {
   result=mid
   loop.break;
  }
 }
}
return result;
}


}



OUTPUT


ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$ scalac a1.scala

warning: there were four deprecation warnings; re-run with -deprecation for details
one warning found
ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$ scala a1
Enter size of array:
4
Enter array elements:
1
2
4
3
Sorted array is:
1
2
3
4
Enter number to search
3
Number found at index: 2
1. to continue  0. to exit
0


Code optimization using DAG using python



filename: b4.py


from sys import argv


mp = {}

list_statement = []
replace = {}
not_used = []

class ExternalNode():

    variable_identifier = ''
    def __init__(self, identifier):
        self.variable_identifier = identifier

class InternalNode():

    variable_identifier = ''
    operator_value = ''
    lchild = None
    rchild = None
    def __init__(self, val, l, r, id):
        self.operator_value = val
        self.lchild = l
        self.rchild = r
        self.variable_identifier = id

def read_input(file_name):

    file_var = open(file_name, 'r').read().strip().split("\n")
    for line in file_var:
        if len(line)>=6 and line[:6] == "return":
            break
        line = line.split(":=")
        value = line[0].strip()
        line [1] = line[1].strip().split(" ")
        first = line[1][0]
        operator = line[1][1]
        second = line[1][2]
        if (operator == '=') or (not first in mp):
            temp_var = ExternalNode(first)
            mp[first] = temp_var
            replace[first] = first
        if not second in mp:
            temp_var = ExternalNode(second)
            mp[second] = temp_var
            replace[second] = second

        list_statement.append(value)

        var = InternalNode(operator, mp[first], mp[second], value)
        mp[value] = var
        replace[value] = value

def print_code():

    for st in list_statement:
        if not st in not_used:
            print mp[st].variable_identifier + " = " + replace[mp[st].lchild.variable_identifier] + " " + mp[st].operator_value + " " + replace[mp[st].rchild.variable_identifier]

def optimise():

    for i in range(len(list_statement)):
        for j in range(i, len(list_statement)):
            st = list_statement[i]
            st2 = list_statement[j]
            if mp[st].lchild == mp[st2].lchild and mp[st].rchild == mp[st2].rchild and mp[st].operator_value == mp[st2].operator_value:
                replace[st2] = replace[st]
                if st2 != st:
                    not_used.append(st2)

if __name__ == "__main__":

    file_name = "intermediate_code"
    if len(argv) == 2:
        file_name = argv[1]
    read_input(file_name)
    optimise()
    print_code()

filename: intermediate_code


t1 := a + b

t2 := c * t1
t3 := a + b
t4 := d * t3
t5 := t2 + t4
t6 := r = t5
t7 := t3 + a
t0 := a = t4
t8 := a + b
t9 := a + b
t10 := t9 + a
t11 := a = l
t12 := a + b
t13 := a + b
t14 := j + t13


OUTPUT


ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$python b4.py

t1 = a + b
t2 = c * t1
t4 = d * t1
t5 = t2 + t4
t6 = r = t5
t7 = t1 + a
t0 = a = t4
t8 = a + b
t10 = t8 + a
t11 = a = l
t12 = a + b
t14 = j + t12


Implementation of K-NN approach take suitable example using python



filename: b13.py

import csv

from math import sqrt
import random
from collections import Counter
from operator import itemgetter

dataset = []

training = []
test = []

def loaddata():

 with open('iris.data','rb') as csvfile:
  lines = csv.reader(csvfile)
  dataset = list(lines)
  random.shuffle(dataset)
  for x in range(15):
   training.append(dataset[x])
  for x in range(15,20):
   test.append(dataset[x])

def calculate():

 for x in test:
  distances = []
  abc = []
  for y in training:
   d = pow(int(x[0])-int(y[0]),2)
   distances.append([sqrt(d),y])
  sorteddistance = sorted(distances,key=itemgetter(0))
  topk = sorteddistance[:3]
  for (a,b) in topk:
   abc.append(b)
  classes = Counter(t for(p,t) in abc)
  print "Class for"+str(x)+':'+ max(classes, key=lambda cls:classes[cls])

def main():

 loaddata()
 calculate()

main()


filename: iris.data


10,A

20,A
30,A
40,A
50,A
60,B
70,B
80,B
90,B
100,B
110,C
120,C
130,C
140,C
150,c
22,A
62,B
92,B
11,A
124,C

OUTPUT


ccpvg@ccpvg-HP-Compaq-4000-Pro-SFF-PC:~$python B13.py

Class for['40', 'A']:A
Class for['60', 'B']:B
Class for['92', 'B']:B
Class for['124', 'C']:C
Class for['90', 'B']:B