### Experiment 1(a) BFS
```bash
from collections import deque

class Graph:

    def __init__(self, directed=True):
        self.edges = {}
        self.directed = directed

    def add_edge(self, node1, node2, reversed=False):
        try:
            neighbors = self.edges[node1]
        except KeyError:
            neighbors = set()

        neighbors.add(node2)
        self.edges[node1] = neighbors

        if not self.directed and not reversed:
            self.add_edge(node2, node1, True)

    def neighbors(self, node):
        try:
            return self.edges[node]
        except KeyError:
            return []

    def breadth_first_search(self, start, goal):

        found, fringe, visited, came_from = (
            False,
            deque([start]),
            set([start]),
            {start: None}
        )

        print('{:11s} | {}'.format('Expand Node', 'Fringe'))
        print(' ' * 11 + '|')
        print('{:11s} | {}'.format('-', start))

        while not found and len(fringe):

            current = fringe.pop()

            print('{:11s}'.format(current), end=' | ')

            if current == goal:
                found = True
                break

            for node in self.neighbors(current):
                if node not in visited:
                    visited.add(node)
                    fringe.appendleft(node)
                    came_from[node] = current

            print(', '.join(fringe))

        if found:
            print()
            return came_from
        else:
            print('No path from {} to {}'.format(start, goal))

    @staticmethod
    def print_path(came_from, goal):

        parent = came_from[goal]

        if parent:
            Graph.print_path(came_from, parent)
        else:
            print(goal, end='')
            return

        print(' ->', goal, end='')

    def __str__(self):
        return str(self.edges)


graph = Graph(directed=False)

graph.add_edge('A', 'B')
graph.add_edge('A', 'S')
graph.add_edge('S', 'G')
graph.add_edge('S', 'C')
graph.add_edge('C', 'F')
graph.add_edge('G', 'F')
graph.add_edge('C', 'D')
graph.add_edge('C', 'E')
graph.add_edge('E', 'H')
graph.add_edge('G', 'H')

start, goal = 'A', 'H'

traced_path = graph.breadth_first_search(start, goal)

if traced_path:
    print('Path:', end=' ')
    Graph.print_path(traced_path, goal)
    print()

```

---

### Experiment 1(b) DFS

```bash 

from collections import deque

class Graph:

    def __init__(self, directed=True):
        self.edges = {}
        self.directed = directed

    def add_edge(self, node1, node2, reversed=False):
        try:
            neighbors = self.edges[node1]
        except KeyError:
            neighbors = set()

        neighbors.add(node2)
        self.edges[node1] = neighbors

        if not self.directed and not reversed:
            self.add_edge(node2, node1, True)

    def neighbors(self, node):
        try:
            return self.edges[node]
        except KeyError:
            return []

    def breadth_first_search(self, start, goal):

        found, fringe, visited, came_from = (
            False, deque([start]), set([start]), {start: None}
        )

        print('{:11s} | {}'.format('Expand Node', 'Fringe'))
        print(' ' * 11 + '|')
        print('{:11s} | {}'.format('-', start))

        while not found and len(fringe):

            current = fringe.pop()

            print('{:11s}'.format(current), end=' | ')

            if current == goal:
                found = True
                break

            for node in self.neighbors(current):
                if node not in visited:
                    visited.add(node)
                    fringe.appendleft(node)
                    came_from[node] = current

            print(', '.join(fringe))

        if found:
            print()
            return came_from
        else:
            print('No path from {} to {}'.format(start, goal))

    @staticmethod
    def print_path(came_from, goal):

        parent = came_from[goal]

        if parent:
            Graph.print_path(came_from, parent)
        else:
            print(goal, end='')
            return

        print(' =>', goal, end=' ')

    def __str__(self):
        return str(self.edges)


graph = Graph(directed=False)

graph.add_edge('A', 'B')
graph.add_edge('A', 'S')
graph.add_edge('S', 'G')
graph.add_edge('S', 'C')
graph.add_edge('C', 'F')
graph.add_edge('G', 'F')
graph.add_edge('C', 'D')
graph.add_edge('C', 'E')
graph.add_edge('E', 'H')
graph.add_edge('G', 'H')

start, goal = 'A', 'H'

traced_path = graph.breadth_first_search(start, goal)

if traced_path:
    print('Path:', end=' ')
    Graph.print_path(traced_path, goal)
    print()
```

---

### EXPERIMENT 2(a) Implementation of Informed search Algorithm (A*, Memory-bounded A *)

```bash

def aStarAlgo(start_node, stop_node):

    open_set = set(start_node)
    closed_set = set()
    g = {}
    parents = {}

    g[start_node] = 0
    parents[start_node] = start_node

    while len(open_set) > 0:

        n = None

        for v in open_set:
            if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
                n = v

        if n == stop_node or Graph_nodes[n] == None:
            pass
        else:
            for (m, weight) in get_neighbors(n):

                if m not in open_set and m not in closed_set:
                    open_set.add(m)
                    parents[m] = n
                    g[m] = g[n] + weight

                else:
                    if g[m] > g[n] + weight:
                        g[m] = g[n] + weight
                        parents[m] = n

                        if m in closed_set:
                            closed_set.remove(m)
                            open_set.add(m)

        if n == None:
            print('Path does not exist!')
            return None

        if n == stop_node:
            path = []

            while parents[n] != n:
                path.append(n)
                n = parents[n]

            path.append(start_node)
            path.reverse()

            print('Path found: {}'.format(path))
            return path

        open_set.remove(n)
        closed_set.add(n)

    print('Path does not exist!')
    return None


# Define function to return neighbor and its distance
# from the passed node

def get_neighbors(v):
    if v in Graph_nodes:
        return Graph_nodes[v]
    else:
        return None


# Heuristic distance for all nodes

def heuristic(n):
    H_dist = {
        'A': 10,
        'B': 8,
        'C': 5,
        'D': 7,
        'E': 3,
        'F': 6,
        'G': 5,
        'H': 3,
        'I': 1,
        'J': 0
    }

    return H_dist[n]


# Describe your graph here

Graph_nodes = {
    'A': [('B', 6), ('F', 3)],
    'B': [('C', 3), ('D', 2)],
    'C': [('D', 1), ('E', 5)],
    'D': [('C', 1), ('E', 8)],
    'E': [('I', 5), ('J', 5)],
    'F': [('C', 1), ('G', 7)],
    'G': [('I', 3)],
    'H': [('I', 2)],
    'I': [('E', 5), ('J', 3)]
}

aStarAlgo('A', 'J')
```
---
### Experiment 2(b) 
```bash 


class Graph:

    def __init__(self, graph, heuristicNodeList, startNode):
        # instantiate graph object with graph topology,
        # heuristic values, and start node
        self.graph = graph
        self.H = heuristicNodeList
        self.start = startNode
        self.parent = {}
        self.status = {}
        self.solutionGraph = {}

    def applyAOStar(self):
        # starts a recursive AO* algorithm
        self.aoStar(self.start, False)

    def getNeighbors(self, v):
        # gets the neighbors of a given node
        return self.graph.get(v, '')

    def getStatus(self, v):
        # return the status of a given node
        return self.status.get(v, 0)

    def setStatus(self, v, val):
        # set the status of a given node
        self.status[v] = val

    def getHeuristicNodeValue(self, n):
        # always return the heuristic value of a given node
        return self.H.get(n, 0)

    def setHeuristicNodeValue(self, n, value):
        # set the revised heuristic value of a given node
        self.H[n] = value

    def printSolution(self):
        print("FOR GRAPH SOLUTION, TRAVERSE THE GRAPH FROM THE STARTNODE:",
              self.start)
        print(" ")
        print(self.solutionGraph)
        print(" ")

    def computeMinimumCostChildNodes(self, v):
        # Computes the Minimum Cost of child nodes of a given node v

        minimumCost = 0
        costToChildNodeListDict = {}
        costToChildNodeListDict[minimumCost] = []
        flag = True

        # iterate over all the set of child node/s
        for nodeInfoTupleList in self.getNeighbors(v):
            cost = 0
            nodeList = []

            for c, weight in nodeInfoTupleList:
                cost = cost + self.getHeuristicNodeValue(c) + weight
                nodeList.append(c)

            # initialize Minimum Cost with the cost of first set
            # of child nodes
            if flag == True:
                minimumCost = cost
                costToChildNodeListDict[minimumCost] = nodeList
                flag = False

            else:
                # checking the Minimum Cost nodes with the
                # current Minimum Cost
                if minimumCost > cost:
                    minimumCost = cost
                    costToChildNodeListDict[minimumCost] = nodeList

        # return Minimum Cost and Minimum Cost child node/s
        return minimumCost, costToChildNodeListDict[minimumCost]

    def aoStar(self, v, backTracking):
        # AO* algorithm for a start node and backtracking status flag

        print("HEURISTIC VALUES :", self.H)
        print("SOLUTION GRAPH :", self.solutionGraph)
        print("PROCESSING NODE :", v)
        print(" ")

        # If status node v >= 0, compute Minimum Cost nodes of v
        if self.getStatus(v) >= 0:

            minimumCost, childNodeList = \
                self.computeMinimumCostChildNodes(v)

            self.setHeuristicNodeValue(v, minimumCost)
            self.setStatus(v, len(childNodeList))

            solved = True

            # check the Minimum Cost nodes of v are solved
            for childNode in childNodeList:
                self.parent[childNode] = v

                if self.getStatus(childNode) != -1:
                    solved = solved & False

            # if the Minimum Cost nodes of v are solved,
            # set the current node status as solved(-1)
            if solved == True:
                self.setStatus(v, -1)

            # update the solution graph with the solved nodes
            self.solutionGraph[v] = childNodeList

            # check the current node is not the start node
            if v != self.start:
                # backtracking the current node value
                self.aoStar(self.parent[v], True)

            # check the current call is not for backtracking
            if backTracking == False:

                # for each Minimum Cost child node
                for childNode in childNodeList:
                    # set status of child node to 0
                    self.setStatus(childNode, 0)

                    # Minimum Cost child node is further explored
                    self.aoStar(childNode, False)


h1 = {
    'A': 1,
    'B': 6,
    'C': 2,
    'D': 12,
    'E': 2,
    'F': 1,
    'G': 5,
    'H': 7,
    'I': 7,
    'J': 1,
    'T': 3
}

graph1 = {
    'A': [[('B', 1), ('C', 1)], [('D', 1)]],
    'B': [[('G', 1)], [('H', 1)]],
    'C': [[('J', 1)]],
    'D': [[('E', 1), ('F', 1)]],
    'G': [[('I', 1)]]
}

G1 = Graph(graph1, h1, 'A')
G1.applyAOStar()
G1.printSolution()


h2 = {
    'A': 1,
    'B': 6,
    'C': 12,
    'D': 10,
    'E': 4,
    'F': 4,
    'G': 5,
    'H': 7
}

graph2 = {
    'A': [[('B', 1), ('C', 1)], [('D', 1)]],
    'B': [[('G', 1)], [('H', 1)]],
    'D': [[('E', 1), ('F', 1)]]
}

G2 = Graph(graph2, h2, 'A')
G2.applyAOStar()
G2.printSolution()

```
---
---

### Experiment 3 (EXP 3 Find Goal by Deepening Depth First Search (DFID) Algorithm)

```bash 
def depth_limited_search(graph, node, goal, depth, path):
    path.append(node)

    if node == goal:
        return path

    if depth == 0:
        path.pop()
        return None

    for neighbor in graph.get(node, []):
        if neighbor not in path:
            result = depth_limited_search(
                graph, neighbor, goal, depth - 1, path
            )
            if result:
                return result

    path.pop()
    return None


def deepening_depth_first_search(graph, start, goal):
    depth = 0

    while True:
        path = []
        result = depth_limited_search(
            graph, start, goal, depth, path
        )

        print("Depth Limit:", depth)

        if result:
            print("Goal Found")
            print("Path:", " -> ".join(result))
            return result

        depth += 1


graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H'],
    'E': ['I'],
    'F': ['J'],
    'G': ['K'],
    'H': [],
    'I': [],
    'J': [],
    'K': []
}

start = 'A'
goal = 'J'

deepening_depth_first_search(graph, start, goal)
```


---
### Experiment 4 Predicting house prices by Linear Regression

```bash
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LinearRegression
from sklearn.compose import ColumnTransformer
from sklearn.preprocessing import OneHotEncoder
from sklearn.pipeline import Pipeline
from sklearn.metrics import mean_absolute_error, r2_score

# Load dataset directly from URL
url = "https://raw.githubusercontent.com/MartinJessenne/Housing-Price-Prediction-Kaggle-Dataset/main/Housing.csv"
df = pd.read_csv(url)

print("Dataset Shape:", df.shape)
print("\nFirst 5 Records:")
print(df.head())

# Separate input and output
X = df.drop("price", axis=1)
y = df["price"]

# Identify categorical and numerical columns
categorical_cols = X.select_dtypes(include=["object"]).columns
numerical_cols = X.select_dtypes(exclude=["object"]).columns

# Preprocess categorical data
preprocessor = ColumnTransformer(
    transformers=[
        ("cat", OneHotEncoder(handle_unknown="ignore"), categorical_cols),
        ("num", "passthrough", numerical_cols)
    ]
)

# Create Linear Regression model
model = Pipeline([
    ("preprocessor", preprocessor),
    ("regressor", LinearRegression())
])

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

# Train model
model.fit(X_train, y_train)

# Predict house prices
y_pred = model.predict(X_test)

# Evaluate model
print("\nMean Absolute Error:", mean_absolute_error(y_test, y_pred))
print("R2 Score:", r2_score(y_test, y_pred))

# Predict price for a new house
new_house = pd.DataFrame([{
    "area": 5000,
    "bedrooms": 3,
    "bathrooms": 2,
    "stories": 2,
    "mainroad": "yes",
    "guestroom": "no",
    "basement": "no",
    "hotwaterheating": "no",
    "airconditioning": "yes",
    "parking": 1,
    "prefarea": "yes",
    "furnishingstatus": "furnished"
}])

predicted_price = model.predict(new_house)

print("\nPredicted House Price:", round(predicted_price[0], 2))
```

---
### Experiment 5 K-Nearest Neighbour (KNN) Classification of Iris Dataset 

```bash 
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

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

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

print("Feature Names:")
print(iris.feature_names)

print("\nTarget Names:")
print(iris.target_names)

print("\nDataset Shape:")
print(X.shape)

df = pd.DataFrame(X, columns=iris.feature_names)
df['target'] = y
print(df.head())

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

print("Training samples:", X_train.shape[0])
print("Testing samples:", X_test.shape[0])

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

print("Feature scaling completed.")

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train)
print("KNN model trained successfully.")

y_pred = knn.predict(X_test)
print("Predicted values:")
print(y_pred)

accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)
print("Accuracy Percentage:", accuracy * 100, "%")

cm = confusion_matrix(y_test, y_pred)
print("Confusion Matrix:")
print(cm)

plt.figure(figsize=(6, 5))
plt.imshow(cm)
plt.title("Confusion Matrix - KNN")
plt.xlabel("Predicted Class")
plt.ylabel("Actual Class")
plt.xticks([0, 1, 2], iris.target_names)
plt.yticks([0, 1, 2], iris.target_names)

for i in range(3):
    for j in range(3):
        plt.text(j, i, cm[i, j], ha='center', va='center')

plt.colorbar()
plt.show()

print("Classification Report:")
print(classification_report(
    y_test, y_pred, target_names=iris.target_names
))

k_values = range(1, 16)
accuracy_values = []

for k in k_values:
    model = KNeighborsClassifier(n_neighbors=k)
    model.fit(X_train, y_train)
    prediction = model.predict(X_test)
    accuracy_values.append(accuracy_score(y_test, prediction))

print("K values:")
print(list(k_values))
print("\nAccuracy values:")
print(accuracy_values)

plt.figure(figsize=(8, 5))
plt.plot(k_values, accuracy_values, marker='o')
plt.xlabel("Value of K")
plt.ylabel("Accuracy")
plt.title("KNN Accuracy for Different K Values")
plt.xticks(list(k_values))
plt.grid()
plt.show()

best_k = list(k_values)[np.argmax(accuracy_values)]
best_accuracy = max(accuracy_values)

print("Best K:", best_k)
print("Best Accuracy:", best_accuracy)
print("Best Accuracy Percentage:", best_accuracy * 100, "%")

final_knn = KNeighborsClassifier(n_neighbors=best_k)
final_knn.fit(X_train, y_train)
final_prediction = final_knn.predict(X_test)
final_accuracy = accuracy_score(y_test, final_prediction)

print("Final K:", best_k)
print("Final Accuracy:", final_accuracy)
print("Final Accuracy Percentage:", final_accuracy * 100, "%")

new_flower = [[5.1, 3.5, 1.4, 0.2]]
new_flower_scaled = scaler.transform(new_flower)
prediction = final_knn.predict(new_flower_scaled)

print("Predicted Class:", iris.target_names[prediction[0]])
```
---

### Experiment 6(a) Random Forest 

```bash 
#RANDOM FOREST EXPERIMENT 6

import pandas as pd

from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.compose import ColumnTransformer
from sklearn.preprocessing import OneHotEncoder
from sklearn.pipeline import Pipeline
from sklearn.impute import SimpleImputer
from sklearn.metrics import accuracy_score, classification_report

# Load dataset directly from URL
url = "https://raw.githubusercontent.com/fejiso/Coronavirus-Dataset/master/patient.csv"
data = pd.read_csv(url)

print("First 5 Records:")
print(data.head())

print("\nDataset Information:")
print(data.info())

# Remove columns not suitable for prediction
data = data.drop(
    columns=["id", "confirmed_date", "released_date", "deceased_date"],
    errors="ignore"
)

# Remove rows where target is missing
data = data.dropna(subset=["state"])

# Separate input and target
X = data.drop("state", axis=1)
y = data["state"]

# Identify categorical and numerical columns
cat_cols = X.select_dtypes(include=["object"]).columns
num_cols = X.select_dtypes(exclude=["object"]).columns

# Preprocessing
preprocessor = ColumnTransformer([
    ("num", SimpleImputer(strategy="median"), num_cols),
    ("cat", Pipeline([
        ("imputer", SimpleImputer(strategy="most_frequent")),
        ("encoder", OneHotEncoder(handle_unknown="ignore"))
    ]), cat_cols)
])

# Random Forest model
model = Pipeline([
    ("preprocessor", preprocessor),
    ("classifier", RandomForestClassifier(
        n_estimators=100,
        random_state=42
    ))
])

# Split dataset
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# Train model
model.fit(X_train, y_train)

# Prediction
y_pred = model.predict(X_test)

# Results
print("\nAccuracy:", accuracy_score(y_test, y_pred))
print("\nClassification Report:")
print(classification_report(y_test, y_pred, zero_division=0))
```

---
### Experiment 6(b) Decision Tree

```bash 
import pandas as pd

from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
from sklearn.preprocessing import LabelEncoder
from sklearn.metrics import accuracy_score, classification_report, confusion_matrix

# Load dataset directly from URL
url = "https://raw.githubusercontent.com/fejiso/Coronavirus-Dataset/master/patient.csv"

data = pd.read_csv(url)

print("Dataset loaded successfully!")
print(data.head())

# Remove unnecessary columns
data = data.drop(
    columns=["id", "confirmed_date", "released_date", "deceased_date"],
    errors="ignore"
)

# Remove rows with missing target values
data = data.dropna(subset=["state"])

# Handle missing values
for col in data.columns:
    if data[col].dtype == "object":
        data[col] = data[col].fillna("Unknown")
    else:
        data[col] = data[col].fillna(data[col].median())

# Encode categorical columns
encoder = LabelEncoder()

for col in data.select_dtypes(include=["object"]).columns:
    data[col] = encoder.fit_transform(data[col].astype(str))

# Separate features and target
X = data.drop("state", axis=1)
y = data["state"]

# Split dataset
X_train, X_test, y_train, y_test = train_test_split(
    X, y,
    test_size=0.2,
    random_state=42,
    stratify=y
)

# Create Decision Tree model
model = DecisionTreeClassifier(
    criterion="entropy",
    random_state=42
)

# Train model
model.fit(X_train, y_train)

# Make predictions
y_pred = model.predict(X_test)

# Evaluate model
print("\nAccuracy:", accuracy_score(y_test, y_pred))

print("\nConfusion Matrix:")
print(confusion_matrix(y_test, y_pred))

print("\nClassification Report:")
print(classification_report(y_test, y_pred, zero_division=0))

# Display feature importance
print("\nFeature Importance:")
print(pd.Series(
    model.feature_importances_,
    index=X.columns
).sort_values(ascending=False))
```

------

### Experiment 7 Implement Naive Bayes Models

```bash
# Import necessary libraries
import pandas as pd
from sklearn.preprocessing import LabelEncoder
from sklearn.naive_bayes import GaussianNB
from sklearn.metrics import accuracy_score, confusion_matrix

# Load dataset directly from URL
url = "https://raw.githubusercontent.com/AshishVajpayee/VTU-AIML-Lab-Programs/master/NaiveBayesianLab6/tennisdata.csv"

data = pd.read_csv(url)

print("The first 5 Values of data are:\n")
print(data.head())

# Obtain training data and output
X = data.iloc[:, :-1]

print("\nThe First 5 values of the train data are:\n")
print(X.head())

y = data.iloc[:, -1]

print("\nThe First 5 values of train output are:\n")
print(y.head())

# Encode categorical data
le = LabelEncoder()

for col in X.columns:
    X[col] = le.fit_transform(X[col])

y = le.fit_transform(y)

# Train the Naive Bayes model
model = GaussianNB()
model.fit(X, y)

# Predict output
y_pred = model.predict(X)

print("\nActual Output:")
print(y)

print("\nPredicted Output:")
print(y_pred)

# Calculate accuracy
print("\nAccuracy:", accuracy_score(y, y_pred))

# Confusion Matrix
print("\nConfusion Matrix:")
print(confusion_matrix(y, y_pred))

# Test a new sample
new_data = pd.DataFrame([{
    "Outlook": "Sunny",
    "Temperature": "Cool",
    "Humidity": "High",
    "Windy": "Strong"
}])

# Encode new sample using the training categories
for col in X.columns:
    new_data[col] = le.fit_transform(
        pd.concat([data[col], new_data[col]]).astype(str)
    )[-1:]

prediction = model.predict(new_data)

print("\nNew Sample Prediction:",
      "Yes" if prediction[0] == 1 else "No")
```

---