DIGITAL ASSISGNMENT

DAA

ADYANT GUPTA

22BCE2473

1. #include <iostream>

#include <algorithm>

using namespace std;

void printMaxActivities(int s[], int f[], int n) {

// Sort activities

sort(f, f+n);

// Print first activity

int i = 0;

cout << i << " ";

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

if(s[j] >= f[i]) {

cout << j << " ";

i = j;

cout << endl;

int main() {
int n;

cin >> n;

int s[n], f[n];

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

cin >> s[i];

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

cin >> f[i];

printMaxActivities(s, f, n);

return 0;
}
2. #include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct Meeting {

int index, start, end;

};

bool compareMeetings(const Meeting &a, const Meeting &b) {

return a.end < b.end;

void printMaxMeetings(int n, vector<int> &start, vector<int> &end) {

vector<Meeting> meetings;

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

meetings.push_back({i + 1, start[i], end[i]});

sort(meetings.begin(), meetings.end(), compareMeetings);

vector<Meeting> result;

int endTime = meetings[0].end;

result.push_back(meetings[0]);

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

if (meetings[i].start >= endTime) {

result.push_back(meetings[i]);

endTime = meetings[i].end;

for (const auto &meeting : result) {

cout << meeting.start << " " << meeting.end << endl;

int main() {

int N;
 cin >> N;

vector<int> startTime(N), endTime(N);

for (int i = 0; i < N; ++i) {

cin >> startTime[i];

for (int i = 0; i < N; ++i) {

cin >> endTime[i];

printMaxMeetings(N, startTime, endTime);

return 0;

3. #include <iostream>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

class Node {

public:

char data;

int freq;

Node* left;

Node* right;
 Node(char d, int f) {

data = d;

freq = f;

left = nullptr;

right = nullptr;

};

struct CompareNodes {

bool operator()(Node* const& n1, Node* const& n2) {

return n1->freq > n2->freq;

};

void generateCodes(Node* root, string code, vector<pair<char, string>>& result) {

if (root == nullptr) {

return;

if (root->data != '\0') {

result.push_back({root->data, code});

return;

generateCodes(root->left, code + "0", result);

generateCodes(root->right, code + "1", result);

vector<pair<char, string>> huffmanCodes(string S, int f[], int N) {

priority_queue<Node*, vector<Node*>, CompareNodes> minHeap;

for (int i = 0; i < N; i++) {

minHeap.push(new Node(S[i], f[i]));

while (minHeap.size() > 1) {

Node* left = minHeap.top();

minHeap.pop();
 Node* right = minHeap.top();

minHeap.pop();

Node* internalNode = new Node('\0', left->freq + right->freq);

internalNode->left = left;

internalNode->right = right;

minHeap.push(internalNode);

vector<pair<char, string>> result;

generateCodes(minHeap.top(), "", result);

return result;

int main() {

string S;

cin >> S;

int N = S.length();

int f[N];

for (int i = 0; i < N; i++) {

cin >> f[i];

vector<pair<char, string>> output = huffmanCodes(S, f, N);

for (const auto& code : output) {

cout << code.first << " " << code.second << endl;

return 0;
}

4. #include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct Item {

int weight;

int value;

double ratio;

int index;

Item(int w, int v, int i) : weight(w), value(v), index(i) {

ratio = (weight == 0) ? 0 : (double)value / weight;

};

bool compare(Item i1, Item i2) {

return i1.ratio > i2.ratio;

void fractionalKnapsack(int N, vector<int>& weights, vector<int>& values, int W) {

vector<Item> items;

for (int i = 0; i < N; ++i) {

items.push_back(Item(weights[i], values[i], i + 1));

sort(items.begin(), items.end(), compare);

vector<pair<int, double>> knapsack;

for (const auto& item : items) {

if (W >= item.weight && item.weight != 0) {

knapsack.push_back({item.weight, item.value});

totalValue += item.value;

W -= item.weight;

} else if (W > 0 && item.weight != 0) {

double fraction = (double)W / item.weight;

knapsack.push_back({W, fraction * item.value});

totalValue += fraction * item.value;

break;

for (const auto& item : knapsack) {

cout << item.first << " " << item.second << endl;

cout << "Total Profit: " <<totalValue << endl;

int main() {

int N;

cin >> N;

vector<int> weights(N);

vector<int> values(N);

for (int i = 0; i < N; ++i) {

cin >> weights[i];

for (int i = 0; i < N; ++i) {

cin >> values[i];

int W;
 cin >> W;

fractionalKnapsack(N, weights, values, W);

return 0;

5. #include <iostream>

#include <vector>

using namespace std;

vector<int> subarraySum(int arr_size, int target_sum, const vector<int>& array_elements) {

int current_sum = 0;

int start = 0;

int end = 0;

while (end < arr_size || current_sum >= target_sum) {

if (current_sum == target_sum) {

return {start + 1, end};

} else if (current_sum < target_sum && end < arr_size) {

current_sum += array_elements[end];

end++;

} else {

current_sum -= array_elements[start];

start++;

return {-1};

}
int main() {

int arr_size, target_sum;

cin >> arr_size >> target_sum;

vector<int> array_elements(arr_size);

for (int i = 0; i < arr_size; i++) {

cin >> array_elements[i];

vector<int> result = subarraySum(arr_size, target_sum, array_elements);

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

cout << result[i] << " ";

return 0;

6. #include <iostream>

using namespace std;

// Returns maximum sum in a subarray of size k.

int maxSum(int arr[], int n, int k)

// k must be smaller than n

if (n < k)

cout << "Invalid";

return -1;

}
 // Compute sum of first window of size k

int res = 0;

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

res += arr[i];

// Compute sums of remaining windows by

// removing first element of previous

// window and adding last element of

// current window.

int curr_sum = res;

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

curr_sum += arr[i] - arr[i-k];

res = max(res, curr_sum);

return res;

// Driver code

int main()

int n;

int k;

cin >> n >>k;

int arr[n];

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

cin >> arr[i];

cout << maxSum(arr, n, k);

return 0;
}

7. #include <stdio.h>

#include <iostream>

#include <math.h>

using namespace std;

int getSize(long num)

int count = 0;

while (num > 0)

count++;

num /= 10;

return count;
}

long long karatsuba(long long X, long long Y)

if (X < 10 && Y < 10)

return X * Y;

int size = fmax(getSize(X), getSize(Y));

cout << "X:" << X << ", "

<< "Y:" << Y << endl;

int n = (int)ceil(size / 2.0);

long p = (long)pow(10, n);

long a = (long)floor(X / (double)p);

cout << "x1=" << a << " ";

long b = X % p;

cout << "x2=" << b << " ";

long c = (long)floor(Y / (double)p);

cout << "y1=" << c << " ";

long d = Y % p;

cout << "y2=" << d << endl;

cout << endl;

long ac = karatsuba(a, c);

long bd = karatsuba(b, d);

long e = karatsuba(a + b, c + d) - ac - bd;

long long jk = (pow(10 * 1L, 2 * n) * ac + pow(10 * 1L, n) * e + bd);

cout << "a=" << ac << " "

<< "b=" << e << " "

cout << "xy: " << jk << endl;

cout << endl;

return (long long)(pow(10 * 1L, 2 * n) * ac + pow(10 * 1L, n) * e + bd);

int main()

long long a, b;

cin >> a >> b;

long long c = karatsuba(a, b);

cout << a << " * " << b << " = " << c;

return 0;