Experiment 1: Divide and Conquer Algorithm
Objective:
Implement a divide and conquer algorithm in Python to demonstrate efficiency on larger datasets.
Introduction:
Divide and conquer algorithms solve complex problems by breaking them down into smaller sub-problems,
solving these independently, and then combining their solutions. Merge Sort is a classic example that uses
this technique, sorting an array by recursively splitting it into halves, sorting each half, and merging the
results.
Code Implementation:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) //
2 left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i=j=k=0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
arr[k:] = left[i:] + right[j:]
Sample Input:
Input array: [38, 27, 43, 3, 9, 82, 10]
Expected Output:
Sorted array: [3, 9, 10, 27, 38, 43, 82]
Conclusion:
Divide and conquer algorithms like merge sort significantly improve efficiency on larger datasets compared
to O(n²) algorithms, due to their O(n log n) time complexity.
Observations:
Merge Sort consistently performs well on large datasets, maintaining stable performance regardless of the
input’s initial ordering.
Experiment 2: Application of Randomization in Algorithms
Objective:
Explore the use of randomization in algorithm design with a randomized quicksort.
Introduction:
Randomization introduces probabilistic behavior to algorithms, which can improve performance.
Randomized Quicksort, for example, selects pivots randomly to reduce the likelihood of worst-case O(n²)
performance.
Code Implementation:
import random
def randomized_quicksort(arr):
if len(arr) <= 1:
return arr
pivot = [Link](arr)
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return randomized_quicksort(less) + equal + randomized_quicksort(greater)
Sample Input:
Input array: [5, 3, 8, 4, 2, 7, 1]
Expected Output:
Sorted array (example): [1, 2, 3, 4, 5, 7, 8]
Conclusion:
Randomized Quicksort provides average-case O(n log n) performance, making it suitable for general use.
Observations:
The random pivot choice helps avoid consistently poor outcomes, resulting in reliable performance across
various input types.
Experiment 3: Breadth-First Search (BFS) Algorithm
Objective:
Implement the BFS algorithm for graph traversal in Python, exploring neighbors level-by-level.
Introduction:
Breadth-First Search (BFS) is a fundamental algorithm in graph theory used for traversing or searching
graph data structures. It’s particularly useful for finding shortest paths in unweighted graphs.
Code Implementation:
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
result = []
while queue:
vertex = [Link]()
[Link](vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)
return result
Sample Input:
Graph: {'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E']}
Start node: 'A'
Expected Output:
Traversal order: ['A', 'B', 'C', 'D', 'E', 'F']
Conclusion:
BFS effectively discovers the shortest path in unweighted graphs by exploring nodes level by level.
Observations:
BFS is highly efficient for level-order traversal in graphs, performing well in scenarios where shortest paths
are needed.
Experiment 4: Search Tree Data Structure
Objective:
Implement a search tree (Binary Search Tree) and evaluate its efficiency for various operations.
Introduction:
Search trees like Binary Search Trees (BSTs) are efficient data structures for ordered data. They support
efficient insertion, deletion, and search operations.
Code Implementation:
class Node:
def init (self, key):
[Link] = None
[Link] = None
[Link] = key
def insert(root, key):
if root is None:
return Node(key)
if key < [Link]:
[Link] = insert([Link], key)
else:
[Link] = insert([Link], key)
return root
Sample Input:
Insert sequence: [20, 10, 30, 5, 15, 25, 35]
Expected Output:
Binary Search Tree with root 20, and nodes arranged by BST properties.
Conclusion:
Binary Search Trees provide efficient access to ordered data, making them suitable for various applications
requiring sorted data retrieval.
Observations:
The efficiency of BST operations depends on the tree’s balance. Balanced trees offer better performance,
while unbalanced trees can degrade to linear search time.
Experiment 5:
Solving a Linear Programming Problem Related to Personal Genomics
Data Analysis
Objective:
Solve a linear programming problem to optimize resources or data related to personal genomics.
Introduction:
Linear programming (LP) is a method to achieve the best outcome (such as maximum profit or lowest cost)
within given constraints. In genomics, LP can optimize tasks like resource allocation or cost minimization in
genetic data processing.
Code Implementation:
from [Link] import linprog
# Objective function coefficients (for example, cost factors)
c = [-1, -2] # Maximize -x - 2y
# Constraints in matrix form (representing genetic data requirements)
A = [[2, 1], [1, 3]]
b = [20, 30] # Limits for constraints
# Bounds for x and y
bounds = [(0, None), (0, None)]
# Solve LP
result = linprog(c, A_ub=A, b_ub=b, bounds=bounds, method='simplex')
Sample Input:
Objective function: Maximize -x - 2y
Constraints:
2x + y <= 20
x + 3y <= 30
Bounds: x, y >= 0
Expected Output:
Optimal solution for x and y based on genetic data constraints.
Conclusion:
LP helps optimize decisions related to data analysis in genomics, such as minimizing data processing costs
or maximizing efficiency under constraints.
Observations:
Linear programming with SciPy simplifies solving complex optimization problems, applicable across
various domains, including genomics.
Experiment 6:
Understanding NP-Completeness Through a Practical Problem-Solving
Example
Objective:
Demonstrate NP-completeness by solving a problem like the subset-sum, which has applications in
cryptography and other fields.
Introduction:
NP-complete problems are computational problems with no known polynomial-time solutions. The subset-
sum problem, where we try to determine if there’s a subset with a given sum, is a classic example of an NP-
complete problem.
Code Implementation:
def is_subset_sum(arr, target):
n = len(arr)
dp = [[False] * (target + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = True
for i in range(1, n + 1):
for j in range(1, target + 1):
if arr[i - 1] <= j:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - arr[i - 1]]
else:
dp[i][j] = dp[i - 1][j]
return dp[n][target]
Sample Input:
Array: [3, 34, 4, 12, 5, 2]
Target sum: 9
Expected Output:
True (indicating a subset with sum 9 exists)
Conclusion:
NP-complete problems require exponential time solutions for exact answers. Approximate or heuristic
approaches are often used for large dataset
Observations:
Understanding NP-completeness helps identify problems that may need alternative strategies, such as
approximation algorithms, when exact solutions are infeasible.
Experiment 7: Implementing Logistic Regression on a Sample Dataset
Objective:
Implement logistic regression to classify data into categories based on a sample dataset.
Introduction:
Logistic regression is a classification algorithm that estimates probabilities and is widely used in binary
classification tasks.
Code Implementation:
from sklearn.model_selection import train_test_split
from sklearn.linear_model import LogisticRegression
from [Link] import accuracy_score
# Sample data (features and labels)
X = [[1, 2], [2, 3], [3, 4], [4, 5]]
y = [0, 0, 1, 1]
# Split data
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.5, random_state=0)
# Logistic Regression model
model = LogisticRegression()
[Link](X_train, y_train)
# Predict and evaluate
y_pred = [Link](X_test)
accuracy = accuracy_score(y_test, y_pred)
Sample Input:
Features: [[1, 2], [2, 3], [3, 4], [4, 5]]
Labels: [0, 0, 1, 1]
Expected Output:
Accuracy of the model on test data.
Conclusion:
Logistic regression is effective for binary classification problems, where it outputs probabilities and
classifies based on a threshold.
Observations:
With sufficient data, logistic regression achieves high accuracy, making it a reliable choice for binary
classification tasks.
Experiment 8:
Performing Model Selection Using Cross-Validation Techniques
Objective:
Use cross-validation to select the best model for a machine learning problem.
Introduction:
Cross-validation is a technique to evaluate models’ performance by dividing data into training and validation
sets multiple times. It helps in selecting the most suitable model and tuning hyperparameters.
Code Implementation:
from sklearn.model_selection import cross_val_score
from [Link] import RandomForestClassifier
# Sample data
X = [[1, 2], [2, 3], [3, 4], [4, 5]]
y = [0, 0, 1, 1]
# Model and cross-validation
model = RandomForestClassifier()
cv_scores = cross_val_score(model, X, y, cv=3)
Sample Input:
Data: Features [[1, 2], [2, 3], [3, 4], [4, 5]], Labels [0, 0, 1, 1]
Model: RandomForestClassifier
Expected Output:
Cross-validation scores across folds
Conclusion:
Cross-validation is essential for robust model evaluation, preventing overfitting by ensuring models
generalize well.
Observations:
Using cross-validation leads to a better understanding of model performance and aids in selecting the most
appropriate model.
Experiment 9: Implementing a Naive Bayes Probabilistic Model
Objective:
Implement a Naive Bayes classifier to predict categories based on sample data.
Introduction:
Naive Bayes is a probabilistic classifier that uses Bayes’ theorem with the assumption of feature
independence. It’s popular in text classification and spam detection.
Code Implementation:
from sklearn.naive_bayes import GaussianNB
from [Link] import accuracy_score
# Sample data
X = [[1, 2], [2, 3], [3, 4], [4, 5]]
y = [0, 0, 1, 1]
# Train model
model = GaussianNB()
[Link](X, y)
# Predict and evaluate
y_pred = [Link](X)
accuracy = accuracy_score(y, y_pred)
Sample Input:
Features: [[1, 2], [2, 3], [3, 4], [4, 5]]
Labels: [0, 0, 1, 1]
Expected Output:
Accuracy of the Naive Bayes model on sample data.
Conclusion:
Naive Bayes is effective for applications with high-dimensional data, where feature independence
assumption holds.
Observations:
Despite its simplicity, Naive Bayes performs well in various applications, especially with small datasets and
high dimensionality.
Experiment 10: Data Cleaning and Preprocessing for Machine Learning
Objective:
Clean and preprocess a real-world dataset for machine learning applications.
Introduction:
Data preprocessing involves handling missing values, encoding categorical variables, and scaling features.
Proper preprocessing ensures that the machine learning model interprets data accurately.
Code Implementation:
import pandas as pd
from [Link] import StandardScaler, LabelEncoder
# Sample dataset
data =
[Link]({ 'age':
[25, None, 35, 50],
'income': [50000, 60000, None, 80000],
'gender': ['M', 'F', 'M', 'F']
})
# Handle missing values
data['age'].fillna(data['age'].mean(), inplace=True)
data['income'].fillna(data['income'].median(),
inplace=True)
# Encode categorical variables
le = LabelEncoder()
data['gender'] = le.fit_transform(data['gender'])
# Scale numerical features
scaler = StandardScaler()
data[['age', 'income']] = scaler.fit_transform(data[['age', 'income']])
Sample Input:
Dataset with missing values and categorical variables.
Expected Output:
Cleaned and scaled dataset, ready for model training.
Conclusion:
Data preprocessing is crucial for enhancing the performance of machine learning models by ensuring data
consistency and reliability.
Observations:
Preprocessing steps vary based on the dataset, but techniques like scaling and encoding are universally
essential for model compatibility.