Iwnrxzwolf

1 Merge Sort
#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;

// Create temporary arrays

int L[n1], R[n2];

// Copy data to temporary arrays

for (int i = 0; i < n1; i++)
    L[i] = arr[left + i];
for (int j = 0; j < n2; j++)
    R[j] = arr[mid + 1 + j];


int i = 0, j = 0, k = left;

// Merge the temporary arrays back into arr[left..right]

while (i < n1 && j < n2) {
    if (L[i] <= R[j]) {
        arr[k] = L[i];
        i++;
    } else {
        arr[k] = R[j];
        j++;
    }
    k++;
}

// Copy the remaining elements of L[], if any

while (i < n1) {
    arr[k] = L[i];
    i++;
    k++;
}

// Copy the remaining elements of R[], if any

while (j < n2) {
    arr[k] = R[j];
    j++;
    k++;
}

}

void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;

    // Sort first and second halves

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);

    // Merge the sorted halves

merge(arr, left, mid, right);
}
}

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

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr) / sizeof(arr[0]);

printf("Given array is \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;

}

1. Dijkstra's Algorithm
   #include <stdio.h>
   #include <limits.h>

#define V 5

int minDistance(int dist[], int sptSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == 0 && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}

void dijkstra(int graph[V][V], int src) {
int dist[V];
int sptSet[V] = {0};

for (int i = 0; i < V; i++)
    dist[i] = INT_MAX;
dist[src] = 0;

for (int count = 0; count < V - 1; count++) {
    int u = minDistance(dist, sptSet);
    sptSet[u] = 1;

    for (int v = 0; v < V; v++)
        if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])
            dist[v] = dist[u] + graph[u][v];
}

printf("Vertex \t Distance from Source\n");
for (int i = 0; i < V; i++)
    printf("%d \t\t %d\n", i, dist[i]);

}

int main() {
int graph[V][V] = {{0, 10, 20, 0, 0}, {10, 0, 5, 16, 0}, {20, 5, 0, 20, 10}, {0, 16, 20, 0, 15}, {0, 0, 10, 15, 0}};
dijkstra(graph, 0);
return 0;
}

2. Prim's Algorithm
   #include <stdio.h>
   #include <limits.h>

#define V 5

int minKey(int key[], int mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == 0 && key[v] < min)
min = key[v], min_index = v;
return min_index;
}

void primMST(int graph[V][V]) {
int parent[V];
int key[V];
int mstSet[V] = {0};

for (int i = 0; i < V; i++)
    key[i] = INT_MAX;
key[0] = 0;
parent[0] = -1;

for (int count = 0; count < V - 1; count++) {
    int u = minKey(key, mstSet);
    mstSet[u] = 1;

    for (int v = 0; v < V; v++)
        if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
            parent[v] = u, key[v] = graph[u][v];
}

printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
    printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);

}

int main() {
int graph[V][V] = {{0, 2, 0, 6, 0}, {2, 0, 3, 8, 5}, {0, 3, 0, 0, 7}, {6, 8, 0, 0, 9}, {0, 5, 7, 9, 0}};
primMST(graph);
return 0;
}

3. Depth-First Search (DFS)
   #include <stdio.h>
   #include <stdlib.h>

#define V 5

void DFSUtil(int v, int visited[], int graph[V][V]) {
visited[v] = 1;
printf("%d ", v);

for (int i = 0; i < V; i++)
    if (graph[v][i] == 1 && !visited[i])
        DFSUtil(i, visited, graph);

}

void DFS(int graph[V][V], int start) {
int visited[V] = {0};
DFSUtil(start, visited, graph);
}

int main() {
int graph[V][V] = {{0, 1, 1, 0, 0}, {1, 0, 0, 1, 1}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 1}, {0, 1, 0, 1, 0}};
printf("DFS traversal starting from vertex 0:\n");
DFS(graph, 0);
return 0;
}

4. Breadth-First Search (BFS)
   #include <stdio.h>
   #include <stdlib.h>

#define V 5

void BFS(int graph[V][V], int start) {
int visited[V] = {0};
int queue[V];
int front = 0, rear = 0;

visited[start] = 1;
queue[rear++] = start;

while (front < rear) {
    int v = queue[front++];
    printf("%d ", v);

    for (int i = 0; i < V; i++)
        if (graph[v][i] == 1 && !visited[i]) {
            visited[i] = 1;
            queue[rear++] = i;
        }
}

}

int main() {
int graph[V][V] = {{0, 1, 1, 0, 0}, {1, 0, 0, 1, 1}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 1}, {0, 1, 0, 1, 0}};
printf("BFS traversal starting from vertex 0:\n");
BFS(graph, 0);
return 0;
}

5. Topological Sort
   #include <stdio.h>
   #include <stdlib.h>

#define V 6

void topologicalSortUtil(int v, int visited[], int stack[], int *stackIndex, int graph[V][V]) {
visited[v] = 1;

for (int i = 0; i < V; i++)
    if (graph[v][i] && !visited[i])
        topologicalSortUtil(i, visited, stack, stackIndex, graph);

stack[(*stackIndex)++] = v;

}

void topologicalSort(int graph[V][V]) {
int visited[V] = {0};
int stack[V];
int stackIndex = 0;

for (int i = 0; i < V; i++)
    if (!visited[i])
        topologicalSortUtil(i, visited, stack, &stackIndex, graph);

printf("Topological Sort: ");
for (int i = stackIndex - 1; i >= 0; i--)
    printf("%d ", stack[i]);

}

int main() {
int graph[V][V] = {{0, 1, 0, 1, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0}};
topologicalSort(graph);
return 0;
}

6. Ford-Fulkerson Algorithm
   #include <stdio.h>
   #include <limits.h>
   #include <string.h>

#define V 6

int bfs(int rGraph[V][V], int s, int t, int parent[]) {
int visited[V] = {0};
int queue[V], front = 0, rear = 0;
queue[rear++] = s;
visited[s] = 1;
parent[s] = -1;

while (front < rear) {
    int u = queue[front++];

    for (int v = 0; v < V; v++) {
        if (!visited[v] && rGraph[u][v] > 0) {
            queue[rear++] = v;
            parent[v] = u;
            visited[v] = 1;
            if (v == t) return 1;
        }
    }
}
return 0;

}

int fordFulkerson(int graph[V][V], int s, int t) {
int u, v;
int rGraph[V][V];
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];

int parent[V];
int max_flow = 0;

while (bfs(rGraph, s, t, parent)) {
    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];
    }

    for (v = t; v != s; v = parent[v]) {
        u = parent[v];
        rGraph[u][v] -= path_flow;
        rGraph[v][u] += path_flow;
    }

    max_flow += path_flow;
}

return max_flow;

}

int main() {
int graph[V][V] = {{0, 16, 13, 0, 0, 0}, {0, 0, 10, 12, 0, 0}, {0, 4, 0, 0, 14, 0}, {0, 0, 9, 0, 0, 20}, {0, 0, 0, 7, 0, 4}, {0, 0, 0, 0, 0, 0}};
printf("The maximum possible flow is %d\n", fordFulkerson(graph, 0, 5));
return 0;
}

1. Bubble Sort
   #include <stdio.h>

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

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

int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
2. Insertion Sort
#include <stdio.h>

void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;

    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j = j - 1;
    }
    arr[j + 1] = key;
}

}

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

int main() {
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
3. Activity Selector (Greedy Approach)
This example assumes that activities are already sorted by their finish time.

#include <stdio.h>

void activitySelection(int start[], int finish[], int n) {
printf("Selected activities: ");

int i = 0;
printf("%d ", i);

for (int j = 1; j < n; j++) {
    if (start[j] >= finish[i]) {
        printf("%d ", j);
        i = j;
    }
}
printf("\n");

}

int main() {
int start[] = {1, 3, 0, 5, 8, 5};
int finish[] = {2, 4, 6, 7, 9, 9};
int n = sizeof(start) / sizeof(start[0]);

activitySelection(start, finish, n);
return 0;

}
4. 0/1 Knapsack Problem
This is a dynamic programming solution to the 0/1 Knapsack problem.

#include <stdio.h>

int max(int a, int b) {
return (a > b) ? a : b;
}

int knapsack(int W, int wt[], int val[], int n) {
int dp[n + 1][W + 1];

for (int i = 0; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
        if (i == 0 || w == 0)
            dp[i][w] = 0;
        else if (wt[i - 1] <= w)
            dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
        else
            dp[i][w] = dp[i - 1][w];
    }
}

return dp[n][W];

}

int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printf("Maximum value in knapsack = %d\n", knapsack(W, wt, val, n));
return 0;
}
These codes cover the essential approaches for sorting, greedy selection, and dynamic programming (Knapsack). Each program is designed to be self-contained and simple to understand. Let me know if you need further customization!

You said:
knapsack using greedy
ChatGPT said:
ChatGPT
The 0/1 Knapsack problem doesn’t lend itself to a greedy solution because it may not produce an optimal result (i.e., choosing the items with the highest value or value-to-weight ratio alone might not yield the highest total value). However, for the Fractional Knapsack problem, a greedy algorithm does work effectively.

The Fractional Knapsack allows taking fractional parts of items, so we can maximize value by taking items with the highest value-to-weight ratio first.

Here’s the code for the Fractional Knapsack Problem using a greedy approach in C:

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

typedef struct {
int weight;
int value;
double ratio;
} Item;

int compare(const void *a, const void *b) {
Item *itemA = (Item *)a;
Item *itemB = (Item *)b;
return (itemB->ratio - itemA->ratio) > 0 ? 1 : -1;
}

double fractionalKnapsack(int W, Item items[], int n) {
// Calculate value-to-weight ratio for each item
for (int i = 0; i < n; i++) {
items[i].ratio = (double)items[i].value / items[i].weight;
}

// Sort items by value-to-weight ratio in descending order
qsort(items, n, sizeof(Item), compare);

double totalValue = 0.0;
for (int i = 0; i < n; i++) {
    if (W == 0) break;

    if (items[i].weight <= W) {
        W -= items[i].weight;
        totalValue += items[i].value;
    } else {
        totalValue += items[i].value * ((double)W / items[i].weight);
        W = 0;
    }
}

return totalValue;

}

int main() {
int W = 50;
Item items[] = {{10, 60}, {20, 100}, {30, 120}};
int n = sizeof(items) / sizeof(items[0]);

double maxValue = fractionalKnapsack(W, items, n);
printf("Maximum value in knapsack = %.2f\n", maxValue);

return 0;

}

Example Output:
If W = 50, values = {60, 100, 120}, and weights = {10, 20, 30}, the output will be:

Maximum value in knapsack = 240.00
This solution provides the optimal result for the Fractional Knapsack Problem.

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

#define MAX_SIZE 100

// Node structure for the Huffman Tree
struct Node {
char ch;
int freq;
struct Node* left;
struct Node* right;
};

// Function to create a new node
struct Node* createNode(char ch, int freq) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->ch = ch;
node->freq = freq;
node->left = node->right = NULL;
return node;
}

// Function to swap two nodes (used in building the min-heap)
void swapNodes(struct Node** a, struct Node** b) {
struct Node* temp = *a;
*a = *b;
*b = temp;
}

// Min-heap structure to keep track of nodes
struct MinHeap {
int size;
struct Node* array[MAX_SIZE];
};

// Function to create a min-heap
struct MinHeap* createMinHeap(int capacity) {
struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = 0;
return minHeap;
}

// Function to insert a node into the min-heap
void insertMinHeap(struct MinHeap* minHeap, struct Node* node) {
minHeap->array[minHeap->size] = node;
int i = minHeap->size;
minHeap->size++;

// Heapify up
while (i && minHeap->array[i]->freq < minHeap->array[(i - 1) / 2]->freq) {
    swapNodes(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);
    i = (i - 1) / 2;
}

}

// Function to heapify down
void minHeapify(struct MinHeap* minHeap, int i) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
    smallest = left;

if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
    smallest = right;

if (smallest != i) {
    swapNodes(&minHeap->array[i], &minHeap->array[smallest]);
    minHeapify(minHeap, smallest);
}

}

// Function to extract the minimum node from the heap
struct Node* extractMin(struct MinHeap* minHeap) {
struct Node* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
minHeap->size--;
minHeapify(minHeap, 0);
return temp;
}

// Function to build the Huffman Tree
struct Node* buildHuffmanTree(char chars[], int freqs[], int n) {
struct MinHeap* minHeap = createMinHeap(n);

for (int i = 0; i < n; i++) {
    insertMinHeap(minHeap, createNode(chars[i], freqs[i]));
}

while (minHeap->size > 1) {
    struct Node* left = extractMin(minHeap);
    struct Node* right = extractMin(minHeap);

    struct Node* newNode = createNode('\0', left->freq + right->freq);
    newNode->left = left;
    newNode->right = right;

    insertMinHeap(minHeap, newNode);
}

return extractMin(minHeap);

}

// Function to generate and print Huffman Codes
void printCodes(struct Node* root, int code[], int top) {
if (root->left) {
code[top] = 0;
printCodes(root->left, code, top + 1);
}

if (root->right) {
    code[top] = 1;
    printCodes(root->right, code, top + 1);
}

if (!root->left && !root->right) {
    printf("%c: ", root->ch);
    for (int i = 0; i < top; i++) {
        printf("%d", code[i]);
    }
    printf("\n");
}

}

// Main function
int main() {
char chars[] = {'a', 'b', 'c', 'd', 'e', 'f'};
int freqs[] = {5, 9, 12, 13, 16, 45};
int n = sizeof(chars) / sizeof(chars[0]);

struct Node* root = buildHuffmanTree(chars, freqs, n);

int code[MAX_SIZE], top = 0;
printf("Huffman Codes:\n");
printCodes(root, code, top);

return 0;

}