PROGRAM – 1 Implement skip lists and measure performance compared with balanced BST.

A skip list is a probabilistic data structure that allows for efficient search, insertion, and
deletion operations with an average time complexity of O(log n), similar to balanced
trees, but with a simpler implementation. It achieves this by maintaining multiple levels
of sorted linked lists, where higher levels act as "express lanes" to skip over elements.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // For INT_MIN
#include <time.h> // For srand and time

#define MAX_LEVEL 6 // Maximum level of the skip list

// Node structure
typedef struct Node {
int key;
struct Node *forward[MAX_LEVEL]; // Array of pointers for different levels
} Node;

// SkipList structure
typedef struct SkipList {
Node *header; // Pointer to the header node
int level; // Current highest level in the skip list
} SkipList;

// Function to create a new node

Node* createNode(int key, int level) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
perror("Memory allocation failed for node");
exit(EXIT_FAILURE);
}
newNode->key = key;
for (int i = 0; i < level; i++) {
newNode->forward[i] = NULL;
}
return newNode;
}

// Function to create a new skip list

SkipList* createSkipList() {
SkipList *list = (SkipList*)malloc(sizeof(SkipList));
if (list == NULL) {
perror("Memory allocation failed for skip list");
exit(EXIT_FAILURE);
}
list->header = createNode(INT_MIN, MAX_LEVEL); // Header node with a minimum key
 list->level = 0;
return list;
}

// Function to generate a random level for a new node

int randomLevel() {
int level = 0;
// Simulate a coin flip: promote to next level with 50% probability
while (rand() < RAND_MAX / 2 && level < MAX_LEVEL - 1) {
level++;
}
return level;
}

// Function to insert a key into the skip list

void insertNode(SkipList *list, int key) {
Node *current = list->header;
Node *update[MAX_LEVEL]; // Array to store nodes where we drop down a level

// Traverse from the highest level down to find insertion point

for (int i = list->level; i >= 0; i--) {
while (current->forward[i] != NULL && current->forward[i]->key < key) {
current = current->forward[i];
}
update[i] = current; // Store the node before dropping down
}

current = current->forward[0]; // Move to the node at level 0

// If key already exists, do nothing or update its value (if storing values)
if (current != NULL && current->key == key) {
printf("Key %d already exists.\n", key);
return;
}

// Generate a random level for the new node

int rlevel = randomLevel();

// If the new node's level is higher than the current highest level of the list,
// extend the header's forward pointers
if (rlevel > list->level) {
for (int i = list->level + 1; i <= rlevel; i++) {
update[i] = list->header;
}
list->level = rlevel; // Update the list's highest level
}
 // Create the new node
Node *newNode = createNode(key, rlevel + 1); // +1 because levels are 0-indexed

// Insert the new node by adjusting pointers at all its levels

for (int i = 0; i <= rlevel; i++) {
newNode->forward[i] = update[i]->forward[i];
update[i]->forward[i] = newNode;
}
printf("Successfully inserted key %d.\n", key);
}

// Function to search for a key in the skip list

Node* searchNode(SkipList *list, int key) {
Node *current = list->header;

// Traverse from the highest level down

for (int i = list->level; i >= 0; i--) {
while (current->forward[i] != NULL && current->forward[i]->key < key) {
current = current->forward[i];
}
}

current = current->forward[0]; // Move to the node at level 0

if (current != NULL && current->key == key) {

return current; // Key found
} else {
return NULL; // Key not found
}
}

// Function to delete a key from the skip list

void deleteNode(SkipList *list, int key) {
Node *current = list->header;
Node *update[MAX_LEVEL];

for (int i = list->level; i >= 0; i--) {

while (current->forward[i] != NULL && current->forward[i]->key < key) {
current = current->forward[i];
}
update[i] = current;
}

current = current->forward[0];

if (current != NULL && current->key == key) {

// Remove the node from all levels it exists in
 for (int i = 0; i <= list->level; i++) {
if (update[i]->forward[i] != current) {
// If update[i] does not point to current, it means current is not at this level
continue;
}
update[i]->forward[i] = current->forward[i];
}
free(current); // Free the memory of the deleted node
printf("Successfully deleted key %d.\n", key);

// Adjust the list's highest level if necessary

while (list->level > 0 && list->header->forward[list->level] == NULL) {
list->level--;
}
} else {
printf("Key %d not found for deletion.\n", key);
}
}

// Function to display the skip list

void displayList(SkipList *list) {
printf("\nSkip List:\n");
for (int i = 0; i <= list->level; i++) {
Node *node = list->header->forward[i];
printf("Level %d: ", i);
while (node != NULL) {
printf("%d ", node->key);
node = node->forward[i];
}
printf("\n");
}
}

int main() {
srand((unsigned)time(0)); // Seed the random number generator

SkipList *list = createSkipList();

insertNode(list, 3);
insertNode(list, 6);
insertNode(list, 7);
insertNode(list, 9);
insertNode(list, 12);
insertNode(list, 19);
insertNode(list, 17);
insertNode(list, 26);
insertNode(list, 21);
 insertNode(list, 25);

displayList(list);

Node *found = searchNode(list, 19);

if (found) {
printf("Key 19 found.\n");
} else {
printf("Key 19 not found.\n");
}

deleteNode(list, 12);
displayList(list);

deleteNode(list, 5); // Attempt to delete a non-existent key

displayList(list);

// Free allocated memory (important for preventing memory leaks)

// This is a simplified cleanup; a full implementation would iterate and free all nodes
Node *temp = list->header->forward[0];
while(temp != NULL) {
Node *next = temp->forward[0];
free(temp);
temp = next;
}
free(list->header);
free(list);

return 0;
}
Output
Successfully inserted key 3.
Successfully inserted key 6.
Successfully inserted key 7.
Successfully inserted key 9.
Successfully inserted key 12.
Successfully inserted key 19.
Successfully inserted key 17.
Successfully inserted key 26.
Successfully inserted key 21.
Successfully inserted key 25.

Skip List:
Level 0: 3 6 7 9 12 17 19 21 25 26
Level 1: 3 7 9 12 21 25
Level 2: 3 7 9 12 21
Level 3: 3 7
Key 19 found.
Successfully deleted key 12.

Skip List:
Level 0: 3 6 7 9 17 19 21 25 26
Level 1: 3 7 9 21 25
Level 2: 3 7 9 21
Level 3: 3 7
Key 5 not found for deletion.

Skip List:
Level 0: 3 6 7 9 17 19 21 25 26
Level 1: 3 7 9 21 25
Level 2: 3 7 9 21
Level 3: 3 7

=== Code Execution Successful ===

PROGRAM – 2 Experiment with cache-aware data structures and analyze memory
utilization.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MATRIX_SIZE 1024 // Adjust for different cache sizes

#define ITERATIONS 100

// Function to measure time

double get_time_in_seconds() {
return (double)clock() / CLOCKS_PER_SEC;
}

int main() {
int (*matrix)[MATRIX_SIZE] =
malloc(sizeof(int[MATRIX_SIZE][MATRIX_SIZE]));

if (matrix == NULL) {
perror("Failed to allocate memory for matrix");
return 1;
}

// Initialize matrix
for (int i = 0; i < MATRIX_SIZE; i++) {
for (int j = 0; j < MATRIX_SIZE; j++) {
matrix[i][j] = i * MATRIX_SIZE + j;
}
}

// --- Experiment 1: Row-major access (cache-friendly) ---

double start_time_row_major = get_time_in_seconds();
long long sum_row_major = 0;
for (int iter = 0; iter < ITERATIONS; iter++) {
for (int i = 0; i < MATRIX_SIZE; i++) {
for (int j = 0; j < MATRIX_SIZE; j++) {
sum_row_major += matrix[i][j]; // Accessing elements in row-
major order
}
}
 }
double end_time_row_major = get_time_in_seconds();
printf("Row-major access time: %.4f seconds\n",
end_time_row_major - start_time_row_major);
printf("Sum (Row-major): %lld\n\n", sum_row_major);

// --- Experiment 2: Column-major access (cache-unfriendly) ---

double start_time_col_major = get_time_in_seconds();
long long sum_col_major = 0;
for (int iter = 0; iter < ITERATIONS; iter++) {
for (int j = 0; j < MATRIX_SIZE; j++) {
for (int i = 0; i < MATRIX_SIZE; i++) {
sum_col_major += matrix[i][j]; // Accessing elements in column-
major order
}
}
}
double end_time_col_major = get_time_in_seconds();
printf("Column-major access time: %.4f seconds\n",
end_time_col_major - start_time_col_major);
printf("Sum (Column-major): %lld\n\n", sum_col_major);

// Analyze Memory Utilization:

// The memory utilization for both experiments is the same, as they
operate on the same data structure.
// The difference lies in how efficiently the cache is utilized.
// The total memory allocated for the matrix is:
size_t total_memory_bytes = sizeof(int[MATRIX_SIZE][MATRIX_SIZE]);
printf("Total memory allocated for matrix: %zu bytes (%.2f MB)\n",
total_memory_bytes, (double)total_memory_bytes / (1024 * 1024));

free(matrix);
return 0;
}
OUTPUT
Row-major access time: 0.1237 seconds
Sum (Row-major): 54975528960000

Column-major access time: 0.3767 seconds

Sum (Column-major): 54975528960000

Total memory allocated for matrix: 4194304 bytes (4.00 MB)

=== Code Execution Successful ===

PROGRAM 3 – Implement B+ tree for database indexing use-case.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define MIN_DEGREE \
3 // Minimum degree (defines the range for number of
// keys)

typedef struct Node {

// Array of keys
int* keys;
// Minimum degree (defines the range for number of keys)
int t;
// Array of child pointers
struct Node** children;
// Current number of keys
int n;
// To determine whether the node is leaf or not
bool leaf;
// Pointer to next leaf node
struct Node* next;
} Node;

typedef struct BTree {

// Pointer to root node
Node* root;
// Minimum degree
int t;
} BTree;

// Function to create a new B+ tree node

Node* createNode(int t, bool leaf)
{
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->t = t;
newNode->leaf = leaf;
newNode->keys = (int*)malloc((2 * t - 1) * sizeof(int));
newNode->children
= (Node**)malloc((2 * t) * sizeof(Node*));
newNode->n = 0;
newNode->next = NULL;
return newNode;
}

// Function to create a new B+ tree

BTree* createBTree(int t)
{
BTree* btree = (BTree*)malloc(sizeof(BTree));
btree->t = t;
btree->root = createNode(t, true);
return btree;
}

// Function to display the B+ tree and print its keys

void display(Node* node)
{
if (node == NULL)
return;
int i;
for (i = 0; i < node->n; i++) {
if (!node->leaf) {
display(node->children[i]);
}
printf("%d ", node->keys[i]);
}
if (!node->leaf) {
display(node->children[i]);
}
}

// Function to search a key in the B+ tree

bool search(Node* node, int key)
{
int i = 0;
while (i < node->n && key > node->keys[i]) {
i++;
}
if (i < node->n && key == node->keys[i]) {
return true;
}
if (node->leaf) {
return false;
}
return search(node->children[i], key);
}

// Function to split the child of a node during insertion

void splitChild(Node* parent, int i, Node* child)
{
int t = child->t;
Node* newChild = createNode(t, child->leaf);
newChild->n = t - 1;
 for (int j = 0; j < t - 1; j++) {
newChild->keys[j] = child->keys[j + t];
}

if (!child->leaf) {
for (int j = 0; j < t; j++) {
newChild->children[j] = child->children[j + t];
}
}

child->n = t - 1;

for (int j = parent->n; j >= i + 1; j--) {

parent->children[j + 1] = parent->children[j];
}
parent->children[i + 1] = newChild;

for (int j = parent->n - 1; j >= i; j--) {

parent->keys[j + 1] = parent->keys[j];
}
parent->keys[i] = child->keys[t - 1];
parent->n += 1;
}

// Function to insert a non-full node

void insertNonFull(Node* node, int key)
{
int i = node->n - 1;

if (node->leaf) {
while (i >= 0 && node->keys[i] > key) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->n += 1;
}
else {
while (i >= 0 && node->keys[i] > key) {
i--;
}
i++;
if (node->children[i]->n == 2 * node->t - 1) {
splitChild(node, i, node->children[i]);
if (node->keys[i] < key) {
i++;
}
 }
insertNonFull(node->children[i], key);
}
}

// Function to insert a key into the B+ tree

void insert(BTree* btree, int key)
{
Node* root = btree->root;
if (root->n == 2 * btree->t - 1) {
Node* newRoot = createNode(btree->t, false);
newRoot->children[0] = root;
splitChild(newRoot, 0, root);
insertNonFull(newRoot, key);
btree->root = newRoot;
}
else {
insertNonFull(root, key);
}
}

// Function prototypes for helper functions used in

// deleteKey
void deleteKeyHelper(Node* node, int key);
int findKey(Node* node, int key);
void removeFromLeaf(Node* node, int idx);
int getPredecessor(Node* node, int idx);
void fill(Node* node, int idx);
void borrowFromPrev(Node* node, int idx);
void borrowFromNext(Node* node, int idx);
void merge(Node* node, int idx);

// Function for deleting a key from the B+ tree

void deleteKey(BTree* btree, int key)
{
Node* root = btree->root;

// Call a helper function to delete the key recursively

deleteKeyHelper(root, key);

// If root has no keys left and it has a child, make its

// first child the new root
if (root->n == 0 && !root->leaf) {
btree->root = root->children[0];
free(root);
}
}
// Helper function to recursively delete a key from the B+
// tree
void deleteKeyHelper(Node* node, int key)
{
int idx = findKey(
node, key); // Find the index of the key in the node

// If key is present in this node

if (idx < node->n && node->keys[idx] == key) {
if (node->leaf) {
// If the node is a leaf, simply remove the key
removeFromLeaf(node, idx);
}
else {
// If the node is not a leaf, replace the key
// with its predecessor/successor
int predecessor = getPredecessor(node, idx);
node->keys[idx] = predecessor;
// Recursively delete the predecessor
deleteKeyHelper(node->children[idx],
predecessor);
}
}
else {
// If the key is not present in this node, go down
// the appropriate child
if (node->leaf) {
// Key not found in the tree
printf("Key %d not found in the B+ tree.\n",
key);
return;
}

bool isLastChild = (idx == node->n);

// If the child where the key is supposed to be lies

// has less than t keys, fill that child
if (node->children[idx]->n < node->t) {
fill(node, idx);
}

// If the last child has been merged, it must have

// merged with the previous child

// So, we need to recursively delete the key from

// the previous child
 if (isLastChild && idx > node->n) {
deleteKeyHelper(node->children[idx - 1], key);
}
else {
deleteKeyHelper(node->children[idx], key);
}
}
}
// Function to find the index of a key in a node
int findKey(Node* node, int key)
{
int idx = 0;
while (idx < node->n && key > node->keys[idx]) {
idx++;
}
return idx;
}

// Function to remove a key from a leaf node

void removeFromLeaf(Node* node, int idx)
{
for (int i = idx + 1; i < node->n; ++i) {
node->keys[i - 1] = node->keys[i];
}
node->n--;
}

// Function to get the predecessor of a key in a non-leaf

// node
int getPredecessor(Node* node, int idx)
{
Node* curr = node->children[idx];
while (!curr->leaf) {
curr = curr->children[curr->n];
}
return curr->keys[curr->n - 1];
}

// Function to fill up the child node present at the idx-th

// position in the node node
void fill(Node* node, int idx)
{
if (idx != 0 && node->children[idx - 1]->n >= node->t) {
borrowFromPrev(node, idx);
}
else if (idx != node->n
&& node->children[idx + 1]->n >= node->t) {
 borrowFromNext(node, idx);
}
else {
if (idx != node->n) {
merge(node, idx);
}
else {
merge(node, idx - 1);
}
}
}

// Function to borrow a key from the previous child and move

// it to the idx-th child
void borrowFromPrev(Node* node, int idx)
{
Node* child = node->children[idx];
Node* sibling = node->children[idx - 1];

// Move all keys in child one step ahead

for (int i = child->n - 1; i >= 0; --i) {
child->keys[i + 1] = child->keys[i];
}

// If child is not a leaf, move its child pointers one

// step ahead
if (!child->leaf) {
for (int i = child->n; i >= 0; --i) {
child->children[i + 1] = child->children[i];
}
}

// Setting child's first key equal to node's key[idx -

// 1]
child->keys[0] = node->keys[idx - 1];

// Moving sibling's last child as child's first child

if (!child->leaf) {
child->children[0] = sibling->children[sibling->n];
}

// Moving the key from the sibling to the parent

node->keys[idx - 1] = sibling->keys[sibling->n - 1];

// Incrementing and decrementing the key counts of child

// and sibling respectively
child->n += 1;
 sibling->n -= 1;
}

// Function to borrow a key from the next child and move it

// to the idx-th child
void borrowFromNext(Node* node, int idx)
{
Node* child = node->children[idx];
Node* sibling = node->children[idx + 1];

// Setting child's (t - 1)th key equal to node's

// key[idx]
child->keys[(child->n)] = node->keys[idx];

// If child is not a leaf, move its child pointers one

// step ahead
if (!child->leaf) {
child->children[(child->n) + 1]
= sibling->children[0];
}

// Setting node's idx-th key equal to sibling's first

// key
node->keys[idx] = sibling->keys[0];

// Moving all keys in sibling one step behind

for (int i = 1; i < sibling->n; ++i) {
sibling->keys[i - 1] = sibling->keys[i];
}

// If sibling is not a leaf, move its child pointers one

// step behind
if (!sibling->leaf) {
for (int i = 1; i <= sibling->n; ++i) {
sibling->children[i - 1] = sibling->children[i];
}
}

// Incrementing and decrementing the key counts of child

// and sibling respectively
child->n += 1;
sibling->n -= 1;
}

// Function to merge idx-th child of node with (idx + 1)-th

// child of node
void merge(Node* node, int idx)
{
Node* child = node->children[idx];
Node* sibling = node->children[idx + 1];

// Pulling a key from the current node and inserting it

// into (t-1)th position of child
child->keys[child->n] = node->keys[idx];

// If child is not a leaf, move its child pointers one

// step ahead
if (!child->leaf) {
child->children[child->n + 1]
= sibling->children[0];
}

// Copying the keys from sibling to child

for (int i = 0; i < sibling->n; ++i) {
child->keys[i + child->n + 1] = sibling->keys[i];
}

// If child is not a leaf, copy the children pointers as

// well
if (!child->leaf) {
for (int i = 0; i <= sibling->n; ++i) {
child->children[i + child->n + 1]
= sibling->children[i];
}
}

// Move all keys after idx in the current node one step
// before, so as to fill the gap created by moving
// keys[idx] to child
for (int i = idx + 1; i < node->n; ++i) {
node->keys[i - 1] = node->keys[i];
}

// Move the child pointers after (idx + 1) in the

// current node one step before
for (int i = idx + 2; i <= node->n; ++i) {
node->children[i - 1] = node->children[i];
}

// Update the key count of child and current node

child->n += sibling->n + 1;
node->n--;

// Free the memory occupied by sibling

 free(sibling);
}

int main()
{
BTree* btree = createBTree(MIN_DEGREE);

// Insert elements into the B+ tree

insert(btree, 2);
insert(btree, 4);
insert(btree, 7);
insert(btree, 10);
insert(btree, 17);
insert(btree, 21);
insert(btree, 28);

// Print the B+ tree

printf("B+ Tree after insertion: ");
display(btree->root);
printf("\n");

// Search for a key

int key_to_search = 17;
bool found = search(btree->root, key_to_search);

if (found) {
printf("Key %d found in the B+ tree.\n",
key_to_search);
}
else {
printf("Key %d not found in the B+ tree.\n",
key_to_search);
}

// Delete element from the B+ tree

deleteKey(btree, 17);

// Print the B+ tree after deletion

printf("B+ Tree after deletion: ");
display(btree->root);
printf("\n");

found = search(btree->root, key_to_search);

if (found) {
printf("Key %d found in the B+ tree.\n",
key_to_search);
 }
else {
printf("Key %d not found in the B+ tree.\n",
key_to_search);
}

return 0;
}
OUTPUT

B+ Tree after insertion: 2 4 7 10 17 21 28

Key 17 found in the B+ tree.
B+ Tree after deletion: 2 4 7 10 21 28
Key 17 not found in the B+ tree.

=== Code Execution Successful ===

PROGRAM – 4 – Design a suffix tree-based algorithm for DNA sequence matching.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET_SIZE 4 // A, C, G, T

// Map DNA characters to array indices

int charToIndex(char c) {
switch (c) {
case 'A': return 0;
case 'C': return 1;
case 'G': return 2;
case 'T': return 3;
default: return -1; // Handle end marker or invalid chars
}
}

// Suffix tree node structure

typedef struct SuffixTreeNode {
struct SuffixTreeNode *children[ALPHABET_SIZE]; // Pointers for A, C, G, T
// In a full implementation, edges have start/end indices into the main text
// For this conceptual search, we just track child nodes
int suffixIndex; // Stores the starting index of the suffix if it's a leaf
} SuffixTreeNode;

// Function to create a new suffix tree node

SuffixTreeNode* createNode() {
SuffixTreeNode *node = (SuffixTreeNode*)malloc(sizeof(SuffixTreeNode));
if (node == NULL) {
perror("malloc failed");
exit(EXIT_FAILURE);
}
for (int i = 0; i < ALPHABET_SIZE; i++) {
node->children[i] = NULL;
}
node->suffixIndex = -1; // Mark as internal node initially
return node;
}

// Conceptual function to build a suffix tree (simplified brute force for

demonstration)
// A real application would use Ukkonen's or McCreight's algorithm for O(N)
efficiency
SuffixTreeNode* buildSuffixTree(const char* text) {
 SuffixTreeNode* root = createNode();
int n = strlen(text);
// This part is highly simplified and not efficient for large DNA sequences
// In a true suffix tree, you insert suffixes efficiently using edge compression
// This is just a basic trie insertion
for (int i = 0; i < n; i++) {
SuffixTreeNode* curr = root;
for (int j = i; j < n; j++) {
int index = charToIndex(text[j]);
if (index == -1) break; // Stop at end marker or invalid char

if (curr->children[index] == NULL) {
curr->children[index] = createNode();
}
curr = curr->children[index];
}
// Mark the end of a suffix at the leaf
// This simple version has issues with prefixes being suffixes,
// which a real suffix tree handles with end markers and suffix links
curr->suffixIndex = i;
}
return root;
}

// Function to search for a pattern in the suffix tree

void searchPattern(SuffixTreeNode* root, const char* pattern, const char* text) {
SuffixTreeNode* curr = root;
int m = strlen(pattern);
int i;
for (i = 0; i < m; i++) {
int index = charToIndex(pattern[i]);
if (index == -1 || curr->children[index] == NULL) {
printf("Pattern \"%s\" not found in the sequence.\n", pattern);
return;
}
curr = curr->children[index];
}

// If the loop completes, the pattern is found up to this node

// To find all occurrences, a DFS from 'curr' is needed to collect all leaf indices
printf("Pattern \"%s\" found in the sequence.\n", pattern);
// A function to do DFS below 'curr' to print all positions would go here
}

// Function to free the memory of the suffix tree (simplified)

void freeSuffixTree(SuffixTreeNode* node) {
if (node == NULL) return;
 for (int i = 0; i < ALPHABET_SIZE; i++) {
freeSuffixTree(node->children[i]);
}
free(node);
}

// Main function
int main() {
// Note: A real implementation appends a unique terminal character (e.g., '$') to
the sequence
// to ensure all suffixes end in a leaf node.
const char* dnaSequence = "AGCTAGCATCGCAT$";
const char* pattern1 = "AGCA";
const char* pattern2 = "TGC";
const char* pattern3 = "GG";

printf("Building suffix tree for DNA sequence: %s\n", dnaSequence);

// The build function is a simplification.
SuffixTreeNode* root = buildSuffixTree(dnaSequence);

printf("\n--- Searching for Patterns ---\n");

searchPattern(root, pattern1, dnaSequence);
searchPattern(root, pattern2, dnaSequence);
searchPattern(root, pattern3, dnaSequence);

// Cleanup
freeSuffixTree(root);

return 0;
}
OUTPUT

Building suffix tree for DNA sequence: AGCTAGCATCGCAT$

--- Searching for Patterns ---

Pattern "AGCA" found in the sequence.
Pattern "TGC" not found in the sequence.
Pattern "GG" not found in the sequence.

=== Code Execution Successful ===

PROGRAM – 5 - Implement Johnson’s algorithm for sparse graph shortest paths.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define INF INT_MAX

// Structure to represent an edge

struct Edge {
int src, dest, weight;
};

// Structure to represent a graph

struct Graph {
int V, E;
struct Edge* edges;
};

// Create a graph with V vertices and E edges

struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edges = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
}

// Bellman-Ford algorithm to find shortest paths from a source

int bellmanFord(struct Graph* graph, int src, int* dist) {
int V = graph->V;
int E = graph->E;

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

dist[i] = INF;
dist[src] = 0;

for (int i = 1; i <= V - 1; i++) {

for (int j = 0; j < E; j++) {
int u = graph->edges[j].src;
int v = graph->edges[j].dest;
int weight = graph->edges[j].weight;
if (dist[u] != INF && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
 }

// Check for negative cycles

for (int i = 0; i < E; i++) {
int u = graph->edges[i].src;
int v = graph->edges[i].dest;
int weight = graph->edges[i].weight;
if (dist[u] != INF && dist[u] + weight < dist[v])
return 0; // Negative cycle detected
}
return 1; // No negative cycle
}

// Dijkstra's algorithm using adjacency matrix (for simplicity)

void dijkstra(int V, int** adjMatrix, int startNode, int* dist) {
int visited[V];
for (int i = 0; i < V; i++) {
dist[i] = INF;
visited[i] = 0;
}
dist[startNode] = 0;

for (int count = 0; count < V - 1; count++) {

int u = -1;
for (int v = 0; v < V; v++) {
if (!visited[v] && (u == -1 || dist[v] < dist[u])) {
u = v;
}
}
visited[u] = 1;

for (int v = 0; v < V; v++) {

if (!visited[v] && adjMatrix[u][v] != INF && dist[u] != INF &&
dist[u] + adjMatrix[u][v] < dist[v]) {
dist[v] = dist[u] + adjMatrix[u][v];
}
}
}
}

// Johnson's algorithm
void johnsonsAlgorithm(struct Graph* graph) {
int V = graph->V;
int E = graph->E;

// Step 1: Create a new graph G' with a new source vertex 's'
// and zero-weight edges from 's' to all other vertices.
struct Graph* G_prime = createGraph(V + 1, E + V);
for (int i = 0; i < E; i++) {
G_prime->edges[i] = graph->edges[i];
}
for (int i = 0; i < V; i++) {
G_prime->edges[E + i].src = V; // New source 's' is V
G_prime->edges[E + i].dest = i;
G_prime->edges[E + i].weight = 0;
}

// Step 2: Run Bellman-Ford on G' from 's' to compute potentials h(v)

int h[V + 1];
if (!bellmanFord(G_prime, V, h)) {
printf("Negative cycle detected in the graph.\n");
return;
}

// Step 3: Re-weight the edges

int** reweightedAdjMatrix = (int**)malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
reweightedAdjMatrix[i] = (int*)malloc(V * sizeof(int));
for (int j = 0; j < V; j++) {
reweightedAdjMatrix[i][j] = INF;
}
}

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

int u = graph->edges[i].src;
int v = graph->edges[i].dest;
int originalWeight = graph->edges[i].weight;
reweightedAdjMatrix[u][v] = originalWeight + h[u] - h[v];
}

// Step 4: Run Dijkstra from each vertex in the re-weighted graph

int** allPairsShortestPaths = (int**)malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
allPairsShortestPaths[i] = (int*)malloc(V * sizeof(int));
dijkstra(V, reweightedAdjMatrix, i, allPairsShortestPaths[i]);
}

// Step 5: Convert back to original path weights

printf("All-Pairs Shortest Paths:\n");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (allPairsShortestPaths[i][j] != INF) {
allPairsShortestPaths[i][j] = allPairsShortestPaths[i][j] - h[i] + h[j];
printf("%d\t", allPairsShortestPaths[i][j]);
 } else {
printf("INF\t");
}
}
printf("\n");
}

// Free allocated memory

free(G_prime->edges);
free(G_prime);
for (int i = 0; i < V; i++) {
free(reweightedAdjMatrix[i]);
free(allPairsShortestPaths[i]);
}
free(reweightedAdjMatrix);
free(allPairsShortestPaths);
}

int main() {
int V = 4; // Number of vertices
int E = 5; // Number of edges

struct Graph* graph = createGraph(V, E);

// Example graph with negative weights

graph->edges[0] = (struct Edge){0, 1, 3};
graph->edges[1] = (struct Edge){0, 2, -2};
graph->edges[2] = (struct Edge){1, 3, 1};
graph->edges[3] = (struct Edge){2, 1, 4};
graph->edges[4] = (struct Edge){2, 3, 2};

johnsonsAlgorithm(graph);

free(graph->edges);
free(graph);

return 0;
}
OUTPUT

All-Pairs Shortest Paths:

0 2 -2 0
INF 0 INF 1
INF 4 0 2
INF INF INF 0

=== Code Execution Successful ===

PROGRAM – 6 - Demonstration of Maximum flow in traffic or network routing
simulation.

#include <stdio.h>
#include <limits.h> // For INT_MAX
#include <string.h> // For memset

#define MAX_VERTICES 100

// Function to perform BFS and find an augmenting path

int bfs(int rGraph[MAX_VERTICES][MAX_VERTICES], int s, int t, int
parent[MAX_VERTICES], int num_vertices) {
int visited[MAX_VERTICES];
memset(visited, 0, sizeof(visited)); // Initialize all nodes as not visited

int queue[MAX_VERTICES];
int front = 0, rear = 0;

queue[rear++] = s;
visited[s] = 1;
parent[s] = -1; // Source has no parent

while (front != rear) {

int u = queue[front++];

for (int v = 0; v < num_vertices; v++) {

// If v is not visited and there is a residual capacity from u to v
if (visited[v] == 0 && rGraph[u][v] > 0) {
queue[rear++] = v;
parent[v] = u;
visited[v] = 1;
if (v == t) {
return 1; // Path found
}
}
}
}
return 0; // No path found
}

// Ford-Fulkerson algorithm to find maximum flow

int ford_fulkerson(int graph[MAX_VERTICES][MAX_VERTICES], int s, int t, int
num_vertices) {
int u, v;
int rGraph[MAX_VERTICES][MAX_VERTICES]; // Residual graph
 // Initialize residual graph with given capacities
for (u = 0; u < num_vertices; u++) {
for (v = 0; v < num_vertices; v++) {
rGraph[u][v] = graph[u][v];
}
}

int parent[MAX_VERTICES]; // Stores path

int max_flow = 0;

// While there is an augmenting path from source to sink

while (bfs(rGraph, s, t, parent, num_vertices)) {
// Find minimum residual capacity of edges along the augmenting path
// This is the maximum flow that can be added in this path
int path_flow = INT_MAX;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
path_flow = (path_flow < rGraph[u][v]) ? path_flow : rGraph[u][v];
}

// Update residual capacities of edges and reverse edges along the path
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow; // Add flow to reverse edge
}

max_flow += path_flow;
}

return max_flow;
}

int main() {
// Example graph representing a network with capacities
// Here, 0 is source, 5 is sink.
// The values represent capacities of connections.
int graph[MAX_VERTICES][MAX_VERTICES] = {
{0, 10, 15, 0, 0, 0},
{0, 0, 0, 5, 10, 0},
{0, 0, 0, 0, 0, 10},
{0, 0, 0, 0, 0, 5},
{0, 0, 0, 0, 0, 10},
{0, 0, 0, 0, 0, 0}
};
int num_vertices = 6;
 int source = 0;
int sink = 5;

int max_flow = ford_fulkerson(graph, source, sink, num_vertices);

printf("Maximum flow from source %d to sink %d is %d\n", source, sink,
max_flow);

return 0;
}

OUTPUT

Maximum flow from source 0 to sink 5 is 20

=== Code Execution Successful ===

PROGRAM – 7 - Implement Strassen’s algorithm and compare with naive matrix
multiplication.

#include <stdio.h>
#include <stdlib.h>

// Function to allocate memory for a matrix

int** allocateMatrix(int n) {
int** matrix = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
matrix[i] = (int*)malloc(n * sizeof(int));
}
return matrix;
}

// Function to free memory allocated for a matrix

void freeMatrix(int** matrix, int n) {
for (int i = 0; i < n; i++) {
free(matrix[i]);
}
free(matrix);
}

// Function to print a matrix

void printMatrix(int** matrix, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d\t", matrix[i][j]);
}
printf("\n");
}
}

// Function to add two matrices

int** add(int** A, int** B, int n) {
int** C = allocateMatrix(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = A[i][j] + B[i][j];
}
}
return C;
}

// Function to subtract two matrices

int** subtract(int** A, int** B, int n) {
int** C = allocateMatrix(n);
 for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
C[i][j] = A[i][j] - B[i][j];
}
}
return C;
}

// Strassen's matrix multiplication function

int** strassenMultiply(int** A, int** B, int n) {
if (n == 1) {
int** C = allocateMatrix(1);
C[0][0] = A[0][0] * B[0][0];
return C;
}

int newSize = n / 2;
int** A11 = allocateMatrix(newSize);
int** A12 = allocateMatrix(newSize);
int** A21 = allocateMatrix(newSize);
int** A22 = allocateMatrix(newSize);
int** B11 = allocateMatrix(newSize);
int** B12 = allocateMatrix(newSize);
int** B21 = allocateMatrix(newSize);
int** B22 = allocateMatrix(newSize);

// Divide matrices into sub-matrices

for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
A11[i][j] = A[i][j];
A12[i][j] = A[i][j + newSize];
A21[i][j] = A[i + newSize][j];
A22[i][j] = A[i + newSize][j + newSize];

B11[i][j] = B[i][j];
B12[i][j] = B[i][j + newSize];
B21[i][j] = B[i + newSize][j];
B22[i][j] = B[i + newSize][j + newSize];
}
}

// Calculate 7 products recursively

int** M1 = strassenMultiply(add(A11, A22, newSize), add(B11, B22, newSize),
newSize);
int** M2 = strassenMultiply(add(A21, A22, newSize), B11, newSize);
int** M3 = strassenMultiply(A11, subtract(B12, B22, newSize), newSize);
int** M4 = strassenMultiply(A22, subtract(B21, B11, newSize), newSize);
 int** M5 = strassenMultiply(add(A11, A12, newSize), B22, newSize);
int** M6 = strassenMultiply(subtract(A21, A11, newSize), add(B11, B12, newSize),
newSize);
int** M7 = strassenMultiply(subtract(A12, A22, newSize), add(B21, B22, newSize),
newSize);

// Calculate sub-matrices of C
int** C11 = add(subtract(add(M1, M4, newSize), M5, newSize), M7, newSize);
int** C12 = add(M3, M5, newSize);
int** C21 = add(M2, M4, newSize);
int** C22 = add(subtract(add(M1, M3, newSize), M2, newSize), M6, newSize);

// Combine sub-matrices into result matrix C

int** C = allocateMatrix(n);
for (int i = 0; i < newSize; i++) {
for (int j = 0; j < newSize; j++) {
C[i][j] = C11[i][j];
C[i][j + newSize] = C12[i][j];
C[i + newSize][j] = C21[i][j];
C[i + newSize][j + newSize] = C22[i][j];
}
}

// Free allocated memory for sub-matrices and intermediate products

freeMatrix(A11, newSize); freeMatrix(A12, newSize); freeMatrix(A21, newSize);
freeMatrix(A22, newSize);
freeMatrix(B11, newSize); freeMatrix(B12, newSize); freeMatrix(B21, newSize);
freeMatrix(B22, newSize);
freeMatrix(M1, newSize); freeMatrix(M2, newSize); freeMatrix(M3, newSize);
freeMatrix(M4, newSize);
freeMatrix(M5, newSize); freeMatrix(M6, newSize); freeMatrix(M7, newSize);
freeMatrix(C11, newSize); freeMatrix(C12, newSize); freeMatrix(C21, newSize);
freeMatrix(C22, newSize);

return C;
}

int main() {
int n = 4; // For a 4x4 matrix

// Initialize matrices A and B

int** A = allocateMatrix(n);
int** B = allocateMatrix(n);

// Example 4x4 matrices

int count = 1;
for (int i = 0; i < n; i++) {
 for (int j = 0; j < n; j++) {
A[i][j] = count;
B[i][j] = count;
count++;
}
}

printf("Matrix A:\n");
printMatrix(A, n);
printf("\nMatrix B:\n");
printMatrix(B, n);

// Perform Strassen's multiplication

int** C = strassenMultiply(A, B, n);

printf("\nResult of Strassen's Matrix Multiplication (C = A * B):\n");

printMatrix(C, n);

// Free allocated memory

freeMatrix(A, n);
freeMatrix(B, n);
freeMatrix(C, n);

return 0;
}
OUTPUT

Matrix A:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Matrix B:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Result of Strassen's Matrix Multiplication (C = A * B):

90 100 110 120
202 228 254 280
314 356 398 440
426 484 542 600

=== Code Execution Successful ===

PROGRAM – 8 - Develop a randomized algorithm for primality testing (Miller–Rabin).

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function to perform modular multiplication (a * b) % mod

// Handles potential overflow of a * b
long long mulmod(long long a, long long b, long long mod) {
long long res = 0;
a %= mod;
while (b > 0) {
if (b % 2 == 1) {
res = (res + a) % mod;
}
a = (a * 2) % mod;
b /= 2;
}
return res;
}

// Function to perform modular exponentiation (base^exp) % mod

long long power(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) {
res = mulmod(res, base, mod);
}
base = mulmod(base, base, mod);
exp /= 2;
}
return res;
}

// Miller-Rabin primality test for a single base 'a'

// Returns 0 if n is composite, 1 if n is probably prime
int millerTest(long long d, long long n) {
// Pick a random number 'a' in [2, n-2]
long long a = 2 + rand() % (n - 3);

long long x = power(a, d, n);

if (x == 1 || x == n - 1) {
return 1; // Probably prime
 }

// Keep squaring x until d becomes n-1

while (d != n - 1) {
x = mulmod(x, x, n);
d *= 2;

if (x == 1) return 0; // Composite
if (x == n - 1) return 1; // Probably prime
}

return 0; // Composite
}

// Main Miller-Rabin primality test function

// k is the number of iterations (determines accuracy)
int isPrimeMillerRabin(long long n, int k) {
// Handle base cases
if (n <= 1 || n == 4) return 0;
if (n <= 3) return 1;

// Find d such that n-1 = d * 2^r, where d is odd

long long d = n - 1;
while (d % 2 == 0) {
d /= 2;
}

// Run Miller-Rabin test k times

for (int i = 0; i < k; i++) {
if (millerTest(d, n) == 0) {
return 0; // Composite
}
}

return 1; // Probably prime

}

int main() {
srand(time(NULL)); // Seed the random number generator

long long num;

int iterations = 5; // Number of iterations for the test

printf("Enter an integer to test for primality: ");

scanf("%lld", &num);

if (isPrimeMillerRabin(num, iterations)) {
 printf("%lld is probably prime.\n", num);
} else {
printf("%lld is composite.\n", num);
}

return 0;
}

OUTPUT

Enter an integer to test for primality: 3

3 is probably prime.

Enter an integer to test for primality: 16

16 is composite.

=== Code Execution Successful ===

PROGRAM – 9 - Implement approximation algorithm for vertex cover.

#include <stdio.h>
#include <stdlib.h>

// Structure to represent an edge

typedef struct Edge {
int u, v;
} Edge;

// Function to implement the 2-approximation algorithm for Vertex Cover

void approxVertexCover(int numVertices, int numEdges, Edge edges[]) {
// Initialize an array to keep track of included vertices in the cover
int *vertexCover = (int *)calloc(numVertices + 1, sizeof(int)); // 1-indexed for
convenience

// Create a copy of edges to be modified

// We'll mark edges as "covered" by setting their endpoints to -1
Edge *remainingEdges = (Edge *)malloc(numEdges * sizeof(Edge));
for (int i = 0; i < numEdges; i++) {
remainingEdges[i] = edges[i];
}

int coveredEdgesCount = 0;
while (coveredEdgesCount < numEdges) {
int pickedEdgeIndex = -1;

// Find an uncovered edge

for (int i = 0; i < numEdges; i++) {
if (remainingEdges[i].u != -1) { // If the edge is not marked as covered
pickedEdgeIndex = i;
break;
}
}

if (pickedEdgeIndex == -1) { // No more uncovered edges

break;
}

int u = remainingEdges[pickedEdgeIndex].u;
int v = remainingEdges[pickedEdgeIndex].v;

// Add both endpoints to the vertex cover

vertexCover[u] = 1;
vertexCover[v] = 1;
 // Remove all edges incident to u or v
for (int i = 0; i < numEdges; i++) {
if (remainingEdges[i].u != -1) { // If the edge is still active
if (remainingEdges[i].u == u || remainingEdges[i].v == u ||
remainingEdges[i].u == v || remainingEdges[i].v == v) {
remainingEdges[i].u = -1; // Mark as covered
coveredEdgesCount++;
}
}
}
}

printf("Approximate Vertex Cover: ");

for (int i = 1; i <= numVertices; i++) {
if (vertexCover[i] == 1) {
printf("%d ", i);
}
}
printf("\n");

free(vertexCover);
free(remainingEdges);
}

int main() {
int numVertices = 7;
int numEdges = 8;

// Example graph edges (1-indexed vertices)

Edge edges[] = {
{1, 2}, {1, 3}, {2, 4}, {3, 4},
{4, 5}, {5, 6}, {5, 7}, {6, 7}
};

approxVertexCover(numVertices, numEdges, edges);

return 0;
}
OUTPUT

Approximate Vertex Cover: 1 2 3 4 5 6

=== Code Execution Successful ===

PROGRAM – 10 - Complexity analysis of a chosen NP-hard problem and implement a
heuristic.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 20
#define MAX_EDGES 100

// Structure to represent an edge

typedef struct Edge {
int u; // Source vertex
int v; // Destination vertex
} Edge;

// Global variables for graph and cover

int numVertices;
int numEdges;
Edge edges[MAX_EDGES];
int vertexCoverSet[MAX_VERTICES];
int isCovered[MAX_VERTICES]; // To mark vertices in the cover set
int edgeRemoved[MAX_EDGES]; // To mark edges that have been "covered"

// Function to add an edge to the graph

void addEdge(int u, int v) {
if (numEdges < MAX_EDGES) {
edges[numEdges].u = u;
edges[numEdges].v = v;
numEdges++;
} else {
printf("Error: Maximum edges reached.\n");
}
}

// The 2-approximation algorithm for Vertex Cover

void findApproxVertexCover() {
// Initialize cover set flags and edge status
for (int i = 0; i < numVertices; i++) {
isCovered[i] = 0;
}
for (int i = 0; i < numEdges; i++) {
edgeRemoved[i] = 0;
}

int coveredCount = 0;

// Iterate while there are uncovered edges

 for (int i = 0; i < numEdges; i++) {
// Pick an arbitrary uncovered edge (u, v)
if (!edgeRemoved[i]) {
int u = edges[i].u;
int v = edges[i].v;

// Add both endpoints u and v to the vertex cover set

if (!isCovered[u]) {
isCovered[u] = 1;
// Add to result set if needed (using isCovered as marker)
}
if (!isCovered[v]) {
isCovered[v] = 1;
// Add to result set if needed (using isCovered as marker)
}

// Remove all edges incident on u or v from the graph

// (by marking them as removed)
for (int j = 0; j < numEdges; j++) {
if (edges[j].u == u || edges[j].v == u || edges[j].u == v || edges[j].v == v) {
edgeRemoved[j] = 1;
}
}
}
}

// Print the resulting approximate vertex cover

printf("The approximate vertex cover is: { ");
for (int i = 0; i < numVertices; i++) {
if (isCovered[i]) {
printf("%d ", i);
coveredCount++;
}
}
printf("}\n");
printf("Size of the vertex cover: %d\n", coveredCount);
}

// Driver program to test the algorithm

int main() {
// Define a graph (example from GeeksforGeeks/TutorialsPoint)
// Vertices are 0 to 6
numVertices = 7;
numEdges = 0; // Will be incremented by addEdge

// Add edges
addEdge(0, 1);
 addEdge(0, 2);
addEdge(1, 3);
addEdge(3, 4);
addEdge(4, 5);
addEdge(5, 6);
// Note: The example graph from the sources uses vertices 0 to 6, not the
// more complex one in the text description of the algorithm.

printf("Graph initialized with %d vertices and %d edges.\n", numVertices,

numEdges);

findApproxVertexCover();

return 0;
}

OUTPUT

Graph initialized with 7 vertices and 6 edges.

The approximate vertex cover is: { 0 1 3 4 5 6 }
Size of the vertex cover: 6

=== Code Execution Successful ===

PROGRAM – 11 - Implement randomized and streaming algorithms on real-world datasets.

1. Randomized Algorithm: Randomized Quicksort

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define DATA_SIZE 100000 // Size of the array (simulating a dataset)

// Function to swap two elements

void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}

// Partition function that places the pivot at its correct position

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Standard last element as pivot for this part
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

// Randomized partition function: chooses a random pivot and swaps it to

the end
int randomizedPartition(int arr[], int low, int high) {
int randomIdx = low + rand() % (high - low + 1); // Get a random index
swap(&arr[randomIdx], &arr[high]); // Move the random element to the end
return partition(arr, low, high); // Use standard partition
}

// The main randomized Quicksort function

void randomizedQuickSort(int arr[], int low, int high) {
if (low < high) {
// pi is the partitioning index, arr[pi] is now at the right place
int pi = randomizedPartition(arr, low, high);

// Recursively sort elements before partition and after partition

 randomizedQuickSort(arr, low, pi - 1);
randomizedQuickSort(arr, pi + 1, high);
}
}

// Helper function to print the array

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main() {
int data[DATA_SIZE];
// Seed the random number generator
srand(time(NULL));

// Fill array with reverse-sorted data to force worst-case for deterministic

QS
for (int i = 0; i < DATA_SIZE; i++) {
data[i] = DATA_SIZE - i;
}

printf("Dataset size: %d elements (initially reverse sorted)\n", DATA_SIZE);

long start_time = time(NULL);

randomizedQuickSort(data, 0, DATA_SIZE - 1);
long end_time = time(NULL);

printf("Sorting completed in approximately %ld seconds.\n", end_time -

start_time);
// You can verify correctness for smaller sizes by uncommenting the print
function:
// printf("Sorted array: \n");
// printArray(data, 20); // Print only first 20 elements for brevity

return 0;
}

OUTPUT

Dataset size: 100000 elements (initially reverse sorted)

Sorting completed in approximately 0 seconds.

=== Code Execution Successful ===

2. Streaming Algorithm: Reservoir Sampling

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SAMPLE_SIZE 10 // Number of items to keep in our limited memory

(reservoir)

// The reservoir sampling function

void reservoirSampling(FILE *stream, int reservoir[], int k) {
int count = 0; // Count of items seen so far in the stream
int item;

// 1. Fill the reservoir with the first k items from the stream
for (int i = 0; i < k && fscanf(stream, "%d", &item) == 1; i++) {
reservoir[i] = item;
count++;
}

// 2. Process items from k+1 to n (end of stream)

while (fscanf(stream, "%d", &item) == 1) {
count++;
// Generate a random index 'j' from 0 to count-1
int j = rand() % count;

// If the random index j is less than k, replace the item at reservoir[j]

// The probability of replacement is k/count
if (j < k) {
reservoir[j] = item;
}
}
}

int main() {
// Seed the random number generator
srand(time(NULL));

// Simulate a large data stream by creating a temporary file with many

numbers
FILE *stream = fopen("data_stream.txt", "w+");
if (!stream) {
perror("Failed to create stream file");
return EXIT_FAILURE;
}

// Write 1 million numbers to the file

 for (int i = 0; i < 1000000; i++) {
fprintf(stream, "%d ", i);
}
// Rewind the file pointer to the beginning to start "streaming" from start
rewind(stream);

int reservoir[SAMPLE_SIZE];

printf("Starting Reservoir Sampling (k=%d) from a stream of 1 million

items.\n", SAMPLE_SIZE);
reservoirSampling(stream, reservoir, SAMPLE_SIZE);

printf("The sampled reservoir is: \n");

for (int i = 0; i < SAMPLE_SIZE; i++) {
printf("%d ", reservoir[i]);
}
printf("\n");

fclose(stream);
// Optionally remove the temporary file using remove("data_stream.txt");

return 0;
}

OUTPUT

Failed to create stream file: Permission denied

=== Code Exited With Errors ===

NOTE : CHECK THE PROGRAM AND CREATE TXT FILE AND THEN RUN
PROGRAM – 12 - Design of parallel and distributed algorithms.