import pandas as pd
 from sklearn.datasets import load_iris
 from sklearn.preprocessing import StandardScaler
 from sklearn.decomposition import PCA
 import seaborn as sns
 import matplotlib.pyplot as plt
 df=pd.read_csv("iris.csv")
 print(df.head())
 print(df.isnull().sum())
 #df.fillna(df.mean(),inplace=True)
 df_encoded=pd.get_dummies(df,columns=['Species'],drop_first=True)
 print(df_encoded.head())
 x=df_encoded
 x_scaled=StandardScaler().fit_transform(x)
 pca=PCA(n_components=2)
 x_pca=pca.fit_transform(x_scaled)

power iso if imager dont work

tools > usb tools > create bootable usb

clone 
server
ui

@ECHO OFF
set list=Desktop Documents Downloads Favorites Music Pictures Videos
set baseLocation="%USERPROFILE%\OneDrive - Olivet Nazarene University\LocalPC\"
set "Key=HKCU\Software\Microsoft\Windows\CurrentVersion\Explorer\User Shell Folders"
set "Typ=REG_EXPAND_SZ"
set RegList="Desktop" "Personal" "{374DE290-123F-4565-9164-39C4925E467B}" "Favorites" "My Music" "My Pictures" "My Video"
set /a c=0
setLocal enableDelayedExpansion
for %%j in (%RegList%) do (
    set RegList[!c!]=%%j & set /a c=c+1
)
for %%i in (%list%) do (
    if not exist %baseLocation%%%i (
        mkdir %baseLocation%%%i
    ) else (
        echo %%i already exsists
    )
)
set baseLocation=%baseLocation:"=%
for %%i in (%list%) do (
    RoboCopy.exe "%USERPROFILE%\%%~i\." "%baseLocation%\%%~i\." *.* /MOV /FP /NP /IS /Z /E /NFL /NDL /NJH
)
set /a d=0
for %%k in (%list%) do (
    call set val=%%RegList[!d!]%% & Reg Add "%Key%" /f /V !val! /T %Typ% /D "%baseLocation%%%k" & set /a d=d+1

 For /D /R j:\test %%1 IN (*) DO c:\trid_w32\trid "%%1"\* -ae
 
 
Replace j:\test with the directory that you want to move recursively through (TrID will not run on the files in the root of this directory).
 
Replace c:\trid_w32\trid with the path to trid.exe.
 
Dump the line in a batch file and run.

 #include <iostream>
#include <queue>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int d) {
        this->data = d;
        this->left = NULL;
        this->right = NULL;
    }
};

Node* insertIntoBST(Node* root, int d) {
    // base case 
    if (root == NULL) {
        root = new Node(d); // Create a new node
        return root; // Return the newly created node
    }
    if (d > root->data) {
        // Insert in the right subtree
        root->right = insertIntoBST(root->right, d);
    } else {
        // Insert in the left subtree
        root->left = insertIntoBST(root->left, d);
    }
    return root; // Return the root of the subtree
}

void levelOrderTraversal(Node* root) {
    if (root == NULL) 
        return; // If the tree is empty, return

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        cout << temp->data << " "; // Print the current node's data

        // Push left and right children into the queue
        if (temp->left) {
            q.push(temp->left);
        }
        if (temp->right) {
            q.push(temp->right);
        }
    }
    cout << endl; // Print a new line after level order traversal
}

void takeInput(Node*& root) {
    int data;
    cin >> data;

    while (data != -1) {
        root = insertIntoBST(root, data); // Update the root pointer
        
        // Print the current state of the BST after each insertion
        cout << "Current state of the BST after inserting " << data << ": ";
        levelOrderTraversal(root);
        
        cin >> data;
    }
}
void inorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    inorder(root->left);
    cout << root-> data << " ";
    inorder(root->right);
}
void preorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    cout << root-> data << " ";
    preorder(root->left);
    preorder(root->right);
}
void postorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    postorder(root->left);
    postorder(root->right);
    cout << root-> data << " ";
}
Node* minVal(Node* root){
    Node* temp = root;
    
    while(temp->left != NULL){
        temp = temp->left;
    }
    return temp;
}
Node* maxVal(Node* root){
    Node* temp = root;
    
    while(temp->right != NULL){
        temp = temp->right;
    }
    return temp;
}
int main() {
    Node* root = NULL;
    cout << "Enter the data for BST (end with -1): ";
    takeInput(root);
    
    cout << "printing inorder" << endl;
    inorder(root);
    
    cout << endl <<"printing preorder" << endl;
    preorder(root);
    
    cout << endl<<  "printing postorder" << endl;
    postorder(root);
    
    cout <<endl <<" min value is "<< minVal(root) -> data << endl;
    cout <<" min value is "<< maxVal(root) -> data << endl;
    
    
    
    
    return 0;
}


//// Time complexity = O(logn)

///************** BST QUESTION*************///////////// 
/// IN THIS QUESTION THEY WILL GIVE US A NUMBER AND IF IT IS PRESENT IN THAT TREE GIVE US TRUE OTHERWISE RETURN FALSE TO JUS 

/// APPROACH 
// if we get null return false otherwise if root->data > (number passed) go to the left side else go to right side 

///// FIRST APPROACH 
bool searchInBST(BinaryTreeNode<int> *root, int x){
    BinaryTreeNode<int> *temp = root;
    
    while(temp != NULL)
    
    if(temp->data == x){
        return true;
    }
    if(temp->data > x){
        temp = temp->left;
    }
    else{
        temp = temp->right;
    }
    return false;
}

////// second approach 
bool searchInBST(BinaryTreeNode<int> *root , int x ){
    // base case 
    if(root == Null){
        return false;
    }
    
    if(root ->data == x){
        return true;
    }
    if(root->data > x){
      return seachInBST(root->left , x ); 
    }
    else{
         return seachInBST(root->right, x ); 
    }

///************** BST QUESTION*************///////////// 
/// IN THIS QUESTION THEY WILL GIVE US A NUMBER AND IF IT IS PRESENT IN THAT TREE GIVE US TRUE OTHERWISE RETURN FALSE TO JUS 

/// APPROACH 
// if we get null return false otherwise if root->data > (number passed) go to the left side else go to right side 

///// FIRST APPROACH 
bool searchInBST(BinaryTreeNode<int> *root, int x){
    BinaryTreeNode<int> *temp = root;
    
    while(temp != NULL)
    
    if(temp->data == x){
        return true;
    }
    if(temp->data > x){
        temp = temp->left;
    }
    else{
        temp = temp->right;
    }
    return false;
}

////// second approach 
bool searchInBST(BinaryTreeNode<int> *root , int x ){
    // base case 
    if(root == Null){
        return false;
    }
    
    if(root ->data == x){
        return true;
    }
    if(root->data > x){
      return seachInBST(root->left , x ); 
    }
    else{
         return seachInBST(root->right, x ); 
    }

public class MergeSort {
   
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                i++;
            } else {
                temp[k] = arr[j];
                j++;
            }
            k++;
        }

        while (i <= mid) {
            temp[k] = arr[i];
            i++;
            k++;
        }

        while (j <= right) {
            temp[k] = arr[j];
            j++;
            k++;
        }

        for (i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);

        System.out.print("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

import java.util.Scanner;

public class QuickSort {

    public static void quicksort(int[] a, int lb, int ub) {
        int pivot, start, end;
        pivot = a[lb];
        start = lb;
        end = ub;

        if (start < end) {
            while (start < end) {
                while (start < end && a[start] <= pivot) {
                    start++;
                }
                while (a[end] > pivot) {
                    end--;
                }
                if (start < end) {
                    swap(a, start, end);
                }
            }
            swap(a, lb, end);

            quicksort(a, lb, end - 1);
            quicksort(a, end + 1, ub);
        }
    }

    
    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void display(int[] a) {
        System.out.println("Sorted array:");
        for (int i : a) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter array size:");
        int n = scanner.nextInt();
        int[] a = new int[n];

        System.out.println("Enter elements into array:");
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        quicksort(a, 0, n - 1);
        display(a);

        scanner.close();
    }
}

#include <iostream>
#include <queue>
using namespace std;

class Node {
public:
    int data;
    Node* left;
    Node* right;

    Node(int d) {
        this->data = d;
        this->left = NULL;
        this->right = NULL;
    }
};

Node* insertIntoBST(Node* root, int d) {
    // base case 
    if (root == NULL) {
        root = new Node(d); // Create a new node
        return root; // Return the newly created node
    }
    if (d > root->data) {
        // Insert in the right subtree
        root->right = insertIntoBST(root->right, d);
    } else {
        // Insert in the left subtree
        root->left = insertIntoBST(root->left, d);
    }
    return root; // Return the root of the subtree
}

void levelOrderTraversal(Node* root) {
    if (root == NULL) 
        return; // If the tree is empty, return

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
        cout << temp->data << " "; // Print the current node's data

        // Push left and right children into the queue
        if (temp->left) {
            q.push(temp->left);
        }
        if (temp->right) {
            q.push(temp->right);
        }
    }
    cout << endl; // Print a new line after level order traversal
}

void takeInput(Node*& root) {
    int data;
    cin >> data;

    while (data != -1) {
        root = insertIntoBST(root, data); // Update the root pointer
        
        // Print the current state of the BST after each insertion
        cout << "Current state of the BST after inserting " << data << ": ";
        levelOrderTraversal(root);
        
        cin >> data;
    }
}
void inorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    inorder(root->left);
    cout << root-> data << " ";
    inorder(root->right);
}
void preorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    cout << root-> data << " ";
    preorder(root->left);
    preorder(root->right);
}
void postorder(Node* root) {
    //base case
    if(root == NULL) {
        return ;
    }
    postorder(root->left);
    postorder(root->right);
    cout << root-> data << " ";
}

int main() {
    Node* root = NULL;
    cout << "Enter the data for BST (end with -1): ";
    takeInput(root);
    
    cout << "printing inorder" << endl;
    inorder(root);
    
    cout << endl <<"printing preorder" << endl;
    preorder(root);
    
    cout << endl<<  "printing postorder" << endl;
    postorder(root);
    return 0;
}


//// Time complexity = O(logn)

#KMeans Classification
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA
# Sample dataset: Fruit type with average RGB values
data = {'Fruit': ['Apple', 'Apple', 'Apple', 'Orange', 'Orange', 'Orange', 'Banana', 'Banana', 'Banana'],
        'Red': [180, 190, 170, 255, 250, 245, 240, 230, 220],
        'Green': [20, 30, 25, 120, 110, 105, 240, 230, 220],
        'Blue': [30, 40, 35, 70, 65, 60, 240, 230, 220]}

df = pd.DataFrame(data)
print(df)
# Extracting the features (Red, Green, Blue)
X = df[['Red', 'Green', 'Blue']]

# Standardize the data
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
# Apply K-Means with 3 clusters
kmeans = KMeans(n_clusters=3, random_state=42)
kmeans.fit(X_scaled)

# Get the cluster labels
df['Cluster'] = kmeans.labels_
print(df)
# Reduce data to 2D using PCA for visualization
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X_scaled)

# Plot the clusters
plt.figure(figsize=(8, 6))
plt.scatter(X_pca[:, 0], X_pca[:, 1], c=kmeans.labels_, cmap='viridis')
plt.title('Fruit Clusters (K-Means)')
plt.xlabel('PCA Component 1')
plt.ylabel('PCA Component 2')
plt.show()

#Decision Tree

from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report
import pandas as pd

# Load Soybean Dataset
url = "https://archive.ics.uci.edu/ml/machine-learning-databases/soybean/soybean-small.data"
columns = ['date', 'plant-stand', 'precip', 'temp', 'hail', 'crop-hist', 'area-damaged', 'severity', 'seed-tmt',
           'germination', 'plant-growth', 'leaves', 'leafspots-halo', 'leafspots-marg', 'leafspot-size',
           'leaf-shread', 'leaf-malf', 'leaf-mild', 'stem', 'lodging', 'stem-cankers', 'canker-lesion',
           'fruiting-bodies', 'external-decay', 'mycelium', 'int-discolor', 'sclerotia', 'fruit-pods',
           'roots', 'class'
          ]

data = pd.read_csv(url, header = None, names = columns)

X = data.drop(columns = ['class'])
y = data['class']

X = pd.get_dummies(X)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.3, random_state = 0)
decision_tree = DecisionTreeClassifier(criterion="gini", max_depth=5, random_state=42)
decision_tree.fit(X_train, y_train)

y_pred = decision_tree.predict(X_test)

accuracy = accuracy_score(y_test, y_pred)
conf = confusion_matrix(y_test, y_pred)
classR = classification_report(y_test, y_pred)

print(accuracy)
print(conf)
print(classR)

#Naive Bayes

from sklearn.model_selection import train_test_split
from sklearn.naive_bayes import GaussianNB
from sklearn.datasets import load_iris
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report

data = load_iris()
X = data.data
y = (data.target == 2).astype(int)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.3, random_state = 0)


model = GaussianNB()
model.fit(X_train, y_train)

y_pred = model.predict(X_test)

accuracy = accuracy_score(y_test, y_pred)
conf = confusion_matrix(y_test, y_pred)
classR = classification_report(y_test, y_pred)

print(accuracy)
print(conf)
print(classR)

#KNN

from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import confusion_matrix, accuracy_score, classification_report
from sklearn.datasets import load_iris

data = load_iris()
X = data.data
y = data.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, random_state = 42)

scaler = StandardScaler()
X_train = scaler.fit_transform(X_train)
X_test = scaler.fit_transform(X_test)


knn = KNeighborsClassifier(n_neighbors = 5)
knn.fit(X_train, y_train)

y_pred = knn.predict(X_test)


accuracy = accuracy_score(y_test, y_pred)
conf = confusion_matrix(y_test, y_pred)
classR = classification_report(y_test, y_pred)

print(accuracy)
print(conf)
print(classR)

#Linear Regression

from sklearn.model_selection import train_test_split
from sklearn.linear_model import LinearRegression
from sklearn.datasets import make_classification
from sklearn.metrics import confusion_matrix, accuracy_score, classification_report
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns

X, y = make_classification(n_samples = 1000, n_features = 2, n_redundant =0, n_informative = 2,  n_classes = 2, random_state = 42)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size = 0.2, random_state = 42)

linear_model = LinearRegression()
linear_model.fit(X_train, y_train)
y_pred_prob = linear_model.predict(X_test)
y_pred = (y_pred_prob >=0.5).astype(int)

cm = confusion_matrix(y_test, y_pred)
plt.figure(figsize = (6, 4))
sns.heatmap(cm, annot=True, fmt='d', cmap='Blues', cbar=False)

#Logistic Regression
# Import necessary libraries
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report
from sklearn.datasets import load_iris

# Load sample data
data = load_iris()
X = data.data
y = (data.target == 2).astype(int)  # Create a binary target for the logistic regression example

# Split data into training and test sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Create and train the logistic regression model
model = LogisticRegression()
model.fit(X_train, y_train)

# Make predictions
y_pred = model.predict(X_test)

# Evaluate the model
accuracy = accuracy_score(y_test, y_pred)
conf_matrix = confusion_matrix(y_test, y_pred)
class_report = classification_report(y_test, y_pred)

print("Accuracy:", accuracy)
print("Confusion Matrix:\n", conf_matrix)
print("Classification Report:\n", class_report)

#Line Plot
import matplotlib.pyplot as plt

x = [1,2,3,4,5]
y = [10, 20, 30, 40, 50]

plt.plot(x,y)
plt.title("Line Plot")
plt.xlabel("X")
plt.ylabel("Y")
plt.show()

#Bar Graph
plt.bar(x,y)
plt.title("Bar Graph")
plt.xlabel("X")
plt.ylabel("Y")
plt.show()

#Histogram
import numpy as np
data = np.random.randn(1000)

plt.hist(data, bins = 30)
plt.show()

#Box Plot
import seaborn as sns
import matplotlib.pyplot as plt

# Example data
data = sns.load_dataset('tips')

# Box plot
sns.boxplot(x='day', y='total_bill', data=data)
plt.title('Box Plot')
plt.show()

#Scatter Plot

import matplotlib.pyplot as plt

# Example data
x = [1, 2, 3, 4, 5]
y = [1, 4, 9, 16, 25]

# Scatter plot
plt.scatter(x, y, color='red')
plt.title('Scatter Plot')
plt.xlabel('X')
plt.ylabel('Y')
plt.show()
#Pie Chart

import matplotlib.pyplot as plt

# Example data
labels = ['Apple', 'Banana', 'Cherry', 'Date']
sizes = [10, 20, 30, 40]

# Pie chart
plt.pie(sizes, labels=labels, autopct='%1.1f%%', startangle=90)
plt.title('Pie Chart')
plt.show()
#Heatmap

import seaborn as sns
import matplotlib.pyplot as plt

# Example data
data = np.random.rand(10, 12)

# Heatmap
sns.heatmap(data, cmap='coolwarm', annot=True)
plt.title('Heatmap')
plt.show()
#Pair plot
import seaborn as sns
import matplotlib.pyplot as plt

# Example data
data = sns.load_dataset('iris')

# Pair plot
sns.pairplot(data, hue='species')
plt.title('Pair Plot')
plt.show()

#MinMaxScaler
from sklearn.preprocessing import MinMaxScaler
data = {
    'Feature1' : [100,200,300,400,500],
    'Feature2' : [1,2,3,4,5]
}
data = pd.DataFrame(data)

min_max_scaler = MinMaxScaler()
data = min_max_scaler.fit_transform(data)
data = pd.DataFrame(data)
data

#Standard Scaler
import pandas as pd
from sklearn.preprocessing import StandardScaler
data = {
    'Feature1' : [100,200,300,400,500],
    'Feature2' : [1,2,3,4,5]
}

data = pd.DataFrame(data)

standard_scaler = StandardScaler()
data_scaled = standard_scaler.fit_transform(data)

data_scaled = pd.DataFrame(data_scaled, columns = data.columns)
data_scaled

#OneHot Encoding
import pandas as pd
from sklearn.preprocessing import OneHotEncoder

data_one_hot = pd.get_dummies(data['Color'], prefix = 'Color')
df = pd.DataFrame(data_one_hot)
df

import pandas as pd
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler
# Sample data
data = {
 'Feature1': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 'Feature2': [5, 8, 12, 15, 18, 24, 28, 30, 34, 40]
}
df = pd.DataFrame(data)
# Standardize the features
scaler = StandardScaler()
X = scaler.fit_transform(df)
# Elbow method for finding optimal k
inertia = []
K = range(1, 11)
for k in K:
 kmeans = KMeans(n_clusters=k, random_state=42)
 kmeans.fit(X)
 inertia.append(kmeans.inertia_)
plt.plot(K, inertia, 'bo-')
plt.xlabel('Number of clusters, k')
plt.ylabel('Inertia')
plt.title('Elbow Method For Optimal k')
plt.show()
# Apply K-Means with the chosen number of clusters (e.g., 3)
kmeans = KMeans(n_clusters=3, random_state=42)
df['Cluster'] = kmeans.fit_predict(X)
# Visualize the clusters
plt.scatter(X[:, 0], X[:, 1], c=df['Cluster'], cmap='viridis', marker='o', edgecolor='k',
s=100)
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1], s=200, c='red',
marker='X') # Cluster centers
plt.xlabel('Feature1')
plt.ylabel('Feature2')
plt.title('K-Means Clustering')
plt.show()

#Label Encoding
from sklearn.preprocessing import OneHotEncoder, LabelEncoder
import pandas as pd

data = {
    'Color': ['Red', 'Green', 'Blue', 'Red', 'Blue', 'Green', 'Green']
}

df = pd.DataFrame(data)
label_encoder = LabelEncoder()

data['Color-Label'] = label_encoder.fit_transform(data['Color'])
df = pd.DataFrame(data)
df

#Missing values
import pandas as pd
data = {
    'Name': ['John', 'Alice', 'Steve'],
    'Age': [18, None, 20],
    'City': ['New York', 'California', None]
}

df = pd.DataFrame(data)

df.fillna({'Age': df['Age'].mean(), 'City': 'Unknown'})

import pandas as pd

# Sample dictionary
data = {
    'Name': ['Alice', 'Bob', 'Charlie'],
    'Age': [25, 30, 35],
    'City': ['New York', 'Los Angeles', 'Chicago']
}

# Convert dictionary to DataFrame
df = pd.DataFrame(data)

# Display the DataFrame
print(df)

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report
# Sample data
data = {
 'Feature1': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 'Feature2': [5, 10, 15, 20, 25, 30, 35, 40, 45, 50],
 'Target': [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
}
df = pd.DataFrame(data)
# Split data into features and target
X = df[['Feature1', 'Feature2']]
y = df['Target']
# Split dataset
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# Initialize and fit model
rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X_train, y_train)
# Make predictions
y_pred = rf.predict(X_test)
# Evaluate model
accuracy = accuracy_score(y_test, y_pred)
conf_matrix = confusion_matrix(y_test, y_pred)
class_report = classification_report(y_test, y_pred)
print(f'Accuracy: {accuracy:.2f}')
print('Confusion Matrix:')
print(conf_matrix)
print('Classification Report:')
print(class_report)

https://tinyurl.com/ds-lab-datasets-123

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report
# Sample data
data = {
 'Feature1': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 'Feature2': [5, 10, 15, 20, 25, 30, 35, 40, 45, 50],
 'Target': [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
}
df = pd.DataFrame(data)
# Split data into features and target
X = df[['Feature1', 'Feature2']]
y = df['Target']
# Split dataset
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# Initialize and fit model
tree = DecisionTreeClassifier(max_depth=3, random_state=42)
tree.fit(X_train, y_train)
# Make predictions
y_pred = tree.predict(X_test)
# Evaluate model
accuracy = accuracy_score(y_test, y_pred)
conf_matrix = confusion_matrix(y_test, y_pred)
class_report = classification_report(y_test, y_pred)
print(f'Accuracy: {accuracy:.2f}')
print('Confusion Matrix:')
print(conf_matrix)
print('Classification Report:')
print(class_report)

public class OBSTree {

    public static void main(String[] args) {
        double[] P = {3, 3, 1, 1};
        double[] Q = {2, 3, 1, 1, 1};

        int n = P.length;

        OBSTResult result = OBST(P, Q, n);

        System.out.println("Cost Matrix C:");
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.printf("%.2f ", result.C[i][j]);
            }
            System.out.println();
        }

        System.out.println("\nRoot Matrix R:");
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.printf("%d ", result.R[i][j]);
            }
            System.out.println();
        }
    }

    public static OBSTResult OBST(double[] P, double[] Q, int n) {
        double[][] C = new double[n + 1][n + 1];
        double[][] W = new double[n + 1][n + 1];
        int[][] R = new int[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            W[i][i] = Q[i];
            C[i][i] = 0;
            R[i][i] = 0;
            if (i < n) {
                W[i][i + 1] = Q[i] + Q[i + 1] + P[i];
                C[i][i + 1] = W[i][i + 1];
                R[i][i + 1] = i + 1;
            }
        }

        for (int m = 2; m <= n; m++) {
            for (int i = 0; i <= n - m; i++) {
                int j = i + m;
                W[i][j] = W[i][j - 1] + P[j - 1] + Q[j];

                double minCost = Double.MAX_VALUE;
                int bestRoot = -1;

                for (int k = R[i][j - 1]; k <= R[i + 1][j]; k++) {
                    double cost = C[i][k - 1] + C[k][j];
                    if (cost < minCost) {
                        minCost = cost;
                        bestRoot = k;
                    }
                }

                C[i][j] = W[i][j] + minCost;
                R[i][j] = bestRoot;
            }
        }

        return new OBSTResult(C, W, R);
    }
}

class OBSTResult {
    double[][] C;
    double[][] W;
    int[][] R;

    OBSTResult(double[][] C, double[][] W, int[][] R) {
        this.C = C;
        this.W = W;
        this.R = R;
    }
}

/*
Test Case 1:
Input:
P = {3, 3, 1, 1}
Q = {2, 3, 1, 1, 1}

Expected Output:
Cost Matrix C:
0.00 2.00 5.00 8.00 9.00 
0.00 0.00 4.00 7.00 8.00 
0.00 0.00 0.00 4.00 5.00 
0.00 0.00 0.00 0.00 1.00 
0.00 0.00 0.00 0.00 0.00 

Root Matrix R:
0 1 1 1 1 
0 0 1 1 2 
0 0 0 3 3 
0 0 0 0 4 
0 0 0 0 0

Test Case 2:
Input:
P = {4, 2, 3, 4, 2}
Q = {3, 1, 2, 1, 2, 3}

Expected Output:
Cost Matrix C:
0.00 3.00 7.00 10.00 15.00 18.00 
0.00 0.00 2.00 5.00 9.00 12.00 
0.00 0.00 0.00 2.00 5.00 7.00 
0.00 0.00 0.00 0.00 2.00 4.00 
0.00 0.00 0.00 0.00 0.00 2.00 
0.00 0.00 0.00 0.00 0.00 0.00 

Root Matrix R:
0 1 2 3 3 4 
0 0 1 2 3 3 
0 0 0 1 2 3 
0 0 0 0 1 2 
0 0 0 0 0 1 
0 0 0 0 0 0
*/

//DijkstraAlgorithm 
import java.util.Scanner;
import java.util.Arrays;

public class DijkstraAlgorithm {

    // Method to find the vertex with the minimum distance value that hasn't been processed yet
    static int getMinDistanceVertex(int[] distance, boolean[] processedVertices, int numberOfVertices) {
        int minDistance = Integer.MAX_VALUE;  // Initialize with a large value
        int minVertexIndex = -1;  // Index of the vertex with the minimum distance

        // Search for the vertex with the smallest distance value
        for (int vertex = 0; vertex < numberOfVertices; vertex++) {
            if (!processedVertices[vertex] && distance[vertex] <= minDistance) {
                minDistance = distance[vertex];  // Update minimum distance
                minVertexIndex = vertex;  // Update index of vertex with minimum distance
            }
        }
        return minVertexIndex;
    }

    // Method to implement Dijkstra's algorithm to find the shortest path from the source
    static void dijkstra(int[][] graph, int[] distance, boolean[] processedVertices, int numberOfVertices, int sourceVertex) {
        // Initialize distances and processedVertices
        Arrays.fill(distance, Integer.MAX_VALUE);  // Set all distances to infinity initially
        Arrays.fill(processedVertices, false);  // Mark all vertices as unprocessed

        distance[sourceVertex] = 0;  // Distance from source to itself is 0

        // Find the shortest path for all vertices
        for (int i = 0; i < numberOfVertices - 1; i++) {
            // Get the vertex with the minimum distance value that hasn't been processed yet
            int currentVertex = getMinDistanceVertex(distance, processedVertices, numberOfVertices);

            // Mark the current vertex as processed
            processedVertices[currentVertex] = true;

            // Update distance values of adjacent vertices of the current vertex
            for (int adjacentVertex = 0; adjacentVertex < numberOfVertices; adjacentVertex++) {
                // If the adjacent vertex is unprocessed, has a path from currentVertex, and distance can be minimized
                if (!processedVertices[adjacentVertex] && graph[currentVertex][adjacentVertex] != 0 &&
                        distance[currentVertex] != Integer.MAX_VALUE &&
                        distance[currentVertex] + graph[currentVertex][adjacentVertex] < distance[adjacentVertex]) {
                    // Update the distance to the adjacent vertex
                    distance[adjacentVertex] = distance[currentVertex] + graph[currentVertex][adjacentVertex];
                }
            }
        }
    }

    // Method to print the solution (distances from source vertex)
    static void printSolution(int[] distance, int numberOfVertices) {
        System.out.println("Vertex   Distance from Source");
        for (int i = 0; i < numberOfVertices; i++) {
            System.out.println(i + " \t\t " + distance[i]);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Taking input for number of vertices
        System.out.print("Enter the number of vertices: ");
        int numberOfVertices = sc.nextInt();

        // Initialize the graph matrix (adjacency matrix)
        int[][] graph = new int[numberOfVertices][numberOfVertices];

        // Taking input for the adjacency matrix (graph)
        System.out.println("Enter the adjacency matrix (0 means no edge between vertices):");
        for (int i = 0; i < numberOfVertices; i++) {
            for (int j = 0; j < numberOfVertices; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // Taking input for the source vertex
        System.out.print("Enter the source vertex: ");
        int sourceVertex = sc.nextInt();

        // Arrays to store the distance and processed status of vertices
        int[] distance = new int[numberOfVertices];
        boolean[] processedVertices = new boolean[numberOfVertices];

        // Run Dijkstra's algorithm starting from the source vertex
        dijkstra(graph, distance, processedVertices, numberOfVertices, sourceVertex);

        // Print the shortest distances from the source vertex
        printSolution(distance, numberOfVertices);
    }
}

/*
Test Case
Enter the number of vertices: 5
Enter the adjacency matrix (0 means no edge between vertices):
0 10 0 0 0
0 0 5 0 0
0 0 0 15 0
0 0 0 0 20
0 0 0 0 0
Enter the source vertex: 0
Vertex   Distance from Source
0        0
1        10
2        15
3        30
4        50
*/

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.naive_bayes import GaussianNB
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report
# Sample data
data = {
 'Feature1': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 'Feature2': [5, 10, 15, 20, 25, 30, 35, 40, 45, 50],
 'Target': [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
}
df = pd.DataFrame(data)
# Split data into features and target
X = df[['Feature1', 'Feature2']]
y = df['Target']
# Split dataset
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# Initialize and fit model
nb = GaussianNB()
nb.fit(X_train, y_train)
# Make predictions
y_pred = nb.predict(X_test)
# Evaluate model
accuracy = accuracy_score(y_test, y_pred)
conf_matrix = confusion_matrix(y_test, y_pred)
class_report = classification_report(y_test, y_pred)
print(f'Accuracy: {accuracy:.2f}')
print('Confusion Matrix:')
print(conf_matrix)
print('Classification Report:')
print(class_report)

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report
# Sample data
data = {
 'Feature1': [2, 4, 4, 4, 6, 6, 6, 8, 8, 8],
 'Feature2': [4, 2, 4, 6, 2, 4, 6, 2, 4, 6],
 'Target': [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
}
df = pd.DataFrame(data)
# Split data into features and target
X = df[['Feature1', 'Feature2']]
y = df['Target']
# Split dataset
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# Initialize and fit model
knn = KNeighborsClassifier(n_neighbors=3)
knn.fit(X_train, y_train)
# Make predictions
y_pred = knn.predict(X_test)
# Evaluate model
accuracy = accuracy_score(y_test, y_pred)
conf_matrix = confusion_matrix(y_test, y_pred)
class_report = classification_report(y_test, y_pred)

//DijkstraAlgorithm 
import java.util.Scanner;
import java.util.Arrays;

public class DijkstraAlgorithm {

    // Method to find the vertex with the minimum distance value that hasn't been processed yet
    static int getMinDistanceVertex(int[] distance, boolean[] processedVertices, int numberOfVertices) {
        int minDistance = Integer.MAX_VALUE;  // Initialize with a large value
        int minVertexIndex = -1;  // Index of the vertex with the minimum distance

        // Search for the vertex with the smallest distance value
        for (int vertex = 0; vertex < numberOfVertices; vertex++) {
            if (!processedVertices[vertex] && distance[vertex] <= minDistance) {
                minDistance = distance[vertex];  // Update minimum distance
                minVertexIndex = vertex;  // Update index of vertex with minimum distance
            }
        }
        return minVertexIndex;
    }

    // Method to implement Dijkstra's algorithm to find the shortest path from the source
    static void dijkstra(int[][] graph, int[] distance, boolean[] processedVertices, int numberOfVertices, int sourceVertex) {
        // Initialize distances and processedVertices
        Arrays.fill(distance, Integer.MAX_VALUE);  // Set all distances to infinity initially
        Arrays.fill(processedVertices, false);  // Mark all vertices as unprocessed

        distance[sourceVertex] = 0;  // Distance from source to itself is 0

        // Find the shortest path for all vertices
        for (int i = 0; i < numberOfVertices - 1; i++) {
            // Get the vertex with the minimum distance value that hasn't been processed yet
            int currentVertex = getMinDistanceVertex(distance, processedVertices, numberOfVertices);

            // Mark the current vertex as processed
            processedVertices[currentVertex] = true;

            // Update distance values of adjacent vertices of the current vertex
            for (int adjacentVertex = 0; adjacentVertex < numberOfVertices; adjacentVertex++) {
                // If the adjacent vertex is unprocessed, has a path from currentVertex, and distance can be minimized
                if (!processedVertices[adjacentVertex] && graph[currentVertex][adjacentVertex] != 0 &&
                        distance[currentVertex] != Integer.MAX_VALUE &&
                        distance[currentVertex] + graph[currentVertex][adjacentVertex] < distance[adjacentVertex]) {
                    // Update the distance to the adjacent vertex
                    distance[adjacentVertex] = distance[currentVertex] + graph[currentVertex][adjacentVertex];
                }
            }
        }
    }

    // Method to print the solution (distances from source vertex)
    static void printSolution(int[] distance, int numberOfVertices) {
        System.out.println("Vertex   Distance from Source");
        for (int i = 0; i < numberOfVertices; i++) {
            System.out.println(i + " \t\t " + distance[i]);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // Taking input for number of vertices
        System.out.print("Enter the number of vertices: ");
        int numberOfVertices = sc.nextInt();

        // Initialize the graph matrix (adjacency matrix)
        int[][] graph = new int[numberOfVertices][numberOfVertices];

        // Taking input for the adjacency matrix (graph)
        System.out.println("Enter the adjacency matrix (0 means no edge between vertices):");
        for (int i = 0; i < numberOfVertices; i++) {
            for (int j = 0; j < numberOfVertices; j++) {
                graph[i][j] = sc.nextInt();
            }
        }

        // Taking input for the source vertex
        System.out.print("Enter the source vertex: ");
        int sourceVertex = sc.nextInt();

        // Arrays to store the distance and processed status of vertices
        int[] distance = new int[numberOfVertices];
        boolean[] processedVertices = new boolean[numberOfVertices];

        // Run Dijkstra's algorithm starting from the source vertex
        dijkstra(graph, distance, processedVertices, numberOfVertices, sourceVertex);

        // Print the shortest distances from the source vertex
        printSolution(distance, numberOfVertices);
    }
}

/*
Test Case
Enter the number of vertices: 5
Enter the adjacency matrix (0 means no edge between vertices):
0 10 0 0 0
0 0 5 0 0
0 0 0 15 0
0 0 0 0 20
0 0 0 0 0
Enter the source vertex: 0
Vertex   Distance from Source
0        0
1        10
2        15
3        30
4        50
*/

//Job Scheduling
import java.util.*;

class Job {
    int id;
    int deadline;
    int profit;

    Job(int id, int deadline, int profit) {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}

public class JobScheduling {

    static class JobComparator implements Comparator<Job> {
        public int compare(Job j1, Job j2) {
            return j2.profit - j1.profit;
        }
    }

    public static int jobSequence(Job[] jobs, int n) {
        Arrays.sort(jobs, new JobComparator());
        
        int[] slot = new int[n];
        Arrays.fill(slot, 0);
        
        int[] jobSequence = new int[n];
        int count = 0;
        int totalProfit = 0;

        for (int i = 0; i < n; i++) {
            for (int j = jobs[i].deadline - 1; j >= 0; j--) {
                if (slot[j] == 0) {
                    slot[j] = 1;
                    jobSequence[j] = jobs[i].id;
                    totalProfit += jobs[i].profit;
                    count++;
                    break;
                }
            }
        }

        System.out.println("Scheduled jobs:");
        for (int i = 0; i < n; i++) {
            if (slot[i] == 1) {
                System.out.println("Job ID: " + jobSequence[i] + ", Profit: " + jobs[i].profit);
            }
        }
        System.out.println("Total profit: " + totalProfit);

        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of jobs: ");
        int n = scanner.nextInt();
        
        Job[] jobs = new Job[n];

        System.out.println("Enter job ID, deadline, profit for each job:");
        for (int i = 0; i < n; i++) {
            int id = scanner.nextInt();
            int deadline = scanner.nextInt();
            int profit = scanner.nextInt();
            jobs[i] = new Job(id, deadline, profit);
        }

        jobSequence(jobs, n);
        scanner.close();
    }
}

/*
Test Case 1:
Input:
5
1 2 50
2 1 10
3 2 20
4 1 30
5 3 40

Expected Output:
Scheduled jobs:
Job ID: 1, Profit: 50
Job ID: 5, Profit: 40
Total profit: 90

Test Case 2:
Input:
4
1 4 30
2 1 20
3 2 10
4 1 40

Expected Output:
Scheduled jobs:
Job ID: 4, Profit: 40
Job ID: 1, Profit: 30
Total profit: 70
*/

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error, mean_absolute_error, r2_score
# Sample data
data = {
 'Feature1': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 'Feature2': [5, 10, 15, 20, 25, 30, 35, 40, 45, 50],
 'Target': [2, 4, 5, 7, 10, 13, 14, 16, 18, 20]
}
df = pd.DataFrame(data)
# Split data into features and target
X = df[['Feature1', 'Feature2']]
y = df['Target']
# Split dataset
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# Initialize and fit model
linreg = LinearRegression()
linreg.fit(X_train, y_train)
# Make predictions
y_pred = linreg.predict(X_test)
# Evaluate model
mse = mean_squared_error(y_test, y_pred)
mae = mean_absolute_error(y_test, y_pred)
r2 = r2_score(y_test, y_pred)
print(f'Mean Squared Error: {mse:.2f}')
print(f'Mean Absolute Error: {mae:.2f}')
print(f'R-squared Score: {r2:.2f}')

//Articulation Points
import java.util.*;

public class ArticulationPoints {
    private int numVertices;
    private int[][] adjacencyMatrix;
    private int[] discoveryTime;
    private int[] lowLinkValue;
    private int timeCounter;
    private Set<Integer> articulationPoints;

    public ArticulationPoints(int numVertices) {
        this.numVertices = numVertices;
        adjacencyMatrix = new int[numVertices][numVertices];
        discoveryTime = new int[numVertices];
        lowLinkValue = new int[numVertices];
        timeCounter = 1;
        articulationPoints = new HashSet<>();
    }

    public void readGraph(Scanner scanner) {
        for (int i = 0; i < numVertices; i++) {
            for (int j = 0; j < numVertices; j++) {
                adjacencyMatrix[i][j] = scanner.nextInt();
            }
            discoveryTime[i] = 0;
        }
    }

    public void findArticulationPoints(int currentVertex, int parentVertex) {
        discoveryTime[currentVertex] = timeCounter;
        lowLinkValue[currentVertex] = timeCounter;
        timeCounter++;
        int childrenCount = 0;

        for (int adjacentVertex = 0; adjacentVertex < numVertices; adjacentVertex++) {
            if (adjacencyMatrix[currentVertex][adjacentVertex] == 1 && discoveryTime[adjacentVertex] == 0) {
                if (parentVertex == -1) childrenCount++;
                findArticulationPoints(adjacentVertex, currentVertex);

                if (parentVertex != -1 && lowLinkValue[adjacentVertex] >= discoveryTime[currentVertex]) {
                    articulationPoints.add(currentVertex);
                }

                lowLinkValue[currentVertex] = Math.min(lowLinkValue[currentVertex], lowLinkValue[adjacentVertex]);
            } else if (adjacencyMatrix[currentVertex][adjacentVertex] == 1 && adjacentVertex != parentVertex) {
                lowLinkValue[currentVertex] = Math.min(lowLinkValue[currentVertex], discoveryTime[adjacentVertex]);
            }
        }

        if (parentVertex == -1 && childrenCount > 1) {
            articulationPoints.add(currentVertex);
        }
    }

    public void printResults() {
        System.out.println("Articulation points: " + articulationPoints);
        System.out.print("Discovery times: ");
        for (int i = 0; i < numVertices; i++) {
            System.out.print(discoveryTime[i] - 1 + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("Enter number of vertices:");
        int numVertices = scanner.nextInt();
        ArticulationPoints articulation = new ArticulationPoints(numVertices);

        System.out.println("Enter the adjacency matrix:");
        articulation.readGraph(scanner);

        articulation.findArticulationPoints(0, -1);
        articulation.printResults();
    }
}

// Input for Test Case with 4 vertices
/*
4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
*/

// Expected Output
/*
Articulation points: [1, 2]
Discovery times: 0 1 2 3
*/

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score, confusion_matrix, classification_report
# Sample data
data = {
 'Feature1': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 'Feature2': [5, 10, 15, 20, 25, 30, 35, 40, 45, 50],
 'Target': [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
}
df = pd.DataFrame(data)
# Split data into features and target
X = df[['Feature1', 'Feature2']]
y = df['Target']
# Split dataset
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
# Initialize and fit model
logreg = LogisticRegression()
logreg.fit(X_train, y_train)
# Make predictions
y_pred = logreg.predict(X_test)
# Evaluate model
accuracy = accuracy_score(y_test, y_pred)
conf_matrix = confusion_matrix(y_test, y_pred)
class_report = classification_report(y_test, y_pred)
print(f'Accuracy: {accuracy:.2f}')
print('Confusion Matrix:')
print(conf_matrix)
print('Classification Report:')
print(class_report)

//Fractional Knapsack
import java.util.*;

class Item {
    int profit;
    int weight;
    float ratio;

    Item(int profit, int weight) {
        this.profit = profit;
        this.weight = weight;
        ratio = (float) (profit / weight);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int capacity = sc.nextInt();
        
        Item[] items = new Item[N];
        
        for (int i = 0; i < N; i++) {
            int profit = sc.nextInt();
            int weight = sc.nextInt();
            items[i] = new Item(profit, weight);
        }
        
        float profit = fractionalKnapsack(items, N, capacity);
        System.out.println("Total profit: " + profit);
    }
    
    public static float fractionalKnapsack(Item[] items, int N, int capacity) {
        Arrays.sort(items, Comparator.comparingDouble((Item item) -> item.ratio).reversed());
        
        float totalProfit = 0;
        int currentWeight = 0;
        
        for (Item item : items) {
            if (currentWeight + item.weight <= capacity) {
                currentWeight += item.weight;
                totalProfit += item.profit;
            } else {
                int remaining = capacity - currentWeight;
                totalProfit += item.profit * ((float) remaining / item.weight);
                break;
            }
        }
        return totalProfit;
    }
}

/*
Sample Test Case:

Input:
4
50
60 10
100 20
120 30
80 40

Output:
Total profit: 240.0
*/

//Merge sort
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] array = new int[N];
        int[] tempArray = new int[N];
        for (int i = 0; i < N; i++)
            array[i] = sc.nextInt();
        mergeSort(array, tempArray, 0, N - 1);
        System.out.println("Sorted Elements: ");
        for (int i = 0; i < N; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

    public static void mergeSort(int[] array, int[] tempArray, int low, int high) {
        if (low < high) {
            int mid = low + (high - low) / 2;
            mergeSort(array, tempArray, low, mid);
            mergeSort(array, tempArray, mid + 1, high);
            merge(array, tempArray, low, high, mid);
        }
    }

    public static void merge(int[] array, int tempArray[], int low, int high, int mid) {
        int left = low;
        int right = mid + 1;
        int current = low;
        while (left <= mid && right <= high) {
            if (array[left] <= array[right]) {
                tempArray[current++] = array[left++];
            } else {
                tempArray[current++] = array[right++];
            }
        }
        while (left <= mid) {
            tempArray[current++] = array[left++];
        }
        while (right <= high) {
            tempArray[current++] = array[right++];
        }
        for (int i = low; i <= high; i++) {
            array[i] = tempArray[i];
        }
    }
}

/*
Sample Test Case:

Input:
6
38 27 43 3 9 82

Output:
Sorted Elements:
3 9 27 38 43 82
*/

//Quick Sort Algorithm
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] array = new int[N];
        for (int i = 0; i < N; i++)
            array[i] = sc.nextInt();
        quickSort(array, 0, N - 1);
        System.out.println("Sorted Elements: ");
        for (int i = 0; i < N; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

    public static int partition(int[] array, int p, int q) {
        int v = array[p];
        int i = p, j = q + 1;
        do {
            do {
                i++;
            } while (i < q && array[i] < v);
            do {
                j--;
            } while (j > p && array[j] > v);
            if (i < j) {
                interchange(array, i, j);
            }
        } while (i < j);
        interchange(array, p, j);
        return j;
    }

    public static void quickSort(int[] array, int p, int q) {
        if (p < q) {
            int j = partition(array, p, q);
            quickSort(array, p, j - 1);
            quickSort(array, j + 1, q);
        }
    }

    public static void interchange(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

/*
Sample Test Case:

Input:
5
12 4 7 9 2

Output:
Sorted Elements:
2 4 7 9 12
*/

import java.util.*;

public class NQueens {

    public static void solveNQueens(int n) {
        int[] board = new int[n];
        Arrays.fill(board, -1);
        solve(0, board, n);
    }

    private static void solve(int col, int[] board, int n) {
        if (col == n) {
            printBoard(board, n);
            return;
        }

        for (int row = 0; row < n; row++) {
            if (isSafe(board, col, row, n)) {
                board[col] = row;
                solve(col + 1, board, n);
                board[col] = -1;
            }
        }
    }

    private static boolean isSafe(int[] board, int col, int row, int n) {
        for (int i = 0; i < col; i++) {
            if (board[i] == row || Math.abs(board[i] - row) == Math.abs(i - col)) {
                return false;
            }
        }
        return true;
    }

    private static void printBoard(int[] board, int n) {
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++) {
                sb.append(board[i] == j ? 'Q' : '.');
            }
            System.out.println(sb.toString());
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter the value of n (size of the board): ");
        int n = scanner.nextInt();
        solveNQueens(n);
    }
}

import java.util.*;

public class Dijkstra {

 
    public static void dijkstra(int[][] cost, int source) {
        int n = cost.length; 
        boolean[] visited = new boolean[n]; 
        double[] dist = new double[n]; 

        Arrays.fill(dist, Double.POSITIVE_INFINITY);
        dist[source] = 0.0; 

        for (int count = 0; count < n - 1; count++) {
           
            int u = minDistance(dist, visited);
            visited[u] = true; 

       
            for (int v = 0; v < n; v++) {
               
                if (!visited[v] && cost[u][v] != 0 && dist[u] != Double.POSITIVE_INFINITY
                        && dist[u] + cost[u][v] < dist[v]) {
                    dist[v] = dist[u] + cost[u][v];
                }
            }
        }


        printSolution(dist);
    }


    private static int minDistance(double[] dist, boolean[] visited) {
        double min = Double.POSITIVE_INFINITY;
        int minIndex = -1;

        for (int v = 0; v < dist.length; v++) {
            if (!visited[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }


    private static void printSolution(double[] dist) {
        System.out.println("Vertex Distance from Source");
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + " \t\t " + dist[i]);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of vertices: ");
        int n = scanner.nextInt();

   
        int[][] cost = new int[n][n];
        System.out.println("Enter the adjacency matrix (enter 0 for no edge):");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cost[i][j] = scanner.nextInt();
            }
        }

        System.out.print("Enter the source vertex (0 to " + (n - 1) + "): ");
        int source = scanner.nextInt();

  
        dijkstra(cost, source);

        scanner.close();
    }
}

Algorithm ShortestPaths(v, cost, dist, n)
// dist[j], 1 ≤ j ≤ n, is set to the length of the shortest path 
// from vertex v to vertex j in a digraph G with n vertices. 
// dist[v] is set to zero. G is represented by its 
// cost adjacency matrix cost[1 : n, 1 : n].

for i := 1 to n do {
    // Initialize S and distances.
    S[i] := false;
    dist[i] := cost[v, i];
}
S[v] := true; dist[v] := 0.0; // Put v in S.

for num := 1 to n - 1 do {
    // Determine n - 1 shortest paths from v.
    Choose u from among those vertices not in S such that dist[u] is minimum;
    S[u] := true; // Put u in S.

    for (each w adjacent to u with S[w] = false) do {
        // Update distances.
        if (dist[w] > dist[u] + cost[u, w]) then
            dist[w] := dist[u] + cost[u, w];
    }
}

import java.util.Scanner;

class PrimsAlgorithm {
    private static int V;

    int minKey(int key[], boolean mstSet[]) {
        int min = Integer.MAX_VALUE, minIndex = -1;
        for (int v = 0; v < V; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }
        return minIndex;
    }

    void printMST(int parent[], int graph[][]) {
        int totalCost = 0;
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
            totalCost += graph[i][parent[i]];
        }
        System.out.println("Total cost of the MST: " + totalCost);
    }

    void primMST(int graph[][]) {
        int parent[] = new int[V];
        int key[] = new int[V];
        boolean mstSet[] = new boolean[V];

        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
            }
        }

        printMST(parent, graph);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of vertices: ");
        V = scanner.nextInt();

        int[][] graph = new int[V][V];

        System.out.println("Enter the adjacency matrix (enter 0 if there is no edge between two vertices):");
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                graph[i][j] = scanner.nextInt();
            }
        }

        PrimsAlgorithm t = new PrimsAlgorithm();
        t.primMST(graph);

        scanner.close();
    }
}




Algorithm Prim(E, cost, n, t)
// E is the set of edges in G. cost[1 : n, 1 : n] is the cost
// adjacency matrix of an n vertex graph such that cost[i, j] is
// either a positive real number or ∞ if no edge (i, j) exists.
// A minimum spanning tree is computed and stored as a set of
// edges in the array t[1 : n − 1, 1 : 2]. (t[i, 1], t[i, 2]) is an edge in
// the minimum-cost spanning tree. The final cost is returned.

css
Copy code
Let (k, l) be an edge of minimum cost in E;  
mincost := cost[k, l];  
t[1, 1] := k; t[1, 2] := l;  
for i := 1 to n do  // Initialize near.  
{  
    if (cost[i, l] < cost[i, k]) then near[i] := l;  
    else near[i] := k;  
}  
near[k] := near[l] := 0;  
for i := 2 to n − 1 do  
{  
    // Find n − 2 additional edges for t.  
    Let j be an index such that near[j] ≠ 0 and  
    cost[j, near[j]] is minimum;  
    t[i, 1] := j; t[i, 2] := near[j];  
    mincost := mincost + cost[j, near[j]];  
    near[j] := 0;  
    for k := 1 to n do  // Update near[ ].  
    {  
        if ((near[k] ≠ 0) and (cost[k, near[k]] > cost[k, j]))  
            then near[k] := j;  
    }  
}  
return mincost;

import java.util.*;

public class Graph {
    private int vertices;
    private LinkedList<Integer>[] adjList;
    private int time;

    public Graph(int v) {
        vertices = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adjList[i] = new LinkedList<>();
        }
        time = 0;
    }

    public void addEdge(int v, int w) {
        adjList[v].add(w);
        adjList[w].add(v);
    }

    public void findArticulationPoints() {
        boolean[] visited = new boolean[vertices];
        int[] dfn = new int[vertices];
        int[] low = new int[vertices];
        int[] parent = new int[vertices];
        Arrays.fill(parent, -1);

        for (int i = 0; i < vertices; i++) {
            if (!visited[i]) {
                DFSArt(i, visited, dfn, low, parent);
            }
        }
    }

    private void DFSArt(int u, boolean[] visited, int[] dfn, int[] low, int[] parent) {
        visited[u] = true;
        dfn[u] = low[u] = ++time;
        int childCount = 0;
        boolean isArticulation = false;

        for (int v : adjList[u]) {
            if (!visited[v]) {
                childCount++;
                parent[v] = u;
                DFSArt(v, visited, dfn, low, parent);

                low[u] = Math.min(low[u], low[v]);

                if (parent[u] != -1 && low[v] >= dfn[u]) {
                    isArticulation = true;
                }

                if (parent[u] == -1 && childCount > 1) {
                    isArticulation = true;
                }
            } else if (v != parent[u]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        if (isArticulation) {
            System.out.println("Articulation Point: " + u);
        }
    }

    public static Graph createGraphFromAdjMatrix(int[][] adjMatrix) {
        int n = adjMatrix.length;
        Graph g = new Graph(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (adjMatrix[i][j] == 1) {
                    g.addEdge(i, j);
                }
            }
        }
        return g;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of vertices: ");
        int v = scanner.nextInt();

        System.out.println("Enter the adjacency matrix:");
        int[][] adjMatrix = new int[v][v];
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                adjMatrix[i][j] = scanner.nextInt();
            }
        }

        Graph g = Graph.createGraphFromAdjMatrix(adjMatrix);

        System.out.println("Articulation Points:");
        g.findArticulationPoints();
    }
}





AlgorithmArt(u, v)
// u: Start vertex for Depth First Search (DFS)
// v: Parent of u in the DFS tree (if any)
// dfn: Global array initialized to 0, storing discovery times of vertices
// L: Global array to store the lowest discovery time reachable from each vertex
// num: Global variable initialized to 1, represents the discovery order
// n: Number of vertices in the graph

{
    dfn[u] := num;           // Assign discovery time for u
    L[u] := num;             // Initialize lowest discovery time for u
    num := num + 1;          // Increment discovery counter

    for each vertex w adjacent to u do
    {
        if (dfn[w] = 0) then  // If w is unvisited
        {
            Art(w, u);        // Recursively visit w
            L[u] := min(L[u], L[w]);  // Update the lowest discovery time for u
        }
        elseif (w ≠ v) then   // If w is not the parent of u
        {
            L[u] := min(L[u], dfn[w]); // Update the lowest discovery time
        }
    }
}
 AlgorithmBiComp(u, v)
// u: Start vertex for Depth First Search (DFS)
// v: Parent of u in the DFS tree (if any)
// dfn: Global array initialized to 0, storing discovery times of vertices
// L: Global array to store the lowest discovery time reachable from each vertex
// num: Global variable initialized to 1, represents the discovery order
// s: Stack to store edges
// n: Number of vertices in the graph

{
    dfn[u] := num;           // Assign discovery time for u
    L[u] := num;             // Initialize lowest discovery time for u
    num := num + 1;          // Increment discovery counter

    for each vertex w adjacent to u do
    {
        // Push edge (u, w) onto the stack if it exists and w is not the parent
        if ((w ≠ v) and (dfn[w] < dfn[u])) then
            Add edge (u, w) to the top of the stack s;

        if (dfn[w] = 0) then  // If w is unvisited
        {
            BiComp(w, u);     // Recursively apply BiComp on w

            if (L[w] > dfn[u]) then  // Found a new biconnected component
            {
                write("New biconnected component:");
                repeat
                {
                    Delete an edge from the top of stack s;
                    Let this edge be (x, y);
                    write(x, y);   // Output the edges in the component
                } until (((x, y) = (u, w)) or ((x, y) = (w, u))); 
            }

            L[u] := min(L[u], L[w]);  // Update the lowest discovery time for u
        }
        elseif (w ≠ v) then
        {
            L[u] := min(L[u], dfn[w]);  // Update the lowest discovery time if w is already visited
        }
    }
}

import java.util.Scanner;

public class OBST {
    private double[][] w;
    private double[][] c;
    private int[][] r;

    public OBST(int n, double[] p, double[] q) {
        w = new double[n + 1][n + 1];
        c = new double[n + 1][n + 1];
        r = new int[n + 1][n + 1];

        for (int i = 0; i <= n; i++) {
            w[i][i] = q[i];
            r[i][i] = 0;
            c[i][i] = 0.0;

            if (i < n) {
                w[i][i + 1] = q[i] + q[i + 1] + p[i + 1];
                r[i][i + 1] = i + 1;
                c[i][i + 1] = w[i][i + 1];
            }
        }

        for (int m = 2; m <= n; m++) {
            for (int i = 0; i <= n - m; i++) {
                int j = i + m;
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                int k = findOptimalRoot(i, j);
                c[i][j] = w[i][j] + c[i][k - 1] + c[k][j];
                r[i][j] = k;
            }
        }
    }

    private int findOptimalRoot(int i, int j) {
        double minCost = Double.POSITIVE_INFINITY;
        int optimalRoot = i;

        for (int m = r[i][j - 1]; m <= r[i + 1][j]; m++) {
            double cost = c[i][m - 1] + c[m][j];
            if (cost < minCost) {
                minCost = cost;
                optimalRoot = m;
            }
        }

        return optimalRoot;
    }

    public void printResult() {
        System.out.println("Cost of Optimal BST: " + c[0][w.length - 1]);
        System.out.println("Root of Optimal BST: " + r[0][w.length - 1]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of keys: ");
        int n = scanner.nextInt();

        double[] p = new double[n + 1];
        double[] q = new double[n + 1];

        System.out.println("Enter the probabilities of keys (p[1] to p[" + n + "]):");
        for (int i = 1; i <= n; i++) {
            System.out.print("p[" + i + "]: ");
            p[i] = scanner.nextDouble();
        }

        System.out.println("Enter the probabilities of dummy keys (q[0] to q[" + n + "]):");
        for (int i = 0; i <= n; i++) {
            System.out.print("q[" + i + "]: ");
            q[i] = scanner.nextDouble();
        }

        OBST obst = new OBST(n, p, q);
        obst.printResult();

        scanner.close();
    }
}





ALGORITHM:
// Algorithm OBST(p, q, n)
// Given n distinct identifiers a1 < a2 < ... < an and probabilities
// p[i], 1 ≤ i ≤ n, and q[i], 0 ≤ i ≤ n, this algorithm computes
// the cost c[i, j] of optimal binary search trees tij for identifiers
// a[i+1],...,a[j]. It also computes r[i, j], the root of tij.
// w[i, j] is the weight of tij.

for i := 0 to n - 1 do
{
    // Initialize.
    w[i, i] := q[i]; r[i, i] := 0; c[i, i] := 0.0;
    // Optimal trees with one node
    w[i, i + 1] := q[i] + q[i + 1] + p[i + 1];
    r[i, i + 1] := i + 1;
    c[i, i + 1] := q[i] + q[i + 1] + p[i + 1];
}
w[n, n] := q[n]; r[n, n] := 0; c[n, n] := 0.0;
for m := 2 to n do // Find optimal trees with m nodes.
    for i := 0 to n - m do
    {
        j := i + m;
        w[i, j] := w[i, j - 1] + p[j] + q[j];
        // Solve 5.12 using Knuth's result.
        k := Find(c, r, i, j);
        // A value of l in the range r[i, j - 1] ≤ l ≤ r[i + 1, j] that minimizes c[i, l - 1] + c[l, j];
        c[i, j] := w[i, j] + c[i, k - 1] + c[k, j];
        r[i, j] := k;
    }
write (c[0, n], w[0, n], r[0, n]);

// Algorithm Find(c, r, i, j)
min := ∞;
for m := r[i, j - 1] to r[i + 1, j] do
    if (c[i, m - 1] + c[m, j]) < min then
    {
        min := c[i, m - 1] + c[m, j];
        l := m;
    }
return l;

import java.util.*;

class Job {
    int id, deadline, profit;

    Job(int id, int deadline, int profit) {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}

public class JobScheduling {

    public static int scheduleJobs(Job[] jobs, int n) {
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit);

        boolean[] slots = new boolean[n];
        int maxProfit = 0;

        for (Job job : jobs) {
            for (int j = Math.min(n, job.deadline) - 1; j >= 0; j--) {
                if (!slots[j]) {
                    slots[j] = true;
                    maxProfit += job.profit;
                    System.out.print("Job " + job.id + " ");
                    break;
                }
            }
        }

        System.out.println("\nMax Profit: " + maxProfit);
        return maxProfit;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of jobs: ");
        int n = sc.nextInt();
        Job[] jobs = new Job[n];

        for (int i = 0; i < n; i++) {
            System.out.print("Enter job ID, deadline, and profit: ");
            jobs[i] = new Job(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        scheduleJobs(jobs, n);
        sc.close();
    }
}




 GreedyJob(d, J, n)
{
    // J is the set of jobs that can be completed by their deadlines.
    J := {1};  // Start with the first job

    for i := 2 to n do
    {
        // Check if adding job i to the set J allows all jobs in J to be completed by their deadlines.
        if (all jobs in J ∪ {i} can be completed by their deadlines) then
        {
            J := J ∪ {i};  // Add job i to the set
        }
    }
}



 Algorithm JS(d, p, n)
// d[i] > 1, 1 ≤ i ≤ n are the deadlines, n > 1.
// The jobs are ordered such that p[1] > p[2] > ... > p[n].
// J[i] is the ith job in the optimal solution, 1 ≤ i ≤ k.
// At termination, d[J[i]] < d[J[i+1]], 1 ≤ i < k.
{
    rf[0] := J[0] := 0;  // Initialize.
    J[1] := 1;           // Include job 1 in the solution.
    k := 1;

    for i := 2 to n do
    {
        // Consider jobs in non-increasing order of profit p[i].
        // Find position for job i and check feasibility of insertion.
        r := k;

        while ((d[J[r]] > d[i]) and (d[J[r]] ≠ r)) do
        {
            r := r - 1;
        }

        if ((d[J[r]] < d[i]) and (d[i] > r)) then
        {
            // Insert job i into J[].
            for q := k to (r + 1) step -1 do
            {
                J[q + 1] := J[q];
            }
            J[r + 1] := i;
            k := k + 1;
        }
    }
    return k;
}

from sklearn.tree import DecisionTreeClassifier
from sklearn.preprocessing import LabelEncoder

df = pd.read_csv('/content/iris.csv')
df.info()
encoder = LabelEncoder()
df["variety"] = encoder.fit_transform(df["variety"])
df.info()
X = df.iloc[:,:-1] #df.drop(columns=["speices"])
y = df.iloc[:,-1] #df["species"]
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=42)
dtc = DecisionTreeClassifier()
dtc.fit(X_train,y_train)
y_pred = dtc.predict(X_test)
print(y_test,y_pred)


from sklearn.metrics import accuracy_score,classification_report,confusion_matrix

accuracy = accuracy_score(y_pred,y_test)
print(accuracy)
print(classification_report(y_pred,y_test))
print(confusion_matrix(y_pred,y_test))


# prompt: Visualize insights of Above decision tree classification on iris dataset
from sklearn import tree
import matplotlib.pyplot as plt

plt.figure(figsize=(15,10))
tree.plot_tree(dtc,filled=True,feature_names=X.columns,class_names=['0','1','2'])
plt.show()

1. Distance-based Pricing
A food delivery service charges a base fee of $2, plus $1.50 per mile for delivery. If the customer is 5 miles away, the fare will be:

Base Fare = $2
Distance Fare = $1.50 × 5 = $7.50
Total Fare = $2 + $7.50 = $9.50

2. Time-based Pricing
A grocery delivery service charges based on time taken. There’s a base fee of $3, plus $0.10 per minute for the duration of the delivery. If a delivery takes 45 minutes:

Base Fare = $3
Time Fare = $0.10 × 45 = $4.50
Total Fare = $3 + $4.50 = $7.50

3. Weight/Size-based Pricing
A furniture delivery service charges a base fee of $10, plus $2 per 10 lbs for items over 50 lbs. If a delivered item weighs 70 lbs:

Base Fare = $10
Weight Fare = $2 × 2 = $4
Total Fare = $10 + $4 = $14

4. Dynamic/Surge Pricing
A ride-sharing delivery charges a base fare of $5, with $2 per mile, but due to high demand, a surge multiplier of 1.5x is applied. For a 4-mile delivery:

Base Fare = $5
Distance Fare = $2 × 4 = $8
Surge Multiplier = 1.5
Total Fare = ($5 + $8) × 1.5 = $19.50

5. Zonal Pricing
A local courier service charges $10 for deliveries within Zone A and $15 for Zone B. If a delivery is in Zone B:

Zone Fare = $15
Total Fare = $15

6. Hybrid Pricing (Distance + Time)
A parcel delivery service charges a base fare of $3, $1 per mile, and $0.05 per minute. If a 10-mile delivery takes 30 minutes:

Base Fare = $3
Distance Fare = $1 × 10 = $10
Time Fare = $0.05 × 30 = $1.50
Total Fare = $3 + $10 + $1.50 = $14.50

7. Fuel Surcharge Additions
A delivery service charges $2 per mile, but also adds a $0.10 per mile fuel surcharge when fuel prices rise. For a 12-mile delivery:

Base Fare = $2 × 12 = $24
Fuel Surcharge = $0.10 × 12 = $1.20
Total Fare = $24 + $1.20 = $25.20

8. Crowdsourced/Bid-based Pricing
In a freelance courier platform, drivers bid for deliveries. A customer needs to deliver a package 5 miles away. Three drivers submit bids:

Driver 1: $15
Driver 2: $12
Driver 3: $18
The customer selects Driver 2’s bid of $12.

import java.util.Scanner;

public class Quick {
    
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low;
        int j = high;

        while (i < j) {
            while (i <= high && arr[i] <= pivot) {
                i++;
            }
            while (arr[j] > pivot) {
                j--;
            }
            if (i < j) {
                interchange(arr, i, j);
            }
        }

     
        interchange(arr, low, j);
        return j; 
    }


    public static void interchange(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int j = partition(arr, low, high);
            quickSort(arr, low, j - 1);
            quickSort(arr, j + 1, high);
        }
    }

   
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

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

        
        int[] arr = new int[n];
        System.out.println("Enter " + n + " elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

       
        System.out.println("Original array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();

        
        quickSort(arr, 0, arr.length - 1);

       
        System.out.println("Sorted array:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}




Algorithm Partition(a, m, p)
Within a[m], a[m+1],...,a[p-1] the elements are rearranged in such a manner that if initially t = a[m],
then after completion a[q] = t for some q between m and p-1, a[k] < t for m ≤ k < q, and a[k] ≥ t for q < k < p. q is returned. Set a[p] = ∞.
v := a[m]; i := m; j := p;
repeat
    repeat
        i := i + 1;
    until (a[i] ≥ v);
    repeat
        j := j - 1;
    until (a[j] < v);
    if (i < j) then
        Interchange(a, i, j);
} until (i ≥ j);

a[m] := a[j]; a[j] := v;
return j;

Algorithm Interchange(a, i, j)
// Exchange a[i] with a[j].
temp := a[i];
a[i] := a[j];
a[j] := temp;


Algorithm: QuickSort (p, q)

// Sorts the elements in the array a[p : q] in non-decreasing order.

if (p < q) then // If there is more than one element
{
    // Divide the array into two subproblems.
    j := Partition(a, p, q + 1);
    // 'j' is the position of the partitioning element.

    QuickSort(p, j - 1); // Sort the left subarray.
    QuickSort(j + 1, q); // Sort the right subarray.


OUTPUT:

Enter the size of the array: 5
Enter 5 elements:
9
3
7
1
5

Original array:
9 3 7 1 5 
Sorted array:
1 3 5 7 9

import java.util.Scanner;

public class Merge {
    public void merge(int arr[], int l, int m, int r) {
        int[] left = new int[m - l + 1];
        int[] right = new int[r - m];
        
        // Copy data into left[] and right[]
        System.arraycopy(arr, l, left, 0, left.length);
        System.arraycopy(arr, m + 1, right, 0, right.length);

        int i = 0, j = 0, k = l;
        
        // Merge the left and right arrays back into arr[]
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        // Copy remaining elements of left[], if any
        while (i < left.length) {
            arr[k++] = left[i++];
        }

        // Copy remaining elements of right[], if any
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    public void sort(int arr[], int l, int r) {
        if (l < r) {
            int mid = (l + r) / 2;
            sort(arr, l, mid);
            sort(arr, mid + 1, r);
            merge(arr, l, mid, r);
        }
    }

    public static void display(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Prompt user for array size
        System.out.print("Enter the size of the array: ");
        int n = scanner.nextInt();

        // Create array and input elements
        int[] arr = new int[n];
        System.out.println("Enter " + n + " elements:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        System.out.println("Original array:");
        display(arr);
        
        // Perform merge sort
        new Merge().sort(arr, 0, arr.length - 1);
        
        System.out.println("Sorted array:");
        display(arr);

        scanner.close();
    }
}


Algorithm:



Algorithm MergeSort(low, high)
    // a[low : high] is a global array to be sorted.
    // Small(P) is true if there is only one element to sort.
    // In this case, the list is already sorted.

    if (low < high) then  
        // Step 1: Divide the problem into subproblems
    {
        mid := ⌊(low + high) / 2⌋;  // Find where to split the set
        
        // Step 2: Solve the subproblems
        MergeSort(low, mid);
        MergeSort(mid + 1, high);

        // Step 3: Combine the solutions
        Merge(low, mid, high);
    }
}



Algorithm Merge (low, mid, high)
k := low; i := low; j := mid + 1;  
while ((i ≤ mid) and (j ≤ high)) do  
    if (a[i] ≤ a[j]) then  
    {  
        b[k] := a[i]; i := i + 1;  
    }  
    else  
    {  
        b[k] := a[j]; j := j + 1;  
    }  
    k := k + 1;  
end  

if (i > mid) then  
    for k := j to high do  
    {  
        b[k] := a[k]; i := i + 1;  
    }  
else  
    for k := i to mid do  
    {  
        b[k] := a[k]; i := i + 1;  
    }  

for k := low to high do a[k] := b[k];  



OUTPUT:
Enter the size of the array: 5
Enter 5 elements:
10
3
6
2
9
Original array:
10 3 6 2 9 
Sorted array:
2 3 6 9 10