Design And Analysis Of Algorithms(DAA)

Assignment-1: Using Divide and Conquer Strategies design a function for Binary Search using C++/Java/Python/Scala.(Binary Search)

C++

#include <iostream>

using namespace std;

int binarySearch(int arr[], int lower, int upper, int key)

{

if (upper >= lower)

{

int mid = lower + (upper - lower)/2;

if (arr[mid] == key)

return mid;

if (arr[mid] > key)

return binarySearch(arr, lower, mid-1, key);

else

return binarySearch(arr, mid+1, upper, key);

}

return 1;

}

int main(void)

{

int i,j,key,size;

cout<<"\n Enter size of Array :";

cin>>size;

int arr[size];

cout<<"\n Enter "<<size<<" Elements in Array :";

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

{

cin>>arr[i];

}

cout<<"\n After Sorting Array :";

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

{

for(j=0;j<size-i-1;j++)

{

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

{

arr[j]=arr[j]+arr[j+1];

arr[j+1]=arr[j]-arr[j+1];

arr[j]=arr[j]-arr[j+1];

}

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

{

cout<<arr[i]<<" ";

}

cout<<"\n Enter key to be search ???";

cin>>key;

int result = binarySearch(arr, 0, size-1, key);

if(result == 1)

cout<<"\n Element is not present in array \n";

else

cout<<"\n Element is present at index " <<result<<"\n\n";

return 0;

}

Java

import java.util.Arrays;

import java.util.Scanner;

public class BinSearch {

Scanner ip=new Scanner(System.in);

public int binsearch(int a[],int key,int low,int high)

{

return (low<high)?search(a,key,low,high):-1;

}

int search(int a[],int key,int low,int high)

{

int mid=(low+high)/2;

return (key==a[mid])? mid:binsearch(a,key,(key>a[mid])? mid+1:low,(key<a[mid])? mid:high);

}

public static void main(String[] args)

{

int a[]={1,3,2,6,4,7,8,4};

Arrays.sort(a);

BinSearch b=new BinSearch();

System.out.println("Enter the element to be searched:");

Scanner i=new Scanner(System.in);

int key=i.nextInt();

int f=b.binsearch(a,key,0,a.length);

System.out.println(f==-1?"Element is not present":"The element is present at position :"+f);

}

/******************OUTPUT********************

Enter the element to be searched:

Element is not present

..............................................

Enter the element to be searched:

The element is present at position :5

Assignment-2: Using Divide and Conquer Strategies design a class for Concurrent Quick Sort using C++. (Quick Sort)

#include<iostream>

#include<omp.h>

using namespace std;

void quicksort(int [], int, int);

int createPartition(int [], int, int);

int main() {

int n;

pthread_t thread;

cout<<"Enter the size of the array = ";

cin>>n;

int elements[n];

cout<<"Enter the elements in the array = "<<endl;

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

cin>>elements[i];

}

int begin = 1, end = n;

quicksort(elements, begin, end);

string delimator = ", ";

cout<<"Quick Sort:"<<endl;

cout<<"[";

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

if (i == n)

delimator = "";

cout<<elements[i]<<delimator;

}

cout<<"]"<<endl;

return 0;

}

void quicksort(int elements[], int begin, int end) {

int middle;

if(begin < end) {

middle = createPartition(elements, begin, end);

#pragma omp parallel sections num_threads(2)

{

#pragma omp section

quicksort(elements, begin, middle - 1);

#pragma omp section

quicksort(elements, middle + 1, end);

}

int createPartition(int elements[], int begin, int end) {

int temp, temp1;

int x = elements[end];

int i = begin - 1;

for(int j = begin; j<= end - 1; j++) {

if(elements[j] <= x) {

i = i+1;

temp = elements[i];

elements[i] = elements[j];

elements[j] = temp;

}

temp1 = elements[i + 1];

elements[i + 1] = elements[end];

elements[end] = temp1;

return i + 1;

}

/******************OUTPUT********************

student@CC:~/Downloads$ make Quick

g++ Quick.cpp -o Quick

student@CC:~/Downloads$ ./Quick

Enter the size of the array = 4

Enter the elements in the array =

Quick Sort:

[1, 2, 3, 4]

student@CC:~/Downloads$

**/

Assignment-3: 8-Queens Matrix is Stored using JSON/XML having ﬁrst Queen placed, use back-tracking to place remaining Queens to generate ﬁnal 8-queen’s Matrix using Python. (8 Queens)

def displayBoard(mat, n):

print ("\n")

for i in range(0,n):

for j in range(0,n):

print (mat[i][j])

print("\n")

def isSafe(mat,n,row,col):

#check LHS of this row

i =0

while i <=col:

if mat[row][i] == 1:

return False

i+=1

#check upper diagonal

i =row

j = col

while i>=0 and j >=0:

if mat[i][j] == 1:

return False

i-=1

j-=1

#check lower diagonal

i= row

j = col

while i < n and j >=0:

if mat[i][j] == 1:

return False

i+=1

j-=1

#otherwise

return True

def solve(mat,n, col):

if col >= n: #base case to stop recursion

return True;

for i in range(0,n): #consider col and try placing the queen in all rows

if isSafe(mat,n, i, col):

mat[i][col] = 1 #place the queen at mat[i][col]

if solve(mat, n, col+1) == True: #recur to place rest of the queens

return True

mat[i][col] = 0 #backtrack

#queen cannot be placed in any row corresponding to this col

return False;

def main(n):

mat=[ [0 for i in range(n)] for j in range(n)]

if solve(mat, n, 0) == False:

print("SOLUTION DOESNT EXIST")

else:

displayBoard(mat,n)

if __name__ == "__main__":

main(8)

****************OUTPUT*************************

pccoe@pccoe-ThinkCentre-M60e:~$ python 8queens.py

[(1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4)]

[(1, 1), (2, 6), (3, 8), (4, 3), (5, 7), (6, 4), (7, 2), (8, 5)]

[(1, 1), (2, 7), (3, 4), (4, 6), (5, 8), (6, 2), (7, 5), (8, 3)]

[(1, 1), (2, 7), (3, 5), (4, 8), (5, 2), (6, 4), (7, 6), (8, 3)]

[(1, 2), (2, 4), (3, 6), (4, 8), (5, 3), (6, 1), (7, 7), (8, 5)]

[(1, 2), (2, 5), (3, 7), (4, 1), (5, 3), (6, 8), (7, 6), (8, 4)]

[(1, 2), (2, 5), (3, 7), (4, 4), (5, 1), (6, 8), (7, 6), (8, 3)]

[(1, 2), (2, 6), (3, 1), (4, 7), (5, 4), (6, 8), (7, 3), (8, 5)]

[(1, 2), (2, 6), (3, 8), (4, 3), (5, 1), (6, 4), (7, 7), (8, 5)]

[(1, 2), (2, 7), (3, 3), (4, 6), (5, 8), (6, 5), (7, 1), (8, 4)]

[(1, 2), (2, 7), (3, 5), (4, 8), (5, 1), (6, 4), (7, 6), (8, 3)]

[(1, 2), (2, 8), (3, 6), (4, 1), (5, 3), (6, 5), (7, 7), (8, 4)]

[(1, 3), (2, 1), (3, 7), (4, 5), (5, 8), (6, 2), (7, 4), (8, 6)]

[(1, 3), (2, 5), (3, 2), (4, 8), (5, 1), (6, 7), (7, 4), (8, 6)]

[(1, 3), (2, 5), (3, 2), (4, 8), (5, 6), (6, 4), (7, 7), (8, 1)]

[(1, 3), (2, 5), (3, 7), (4, 1), (5, 4), (6, 2), (7, 8), (8, 6)]

[(1, 3), (2, 5), (3, 8), (4, 4), (5, 1), (6, 7), (7, 2), (8, 6)]

[(1, 3), (2, 6), (3, 2), (4, 5), (5, 8), (6, 1), (7, 7), (8, 4)]

[(1, 3), (2, 6), (3, 2), (4, 7), (5, 1), (6, 4), (7, 8), (8, 5)]

[(1, 3), (2, 6), (3, 2), (4, 7), (5, 5), (6, 1), (7, 8), (8, 4)]

[(1, 3), (2, 6), (3, 4), (4, 1), (5, 8), (6, 5), (7, 7), (8, 2)]

[(1, 3), (2, 6), (3, 4), (4, 2), (5, 8), (6, 5), (7, 7), (8, 1)]

[(1, 3), (2, 6), (3, 8), (4, 1), (5, 4), (6, 7), (7, 5), (8, 2)]

[(1, 3), (2, 6), (3, 8), (4, 1), (5, 5), (6, 7), (7, 2), (8, 4)]

[(1, 3), (2, 6), (3, 8), (4, 2), (5, 4), (6, 1), (7, 7), (8, 5)]

[(1, 3), (2, 7), (3, 2), (4, 8), (5, 5), (6, 1), (7, 4), (8, 6)]

[(1, 3), (2, 7), (3, 2), (4, 8), (5, 6), (6, 4), (7, 1), (8, 5)]

[(1, 3), (2, 8), (3, 4), (4, 7), (5, 1), (6, 6), (7, 2), (8, 5)]

[(1, 4), (2, 1), (3, 5), (4, 8), (5, 2), (6, 7), (7, 3), (8, 6)]

[(1, 4), (2, 1), (3, 5), (4, 8), (5, 6), (6, 3), (7, 7), (8, 2)]

[(1, 4), (2, 2), (3, 5), (4, 8), (5, 6), (6, 1), (7, 3), (8, 7)]

[(1, 4), (2, 2), (3, 7), (4, 3), (5, 6), (6, 8), (7, 1), (8, 5)]

[(1, 4), (2, 2), (3, 7), (4, 3), (5, 6), (6, 8), (7, 5), (8, 1)]

[(1, 4), (2, 2), (3, 7), (4, 5), (5, 1), (6, 8), (7, 6), (8, 3)]

[(1, 4), (2, 2), (3, 8), (4, 5), (5, 7), (6, 1), (7, 3), (8, 6)]

[(1, 4), (2, 2), (3, 8), (4, 6), (5, 1), (6, 3), (7, 5), (8, 7)]

[(1, 4), (2, 6), (3, 1), (4, 5), (5, 2), (6, 8), (7, 3), (8, 7)]

[(1, 4), (2, 6), (3, 8), (4, 2), (5, 7), (6, 1), (7, 3), (8, 5)]

[(1, 4), (2, 6), (3, 8), (4, 3), (5, 1), (6, 7), (7, 5), (8, 2)]

[(1, 4), (2, 7), (3, 1), (4, 8), (5, 5), (6, 2), (7, 6), (8, 3)]

[(1, 4), (2, 7), (3, 3), (4, 8), (5, 2), (6, 5), (7, 1), (8, 6)]

[(1, 4), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3), (8, 8)]

[(1, 4), (2, 7), (3, 5), (4, 3), (5, 1), (6, 6), (7, 8), (8, 2)]

[(1, 4), (2, 8), (3, 1), (4, 3), (5, 6), (6, 2), (7, 7), (8, 5)]

[(1, 4), (2, 8), (3, 1), (4, 5), (5, 7), (6, 2), (7, 6), (8, 3)]

[(1, 4), (2, 8), (3, 5), (4, 3), (5, 1), (6, 7), (7, 2), (8, 6)]

[(1, 5), (2, 1), (3, 4), (4, 6), (5, 8), (6, 2), (7, 7), (8, 3)]

[(1, 5), (2, 1), (3, 8), (4, 4), (5, 2), (6, 7), (7, 3), (8, 6)]

[(1, 5), (2, 1), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4)]

[(1, 5), (2, 2), (3, 4), (4, 6), (5, 8), (6, 3), (7, 1), (8, 7)]

[(1, 5), (2, 2), (3, 4), (4, 7), (5, 3), (6, 8), (7, 6), (8, 1)]

[(1, 5), (2, 2), (3, 6), (4, 1), (5, 7), (6, 4), (7, 8), (8, 3)]

[(1, 5), (2, 2), (3, 8), (4, 1), (5, 4), (6, 7), (7, 3), (8, 6)]

[(1, 5), (2, 3), (3, 1), (4, 6), (5, 8), (6, 2), (7, 4), (8, 7)]

[(1, 5), (2, 3), (3, 1), (4, 7), (5, 2), (6, 8), (7, 6), (8, 4)]

[(1, 5), (2, 3), (3, 8), (4, 4), (5, 7), (6, 1), (7, 6), (8, 2)]

[(1, 5), (2, 7), (3, 1), (4, 3), (5, 8), (6, 6), (7, 4), (8, 2)]

[(1, 5), (2, 7), (3, 1), (4, 4), (5, 2), (6, 8), (7, 6), (8, 3)]

[(1, 5), (2, 7), (3, 2), (4, 4), (5, 8), (6, 1), (7, 3), (8, 6)]

[(1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 4), (8, 8)]

[(1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 8), (8, 4)]

[(1, 5), (2, 7), (3, 4), (4, 1), (5, 3), (6, 8), (7, 6), (8, 2)]

[(1, 5), (2, 8), (3, 4), (4, 1), (5, 3), (6, 6), (7, 2), (8, 7)]

[(1, 5), (2, 8), (3, 4), (4, 1), (5, 7), (6, 2), (7, 6), (8, 3)]

[(1, 6), (2, 1), (3, 5), (4, 2), (5, 8), (6, 3), (7, 7), (8, 4)]

[(1, 6), (2, 2), (3, 7), (4, 1), (5, 3), (6, 5), (7, 8), (8, 4)]

[(1, 6), (2, 2), (3, 7), (4, 1), (5, 4), (6, 8), (7, 5), (8, 3)]

[(1, 6), (2, 3), (3, 1), (4, 7), (5, 5), (6, 8), (7, 2), (8, 4)]

[(1, 6), (2, 3), (3, 1), (4, 8), (5, 4), (6, 2), (7, 7), (8, 5)]

[(1, 6), (2, 3), (3, 1), (4, 8), (5, 5), (6, 2), (7, 4), (8, 7)]

[(1, 6), (2, 3), (3, 5), (4, 7), (5, 1), (6, 4), (7, 2), (8, 8)]

[(1, 6), (2, 3), (3, 5), (4, 8), (5, 1), (6, 4), (7, 2), (8, 7)]

[(1, 6), (2, 3), (3, 7), (4, 2), (5, 4), (6, 8), (7, 1), (8, 5)]

[(1, 6), (2, 3), (3, 7), (4, 2), (5, 8), (6, 5), (7, 1), (8, 4)]

[(1, 6), (2, 3), (3, 7), (4, 4), (5, 1), (6, 8), (7, 2), (8, 5)]

[(1, 6), (2, 4), (3, 1), (4, 5), (5, 8), (6, 2), (7, 7), (8, 3)]

[(1, 6), (2, 4), (3, 2), (4, 8), (5, 5), (6, 7), (7, 1), (8, 3)]

[(1, 6), (2, 4), (3, 7), (4, 1), (5, 3), (6, 5), (7, 2), (8, 8)]

[(1, 6), (2, 4), (3, 7), (4, 1), (5, 8), (6, 2), (7, 5), (8, 3)]

[(1, 6), (2, 8), (3, 2), (4, 4), (5, 1), (6, 7), (7, 5), (8, 3)]

[(1, 7), (2, 1), (3, 3), (4, 8), (5, 6), (6, 4), (7, 2), (8, 5)]

[(1, 7), (2, 2), (3, 4), (4, 1), (5, 8), (6, 5), (7, 3), (8, 6)]

[(1, 7), (2, 2), (3, 6), (4, 3), (5, 1), (6, 4), (7, 8), (8, 5)]

[(1, 7), (2, 3), (3, 1), (4, 6), (5, 8), (6, 5), (7, 2), (8, 4)]

[(1, 7), (2, 3), (3, 8), (4, 2), (5, 5), (6, 1), (7, 6), (8, 4)]

[(1, 7), (2, 4), (3, 2), (4, 5), (5, 8), (6, 1), (7, 3), (8, 6)]

[(1, 7), (2, 4), (3, 2), (4, 8), (5, 6), (6, 1), (7, 3), (8, 5)]

[(1, 7), (2, 5), (3, 3), (4, 1), (5, 6), (6, 8), (7, 2), (8, 4)]

[(1, 8), (2, 2), (3, 4), (4, 1), (5, 7), (6, 5), (7, 3), (8, 6)]

[(1, 8), (2, 2), (3, 5), (4, 3), (5, 1), (6, 7), (7, 4), (8, 6)]

[(1, 8), (2, 3), (3, 1), (4, 6), (5, 2), (6, 5), (7, 7), (8, 4)]

[(1, 8), (2, 4), (3, 1), (4, 3), (5, 6), (6, 2), (7, 7), (8, 5)]

Assignment-4: Implementation of 0-1 knapsack problem using branch and bound approach.(Knapsack)

#include <queue>

#include <iostream>

using namespace std;

struct node

{

int level;

int profit;

int weight;

int bound;

};

int bound(node u, int n, int W, vector<int> pVa, vector<int> wVa)

{

int j = 0, k = 0;

int totweight = 0;

int result = 0;

if (u.weight >= W)

{

return 0;

}

else

{

result = u.profit;

j = u.level + 1;

totweight = u.weight;

while ((j < n) && (totweight + wVa[j] <= W))

{

totweight = totweight + wVa[j];

result = result + pVa[j];

j++;

}

k = j;

if (k < n)

{

result = result + (W - totweight) * pVa[k]/wVa[k];

}

return result;

}

int knapsack(int n, int p[], int w[], int W)

{

queue<node> Q;

node u, v;

vector<int> pV;

vector<int> wV;

Q.empty();

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

{

pV.push_back(p[i]);

wV.push_back(w[i]);

}

v.level = -1;

v.profit = 0;

v.weight = 0;

int maxProfit = 0;

//v.bound = bound(v, n, W, pV, wV);

Q.push(v);

while (!Q.empty())

{

v = Q.front();

Q.pop();

if (v.level == -1)

{

u.level = 0;

}

else if (v.level != (n - 1))

{

u.level = v.level + 1;

}

u.weight = v.weight + w[u.level];

u.profit = v.profit + p[u.level];

u.bound = bound(u, n, W, pV, wV);

if (u.weight <= W && u.profit > maxProfit)

{

maxProfit = u.profit;

}

if (u.bound > maxProfit)

{

Q.push(u);

}

u.weight = v.weight;

u.profit = v.profit;

u.bound = bound(u, n, W, pV, wV);

if (u.bound > maxProfit)

{

Q.push(u);

}

return maxProfit;

}

int main()

{

int maxProfit,n,W,w[10],p[10],i;

/* int n = 4;

int W = 16;;

int w[4] = {3,5,9,5};

int p[4] = {45,30,45,10};*/

cout<<"Enter the number of nodes :";

cin>>n;

cout<<"Enter the weights:"<<endl;

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

{

cin>>w[i];

}

cout<<"Enter the profits:"<<endl;

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

{

cin>>p[i];

}

cout<<"Enter the capacity ";

cin>>W;

cout<<" The maximum profit using knapsack branch and bound is :";

cout << knapsack(n, p, w, W) << endl;

}

/******************OUTPUT********************

student@210-10:~$ g++ knap.cpp

student@210-10:~$ ./a.out

Enter the number of nodes :4

Enter the weights:

3 5 9 5

Enter the profits:

45 30 45 10

Enter the capacity 16

The maximum profit using knapsack branch and bound is :90

student@210-10:~$ */

/****************************ACP******************************/

Assignment-5: Write a java program to multiply 64-bit numbers using shared memory, java collection framework and java utilities. (MultiCollection)

Multiply 64 Bit Numbers

Using Bit Shif Logic

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class MultiCollection {

public static List<Integer> getShiftList(String number){

List<Integer> shiftList = new ArrayList<Integer>();

for(int i=0; i<number.length(); i++){

if(String.valueOf(number.charAt(i)).equals("1")){

shiftList.add(number.length()-1-i);

}

return shiftList;

}

public static Long getMultiplication(Long firstNumber,

List<Integer> secondNumber) {

Long result = 0l;

String secondNumberStr = "";

* Get shiftList as per secondNumber as it will be used to shift first number

* All shift of firstNumber Added Together to form Result

for(int i=0; i<secondNumber.size(); i++){

secondNumberStr += String.valueOf(secondNumber.get(i));

}

List<Integer> shiftList = getShiftList(secondNumberStr);

* Now Use shiftList to shift firstNumber with given shift and add all shifted

* numbers together to get result

for(int i=0; i<shiftList.size(); i++){

int shiftBy = shiftList.get(i);

result += firstNumber << shiftBy;

}

return result;

}

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);

System.out.println("Enter first 64bit Number : ");

Long numberOne = scanner.nextLong();

System.out.println("Enter second 64bit Number : ");

Integer numberTwo = scanner.nextInt();

String numberTwoBin = Integer.toBinaryString(numberTwo);

List<Integer> listTwo = new ArrayList<Integer>();

for (int i = 0; i < numberTwoBin.length(); i++) {

String temp = String.valueOf(numberTwoBin.charAt(i));

listTwo.add(Integer.parseInt(temp));

}

System.out.println();

System.out.print("Multiplication : ");

System.out.print(getMultiplication(numberOne, listTwo));

}

/******************OUTPUT********************

Enter first 64bit Number :

9223372036854

Enter second 64bit Number :

Multiplication : 18446744073708*/

Assignment-6: Write a program using Sqoop to transfer the Digital Library Book Data and related linked to multimedia/PDF to stored using MySQL to HDFS and from HDFS to MySQL. (Sqoop)

import com.cloudera.sqoop.*;

import com.cloudera.sqoop.tool.*;

public class MySqlImport {

/* CONSTANTS */

private static final String JOB_NAME = "Sqoop HDFS Job";

private static final String MAPREDUCE_JOB = "HDFS Map Reduce Job";

private static final String DBURL = "jdbc:mysql://localhost:3306/dgb";

private static final String DRIVER = "com.mysql.jdbc.Driver";

private static final String USERNAME = "root";

private static final String PASSWORD = "alliswell";

private static final String HADOOP_HOME = "/usr/local/hadoop";

private static final String JAR_OUTPUT_DIR = "/home/shailesh/compile";

private static final String TARGET_DIR = "/home/shailesh/hdfs/out";

private static final String SUCCESS = "SUCCESS !!!";

private static final String FAIL = "FAIL !!!";

/**

* Imports data from RDBMS MySQL and uploads into Hadoop file system

* @param RDBMS Table Name

public void importToHadoop(String table){

//log.info("Importing data into HDFS â€¦....");

SqoopOptions options = new SqoopOptions(DBURL,table);

options.setDriverClassName(DRIVER);

options.setUsername(USERNAME);

options.setPassword(PASSWORD);

options.setFieldsTerminatedBy('\t');

options.setHadoopMapRedHome(HADOOP_HOME);

options.setJobName(JOB_NAME);

options.setLinesTerminatedBy('\n');

options.setMapreduceJobName(MAPREDUCE_JOB);

options.setTableName(table);

options.setJarOutputDir(JAR_OUTPUT_DIR);

options.setTargetDir(TARGET_DIR + table);

ImportTool it = new ImportTool();

int retVal = it.run(options);

if(retVal == 0)

{

//log.info(SUCCESS);

}

else{

//log.info(FAIL);

}

public static void main(String[] args) {

MySqlImport t= new MySqlImport();

t.importToHadoop("book");

}

Assignment-7: Write a MapReduce program using Java/Python/Scala to arrange the data on userid, then with in the user id sort them in increasing or decreasing order of hit count of accession number demanded by students using digital library. (Hive)

import java.sql.Connection;

import java.sql.DriverManager;

import java.sql.ResultSet;

import java.sql.Statement;

import java.util.Scanner;

public class HivePrac

{

private static Connection con;

private static Statement stmt;

private static String driverName = "org.apache.hive.jdbc.HiveDriver";

private static void createConnect() throws Exception {

try

{

Class.forName(driverName);

// get connection

con = DriverManager.getConnection("jdbc:hive2://localhost:10000","","");

// create statement

stmt = con.createStatement();

} catch (Exception e) {

System.out.println(e.getMessage());

}

private static void createDatabase() throws Exception {

stmt.executeUpdate("CREATE DATABASE IF NOT EXISTS userdb1");

System.out.println("Database userdb created successfully.");

}

private static void createTable() throws Exception {

stmt.executeUpdate("CREATE TABLE IF NOT EXISTS "

+ " books ( bid int, name String, "

+ " price String, url String)"

+ " COMMENT 'Book details'" + " ROW FORMAT DELIMITED"

+ " FIELDS TERMINATED BY '\t'" + " LINES TERMINATED BY '\n'"

+ " STORED AS TEXTFILE");

System.out.println("Table books created.");

}

private static void loadData() throws Exception {

stmt.executeUpdate("LOAD DATA LOCAL INPATH '/home/cloudera/Desktop/sample.txt'"

+ "OVERWRITE INTO TABLE books");

System.out.println("Load Data into books successful");

}

private static void displayData() throws Exception {

ResultSet res = stmt

.executeQuery("SELECT * FROM books WHERE price>300");

System.out.println("Result:");

System.out.println(" ID \t Name \t Price \t URL ");

while (res.next()) {

System.out.println(res.getInt(1) + " " + res.getString(2) + " "

+ res.getString(3) + " " + res.getString(4));

}

private static void groupBy() throws Exception {

// execute statement

ResultSet res = stmt.executeQuery("SELECT name,count(*) "

+ "FROM books GROUP BY name ");

while (res.next()) {

System.out.println(res.getString(1) + " " + res.getInt(2));

}

private static void orderBy() throws Exception {

ResultSet res = stmt.executeQuery("SELECT * FROM books ORDER BY price desc");

System.out.println(" ID \t Name \t Price \t URL");

while (res.next()) {

System.out.println(res.getInt(1) + " " + res.getString(2) + " " + res.getString(3) + " " + res.getString(4) );

}

private static void closeConnection() throws Exception {

con.close();

}

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

createConnect();

Scanner scanner = new Scanner(System.in);

int option = 0;

while (option<6) {

System.out.println("Menu: \n" + "1 Create Database\n"

+ "2 Create Table\n" + "3 Load Data\n" + "4 Display Data\n"

+ "5 Group By\n" + "6 Order By\n");

option = scanner.nextInt();

switch (option) {

case 1:

createDatabase();

break;

case 2:

createTable();

break;

case 3:

loadData();

break;

case 4:

displayData();

break;

case 5:

groupBy();

break;

case 6:

orderBy();

break;

}

closeConnection();

}

}

/****************************DMTA******************************/

Apriori

import java.io.*; class ap

{

public static void main(String []arg)throws IOException

{ int i,j,m=0; int t1=0;

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

System.out.println("Enter the number of transaction :"); int n=Integer.parseInt(b.readLine());

System.out.println("items :1--Mango 2--Nuts 3--Corn 4--Apple 5--Toothbrush 6--Jar

7--Key-Chain 8-- Eggs 9-- Knife 10- Chocolates 11-- Onion");

int item[][]=new int[n][11]; for(i=0;i<n;i++) for(j=0;j<11;j++) item[i][j]=0;

String[] itemlist={"MANGO","NUTS","CORN","APPLE","TOOTHBRUSH","JAR","KEY-

CHAIN","EGGS","KNIFE","CHOCOLATES","ONION"};

int nt[]=new int[11]; int q[]=new int[11]; for(i=0;i<n;i++)

{ System.out.println("Transaction "+(i+1)+" :");

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

{ //System.out.println(itemlist[j]);

System.out.println("Is Item "+itemlist[j]+" present in this transaction(1/0)? :");

item[i][j]=Integer.parseInt(b.readLine());

}

for(j=0;j<11;j++) { for(i=0;i<n;i++)

{if(item[i][j]==1) nt[j]=nt[j]+1;

}

System.out.println("Number of Item "+itemlist[j]+" :"+nt[j]);

}

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

{ if(((nt[j]/(float)n)*100)>=50) q[j]=1; else q[j]=0;

if(q[j]==1)

{t1++;

System.out.println("Item "+itemlist[j]+" is selected ");

}

for(j=0;j<11;j++) { for(i=0;i<n;i++)

{

if(q[j]==0)

{

item[i][j]=0;

}

} }

int nt1[][]=new int[11][11]; for(j=0;j<11;j++)

{ for(m=j+1;m<11;m++)

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

{ if(item[i][j]==1 &&item[i][m]==1)

{ nt1[j][m]=nt1[j][m]+1;

}

if(nt1[j][m]!=0)

System.out.println("Number of Items of "+itemlist[j]+"& "+itemlist[m]

+" :"+nt1[j][m]);

}

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

{ for(m=j+1;m<11;m++)

{

if(((nt1[j][m]/(float)n)*100)>=50) q[j]=1; else q[j]=0;

if(q[j]==1)

{

System.out.println("Item "+itemlist[j]+"& "+itemlist[m]+" is selected ");

}

/******************OUTPUT********************

Enter the number of transaction :

items :1--Mango 2--Nuts 3--Corn 4--Apple 5--Toothbrush 6--Jar 7--Key-Chain 8-- Eggs 9-- Knife 10- Chocolates 11-- Onion Transaction 1 :

Is Item MANGO present in this transaction(1/0)? :

1 Is Item NUTS present in this transaction(1/0)? :

0 Is Item CORN present in this transaction(1/0)? :

0 Is Item APPLE present in this transaction(1/0)? :

0 Is Item TOOTHBRUSH present in this transaction(1/0)? :

0 Is Item JAR present in this transaction(1/0)? :

1 Is Item KEY-CHAIN present in this transaction(1/0)? :

1 Is Item EGGS present in this transaction(1/0)? : 1 Is Item KNIFE present in this transaction(1/0)? :

0 Is Item CHOCOLATES present in this transaction(1/0)? :

1 Is Item ONION present in this transaction(1/0)? :

1 Transaction 2 :

Is Item MANGO present in this transaction(1/0)? :

0 Is Item NUTS present in this transaction(1/0)? :

1 Is Item CORN present in this transaction(1/0)? :

0 Is Item APPLE present in this transaction(1/0)? :

0 Is Item TOOTHBRUSH present in this transaction(1/0)? :

0 Is Item JAR present in this transaction(1/0)? :

1 Is Item KEY-CHAIN present in this transaction(1/0)? :

1 Is Item EGGS present in this transaction(1/0)? :

1 Is Item KNIFE present in this transaction(1/0)? :

0 Is Item CHOCOLATES present in this transaction(1/0)? :

1 Is Item ONION present in this transaction(1/0)? :

1 Transaction 3 :

Is Item MANGO present in this transaction(1/0)? :

1 Is Item NUTS present in this transaction(1/0)? :

0 Is Item CORN present in this transaction(1/0)? :

0 Is Item APPLE present in this transaction(1/0)? :

1 Is Item TOOTHBRUSH present in this transaction(1/0)? :

0 Is Item JAR present in this transaction(1/0)? :

0 Is Item KEY-CHAIN present in this transaction(1/0)? :

1 Is Item EGGS present in this transaction(1/0)? :

1 Is Item KNIFE present in this transaction(1/0)? :

0 Is Item CHOCOLATES present in this transaction(1/0)? :

0 Is Item ONION present in this transaction(1/0)? :

0 Transaction 4 :

Is Item MANGO present in this transaction(1/0)? :

1 Is Item NUTS present in this transaction(1/0)? :

0 Is Item CORN present in this transaction(1/0)? : 1 Is Item APPLE present in this transaction(1/0)? :

0 Is Item TOOTHBRUSH present in this transaction(1/0)? :

1 Is Item JAR present in this transaction(1/0)? :

0 Is Item KEY-CHAIN present in this transaction(1/0)? :

1 Is Item EGGS present in this transaction(1/0)? :

0 Is Item KNIFE present in this transaction(1/0)? :

0 Is Item CHOCOLATES present in this transaction(1/0)? :

1 Is Item ONION present in this transaction(1/0)? :

0 Transaction 5 :

Is Item MANGO present in this transaction(1/0)? :

0 Is Item NUTS present in this transaction(1/0)? :

0 Is Item CORN present in this transaction(1/0)? :

1 Is Item APPLE present in this transaction(1/0)? :

0 Is Item TOOTHBRUSH present in this transaction(1/0)? :

0 Is Item JAR present in this transaction(1/0)? :

0 Is Item KEY-CHAIN present in this transaction(1/0)? :

1 Is Item EGGS present in this transaction(1/0)? :

1 Is Item KNIFE present in this transaction(1/0)? :

1 Is Item CHOCOLATES present in this transaction(1/0)? :

0 Is Item ONION present in this transaction(1/0)? :

Number of Item MANGO :3

Number of Item NUTS :1

Number of Item CORN :2

Number of Item APPLE :1

Number of Item TOOTHBRUSH :1

Number of Item JAR :2

Number of Item KEY-CHAIN :5

Number of Item EGGS :4

Number of Item KNIFE :1

Number of Item CHOCOLATES :3

Number of Item ONION :3

Item MANGO is selected

Item KEY-CHAIN is selected

Item EGGS is selected

Item CHOCOLATES is selected

Item ONION is selected

Number of Items of MANGO& KEY-CHAIN :3

Number of Items of MANGO& EGGS :2

Number of Items of MANGO& CHOCOLATES :2

Number of Items of MANGO& ONION :1

Number of Items of KEY-CHAIN& EGGS :4

Number of Items of KEY-CHAIN& CHOCOLATES :3

Number of Items of KEY-CHAIN& ONION :3

Number of Items of EGGS& CHOCOLATES :2

Number of Items of EGGS& ONION :3

Number of Items of CHOCOLATES& ONION :2

Item MANGO& KEY-CHAIN is selected

Item KEY-CHAIN& EGGS is selected

Item KEY-CHAIN& CHOCOLATES is selected

Item KEY-CHAIN& ONION is selected

Item EGGS& ONION is selected

KNN

#include<iostream>

#include<math.h> using namespace std;

int main()

{

cout<<"---------------------------------------------------------";

cout<<"\n\t\t\tKnn code\n";

cout<<"---------------------------------------------------------\n"; int array[10][3];

array[0][0]=4; array[0][1]=2; array[0][2]=1;

array[1][0]=2; array[1][1]=3; array[1][2]=1;

array[2][0]=3; array[2][1]=4; array[2][2]=0;

array[3][0]=4; array[3][1]=5; array[3][2]=1;

array[4][0]=2; array[4][1]=3; array[4][2]=1;

array[5][0]=2; array[5][1]=4; array[5][2]=0;

array[6][0]=3; array[6][1]=5; array[6][2]=0;

array[7][0]=1; array[7][1]=4; array[7][2]=0;

array[8][0]=2; array[8][1]=5; array[8][2]=0;

array[9][0]=3; array[9][1]=3; array[9][2]=0;

array[10][0]=4; array[10][1]=4;

int a[10]; int b[10];

cout<<"\n#Training set :"; cout<<"\nX\tY\tOutput"; for(int i=0;i<11;i++)

{ cout<<"\n";

for(int j=0;j<3;j++)

{

cout<<array[i][j]<<"\t";

}

cout<<"\n#Unkown point :"; cout<<"\nX\tY\n"; for(int j=0;j<2;j++)

{ int i=10;

cout<<array[i][j]<<"\t";

}

cout<<"\n\n#Calculating distance from unknown point :"; cout<<"\n\nDistance\tOutput";

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

{

a[i]=sqrt(pow((array[10][0]-array[i][0]),2) + pow((array[10][1]-array[i]

[1]),2)); b[i]=array[i][2];

cout<<"\n"<<a[i]<<"\t\t"<<b[i]; }

//sorting according to distance

int temp; int temp1; for(int i=0;i<9;i++)

{

for(int j=9;i<j;j--)

{ if(a[j]<a[j-1])

{ temp=a[j]; temp1=b[j];

a[j]=a[j-1]; b[j]=b[j-1];

a[j-1]=temp; b[j-1]=temp1;

}

} }

cout<<"\n\n##sorted list : "; cout<<"\nDistance \tOutput";

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

{ cout<<"\n"<<a[i]<<"\t\t"<<b[i]; }

int k;

cout<<"\n\nenter the no of neighbours to be considered(k) = "; cin>>k;

int y=0,n=0; for(int i=0;i<k;i++)

{ if(b[i]==0)

y++; else n++;

}

if(y>n) cout<<"\nOutput = yes(0)"; else cout<<"\nOutput = no(1)"; cout<<"\n\n"; }

/******************OUTPUT********************

pccoe@ubuntu:~$ cd knn pccoe@ubuntu:~/knn$ g++ knn.cpp pccoe@ubuntu:~/knn$ ./a.out---------------------------------------------------------

Knn code

--------------------------------------------------------#Training set :

X	Y	Output
4	2	1
2	3	1
3	4	0
4	5	1
2	3	1
2	4	0
3	5	0
1	4	0
2	5	0
3	3	0
4	4	0

#Unkown point :

X Y

4 4

#Calculating distance from unknown point :

Distance Output

2 1

1 0

1 1

2 1

2 0

1 0

3 0

2 0

1 0

##sorted list :

Distance Output

1 0

1 1

1 0

2 1

2 0

3 0

enter the no of neighbours to be considered(k) = 3

Output = yes(0)

k-Means

#include<iostream> using namespace std;

int main()

{ int n,m;

int d[10][10],cluster[10][10];

int index=0; int a=0;

cout<<"---------------------------------------------------------";

cout<<"\n\t\tK-means code\n";

cout<<"---------------------------------------------------------\n";

cout<<"\nEnter no of elements = "; cin>>n; int array[n];

cout<<"\nEnter "<<n<<" elements :\n";

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

{ cin>>array[i]; }

cout<<"\nEnter no of clusters = "; cin>>m;

int mean[m]; int newmean[m];

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

{ cout<<"Enter cluster mean "<<i+1<<" = "; cin>>mean[i];

}

int b[m][n]; int c[n];

do{ cout<<"\nCalculating distance : \n";

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

{ cout<<"\n\n";

int z=10;

for(int j=0;j<m;j++)

{ cout<<"dist of "<<array[i]<<" from cluster "<<j+1<<" = "; d[i][j]=array[i]-mean[j];

if(d[i][j]<0)

d[i][j]=-d[i][j];

cout<<d[i][j]<<" , ";

if(d[i][j]<z)

{ z=d[i][j]; index=j;

}

cout<<"\n"<<array[i]<<" belongs to cluster "<<index+1;

c[i]=index;

}

cout<<"\n\nCluster formation :"; for(int i=0;i<m;i++)

{ cout<<"\ncluster "<<i+1<<" : "; for(int j=0;j<n;j++)

{ b[i][j]=0;

if(c[j]==i)

{ b[i][j]=array[j];

cout<<b[i][j]<<" ";

}

cout<<"\n\nNew mean :"; for(int i=0;i<m;i++)

{ newmean[i]=0; int z=0; for(int j=0;j<n;j++)

{ if(b[i][j]!=0)

{ newmean[i]=newmean[i]+b[i][j]; z++;

}

newmean[i]=newmean[i]/z;

cout<<"\nnew cluster "<<i+1<<" = "<<newmean[i];

}

int flag[m]; for(int i=0;i<m;i++)

{

if(mean[i]!=newmean[i])

{ flag[i]=0;

mean[i]=newmean[i];

//break;

} else flag[i]=1;

} int i=0; while(i<m)

{ if(flag[i]==1)

{ i++; }

else break;

a=1; }

}while(a==0); cout<<"\n"; }

/******************OUTPUT********************

pccoe@ubuntu:~$ cd kmeans pccoe@ubuntu:~/kmeans$ g++ kmeans.cpp pccoe@ubuntu:~/kmeans$ ./a.out

---------------------------------------------------------

K-means code

---------------------------------------------------------

Enter no of elements = 8 Enter 8 elements :

Enter no of clusters = 2

Enter cluster mean 1 = 3

Enter cluster mean 2 = 8

Calculating distance : dist of 1 from cluster 1 = 2 , dist of 1 from cluster 2 = 7 ,

1 belongs to cluster 1

dist of 2 from cluster 1 = 1 , dist of 2 from cluster 2 = 6 ,

2 belongs to cluster 1

dist of 3 from cluster 1 = 0 , dist of 3 from cluster 2 = 5 ,

3 belongs to cluster 1

dist of 4 from cluster 1 = 1 , dist of 4 from cluster 2 = 4 ,

4 belongs to cluster 1

dist of 6 from cluster 1 = 3 , dist of 6 from cluster 2 = 2 ,

6 belongs to cluster 2

dist of 8 from cluster 1 = 5 , dist of 8 from cluster 2 = 0 ,

8 belongs to cluster 2

dist of 9 from cluster 1 = 6 , dist of 9 from cluster 2 = 1 ,

9 belongs to cluster 2

dist of 10 from cluster 1 = 7 , dist of 10 from cluster 2 = 2 ,

10 belongs to cluster 2

Cluster formation :

cluster 1 : 1 2 3 4

cluster 2 : 6 8 9 10

New mean :

new cluster 1 = 2 new cluster 2 = 8 Calculating distance :

dist of 1 from cluster 1 = 1 , dist of 1 from cluster 2 = 7 ,

1 belongs to cluster 1

dist of 2 from cluster 1 = 0 , dist of 2 from cluster 2 = 6 ,

2 belongs to cluster 1

dist of 3 from cluster 1 = 1 , dist of 3 from cluster 2 = 5 ,

3 belongs to cluster 1

dist of 4 from cluster 1 = 2 , dist of 4 from cluster 2 = 4 ,

4 belongs to cluster 1

dist of 6 from cluster 1 = 4 , dist of 6 from cluster 2 = 2 ,

6 belongs to cluster 2

dist of 8 from cluster 1 = 6 , dist of 8 from cluster 2 = 0 ,

8 belongs to cluster 2

dist of 9 from cluster 1 = 7 , dist of 9 from cluster 2 = 1 ,

9 belongs to cluster 2

dist of 10 from cluster 1 = 8 , dist of 10 from cluster 2 = 2 ,

10 belongs to cluster 2

Cluster formation :

cluster 1 : 1 2 3 4

cluster 2 : 6 8 9 10

New mean :

new cluster 1 = 2 new cluster 2 = 8

Step In For Wide Learning Experience

Search This Blog

Design And Analysis Of Algorithms(DAA)