Abhishek DAA

DATA SCIENCE LAB FILE
(LC-DS-345G)
V SEMESTER
CSE-DS ENGINEERING
Department of CSE-DS Engineering

DPG Institute of Technology and Management
Gurugram 122004 Haryana
Submitted BY: Submitted To:

Abhishek Ms Archana Rohilla
Roll. No: Ass. Professor
B.Tech(CSE-DS)-5th sem CSE Department
INDEX
RUBRICS
Evaluation Parameters Max Marks Marks Alotted
Attendance 5
Conduction of Program 10
Record Maintenance 5
Internal Viva 5
Total 25
Experiment 1
Program – Write a Program for Linear Search.
#include <iostream>
using namespace std;
// Function to perform linear search
int search(int array[], int n, int x) {
for (int i = 0; i < n; i++) {
if (array[i] == x) {
return i; // Return the index where the element is found
}
}
return -1; // Element not found
}
int main() {
int array[] = {2, 4, 7, 8, 0, 1, 9};
int x = 8;
int n = sizeof(array) / sizeof(array[0]); // Calculate the number of
elements in the array
int result = search(array, n, x); // Perform the search
if (result == -1) {
cout << "Element not found";
} else {
cout << "Element found at index: " << result;
}
return 0;
}
OUTPUT:
Element found at index: 3
Experiment 2
Program – Write a Program for Binary Search (Iterative Method).
// C++ program to implement iterative Binary Search

#include <bits/stdc++.h>
int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
if(result == -1) cout << "Element is not present in array";
else cout << "Element is present at index " << result;
return 0;
}
OUTPUT:
Element is present at index 3
Experiment 3
Program – Write a Program for Binary Search (Recursive Method).
#include <iostream>
// Recursive function for binary search
int binarySearch(int arr[], int left, int right, int target) {
if (right >= left) {
int mid = left + (right - left) / 2; // Find the middle index
if (arr[mid] == target)
return mid;
if (arr[mid] > target)
return binarySearch(arr, left, mid - 1, target);
return binarySearch(arr, mid + 1, right, target);
}
// Return -1 if the target is not present in the array
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40, 50, 70};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 10; // Element to search fo
int result = binarySearch(arr, 0, n - 1, target);
if (result != -1)
cout << "Element " << target << " found at index " << result <<
endl;
else
cout << "Element " << target << " not found in array" << endl;
return 0;
}
OUTPUT:
Element 10 found at index 3
Experiment 4
Program – Write a Program for Quick Sort.
// Quick sort in C++

#include <iostream>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
void printArray(int array[], int size) {
int i;
for (i = 0; i < size; i++)
cout << array[i] << " ";
cout << endl;
}
int partition(int array[], int low, int high) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (array[j] <= pivot) {
i++;
swap(&array[i], &array[j]);
}
}
swap(&array[i + 1], &array[high]);
return (i + 1);
}
void quickSort(int array[], int low, int high) {
if (low < high) {
int pi = partition(array, low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi + 1, high);
}
}
int main() {
int data[] = {8, 7, 6, 1, 0, 9, 2};
int n = sizeof(data) / sizeof(data[0]);
cout << "Unsorted Array: \n";
printArray(data, n);
quickSort(data, 0, n - 1);
cout << "Sorted array in ascending order: \n";
printArray(data, n);
}
OUTPUT:
Unsorted Array:
8761092
Sorted array in ascending order:
0126789
Experiment 5
Program – Write a Program for Merge Sort.
// Merge sort in C++

#include <iostream>
#include <vector>
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
vector<int> L(n1);
vector<int> M(n2);
for (int i = 0; i < n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];
int i = 0, j = 0, k = p;
while (i < n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = M[j];
j++;
}
k++;
}
while (i < n1) {

arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = M[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
int main() {
int arr[] = {6, 5, 12, 10, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
cout << "Sorted array: \n";
printArray(arr, size);
return 0;
}
OUTPUT:
Sorted array:
1 5 6 9 10 12
Experiment 6
Program – Write a Program for Fractional Knapsack.
#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
int value, weight;
Item(int v, int w) : value(v), weight(w) {}
};
bool compare(Item a, Item b) {
double r1 = (double) a.value / a.weight;
double r2 = (double) b.value / b.weight;
return r1 > r2;
}
double fractionalKnapsack(int capacity, vector<Item>& items) {
sort(items.begin(), items.end(), compare);
double totalValue = 0.0;
int currentWeight = 0;
for (Item& item : items) {
if (currentWeight + item.weight <= capacity) {
currentWeight += item.weight;
totalValue += item.value;
}
else {
int remainingCapacity = capacity - currentWeight;
totalValue += item.value * ((double) remainingCapacity /
item.weight);
break;
}
}
return totalValue;
}
int main() {
vector<Item> items = { {60, 10}, {100, 20}, {120, 30} };
int capacity = 50; // Knapsack capacity
double maxValue = fractionalKnapsack(capacity, items);
cout << "Maximum value in the knapsack = " << maxValue << endl;
return 0;
}
OUTPUT:
Maximum value in the knapsack = 240
Experiment 7
Program – Write a Program for 0/1 Knapsack.
#include <iostream>
#include <vector>
// Function to solve the 0/1 Knapsack problem using dynamic

programming
int knapsack(int capacity, vector<int>& weights, vector<int>& values,
int n) {
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], // Exclude the item
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][capacity];
}
int main() {
vector<int> values = {60, 100, 120};
vector<int> weights = {10, 20, 30};
int capacity = 50; // Knapsack capacity
int n = values.size(); // Number of items
int maxValue = knapsack(capacity, weights, values, n);
cout << "Maximum value in the knapsack = " << maxValue << endl;
return 0;
}
OUTPUT:
Maximum value in the knapsack = 220

Abhishek DAA

Uploaded by

Copyright:

Available Formats

Abhishek DAA

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Abhishek DAA

Uploaded by

Copyright:

Available Formats

DATA SCIENCE LAB FILE

Department of CSE-DS Engineering

Submitted BY: Submitted To:

Evaluation Parameters Max Marks Marks Alotted

// C++ program to implement iterative Binary Search

// Quick sort in C++

// Merge sort in C++

while (i < n1) {

using namespace std;

// Function to solve the 0/1 Knapsack problem using dynamic

You might also like