Untitled

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

int weight = 0;

struct AdjListNode {
	int dest;
	int weight;
	struct AdjListNode* next;
};

struct AdjList {
	struct AdjListNode* head;
};

struct Graph {
	int V;
	struct AdjList* array;
};

struct AdjListNode* newAdjListNode(int dest, int weight)
{
	struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
	newNode->dest = dest;
	newNode->weight = weight;
	newNode->next = NULL;
	return newNode;
}

struct Graph* createGraph(int V)
{
	struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
	graph->V = V;

	
	graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));

	
	for (int i = 0; i < V; ++i)
		graph->array[i].head = NULL;

	return graph;
}

void addEdge(struct Graph* graph, int src, int dest, int weight)
{
	struct AdjListNode* newNode = newAdjListNode(dest, weight);
	newNode->next = graph->array[src].head;
	graph->array[src].head = newNode;

}


struct MinHeapNode {
	int v;
	int key;
};


struct MinHeap {
	int size; 
	int capacity; 
	int* pos; 
	struct MinHeapNode** array;
};


struct MinHeapNode* newMinHeapNode(int v, int key)
{
	struct MinHeapNode* minHeapNode = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
	minHeapNode->v = v;
	minHeapNode->key = key;
	return minHeapNode;
}
struct MinHeap* createMinHeap(int capacity)
{
	struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
	minHeap->pos = (int*)malloc(capacity * sizeof(int));
	minHeap->size = 0;
	minHeap->capacity = capacity;
	minHeap->array = (struct MinHeapNode**)malloc(capacity * sizeof(struct MinHeapNode*));
	return minHeap;
}


void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b)
{
	struct MinHeapNode* t = *a;
	*a = *b;
	*b = t;
}



void minHeapify(struct MinHeap* minHeap, int idx)
{
	int smallest, left, right;
	smallest = idx;
	left = 2 * idx + 1;
	right = 2 * idx + 2;

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

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

	if (smallest != idx) {
		
		struct MinHeapNode* smallestNode = minHeap->array[smallest];
        struct MinHeapNode* idxNode = minHeap->array[idx];

		
		minHeap->pos[smallestNode->v] = idx;
		minHeap->pos[idxNode->v] = smallest;

		
		swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);

		minHeapify(minHeap, smallest);
	}
}
int isEmpty(struct MinHeap* minHeap)
{
	return minHeap->size == 0;
}


struct MinHeapNode* extractMin(struct MinHeap* minHeap)
{
	if (isEmpty(minHeap))
		return NULL;

	
	struct MinHeapNode* root = minHeap->array[0];

	
	struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
	minHeap->array[0] = lastNode;

	
	minHeap->pos[root->v] = minHeap->size - 1;
	minHeap->pos[lastNode->v] = 0;

	
	--minHeap->size;
	minHeapify(minHeap, 0);

	return root;
}



void decreaseKey(struct MinHeap* minHeap, int v, int key)
{
	
	int i = minHeap->pos[v];

	
	minHeap->array[i]->key = key;

	
	while (i && minHeap->array[i]->key < minHeap->array[(i - 1) / 2]->key) {
		minHeap->pos[minHeap->array[i]->v] = (i - 1) / 2;
		minHeap->pos[minHeap->array[(i - 1) / 2]->v] = i;
		swapMinHeapNode(&minHeap->array[i], &minHeap->array[(i - 1) / 2]);

		i = (i - 1) / 2;
	}
}


int isInMinHeap(struct MinHeap* minHeap, int v)
{
	if (minHeap->pos[v] < minHeap->size)
		return 1;
	return 0;
}


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


void PrimMST(struct Graph* graph)
{
	int V = graph->V;
	int parent[V]; 
	int key[V];
struct MinHeap* minHeap = createMinHeap(V);

	
	for (int v = 1; v < V; ++v) {
		parent[v] = -1;
		key[v] = INT_MAX;
		minHeap->array[v] = newMinHeapNode(v, key[v]);
		minHeap->pos[v] = v;
	}

	
	key[0] = 0;
	minHeap->array[0] = newMinHeapNode(0, key[0]);
	minHeap->pos[0] = 0;

	
	minHeap->size = V;

	
	while (!isEmpty(minHeap)) {
		
		struct MinHeapNode* minHeapNode = extractMin(minHeap);
		int u = minHeapNode->v; 
        weight = weight + minHeapNode->key;

		
		struct AdjListNode* pCrawl = graph->array[u].head;
		while (pCrawl != NULL) {
			int v = pCrawl->dest;

			
			if (isInMinHeap(minHeap, v) && pCrawl->weight < key[v]) {
				key[v] = pCrawl->weight;
				parent[v] = u;
				decreaseKey(minHeap, v, key[v]);
			}
			pCrawl = pCrawl->next;
		}
	}

	printf("\nMST :\n\n");
	printArr(parent, V);
    printf("\nWeight : %d",weight);
}
int main()
{
	
	int V = 9;
	struct Graph* graph = createGraph(V);

    addEdge(graph,0,1,4);
    addEdge(graph,0,7,8);
    addEdge(graph,1,0,4);
    addEdge(graph,1,2,8);
    addEdge(graph,1,7,11);
    addEdge(graph,2,1,8);
    addEdge(graph,2,3,7);
    addEdge(graph,2,5,4);
    addEdge(graph,2,8,2);
    addEdge(graph,3,2,7);
    addEdge(graph,3,4,9);
    addEdge(graph,3,5,14);
    addEdge(graph,4,3,9);
    addEdge(graph,4,5,10);
    addEdge(graph,5,2,4);
    addEdge(graph,5,3,14);
    addEdge(graph,5,4,10);
    addEdge(graph,5,6,2);
    addEdge(graph,6,5,2);
    addEdge(graph,6,7,3);
    addEdge(graph,6,8,6);
    addEdge(graph,7,0,8);
    addEdge(graph,7,1,11);
    addEdge(graph,7,6,1);
    addEdge(graph,7,8,7);
    addEdge(graph,8,2,2);
    addEdge(graph,8,6,2);
    addEdge(graph,8,7,7);


    struct AdjListNode* ptr;
    printf("\nAdjacent List : \n\n");
    for(int i=0;i<V;i++)
    {
        printf("%d : ",i);
        ptr = graph->array[i].head;
        while(ptr!=NULL)
        {
            printf("(%d, %d) -> ",ptr->dest,ptr->weight);
            ptr = ptr->next;
        }
        printf("\n");
    }

	PrimMST(graph);

	return 0;
}






OUTPUT : 
Adjacent List : 

0 : (7, 8) -> (1, 4) -> 
1 : (7, 11) -> (2, 8) -> (0, 4) -> 
2 : (8, 2) -> (5, 4) -> (3, 7) -> (1, 8) -> 
3 : (5, 14) -> (4, 9) -> (2, 7) -> 
4 : (5, 10) -> (3, 9) -> 
5 : (6, 2) -> (4, 10) -> (3, 14) -> (2, 4) -> 
6 : (8, 6) -> (7, 3) -> (5, 2) -> 
7 : (8, 7) -> (6, 1) -> (1, 11) -> (0, 8) -> 
8 : (7, 7) -> (6, 2) -> (2, 2) -> 

MST :

0 - 1
5 - 2
2 - 3
3 - 4
6 - 5
7 - 6


//permutation

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

int comparisons=0;

void swap_sort(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
    comparisons++;
}

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

int partition_lumoto(int *arr, int lo, int hi)
{
    int pivot = arr[hi];
    int i=lo-1;
    for(int j=lo;j<hi;j++)
    {
        if(arr[j]<pivot)
        {
            i++;
            swap_sort(&arr[i], &arr[j]);
        }
    }
    swap_sort(&arr[i+1], &arr[hi]);
    return (i+1);
}

void quicksort(int *arr, int lo, int hi)
{
    if(lo<hi)
    {
        int q = partition_lumoto(arr,lo,hi);
        quicksort(arr,lo,q-1);
        quicksort(arr,q+1,hi);
    }
}

int duplicate(int *arr, int lo, int hi)
{
    for(int i=lo;i<hi;i++)
    {
        if(arr[i]==arr[hi])
            return 0;
    }
    return 1;   
}

void permute(int *arr, int lo, int hi)
{
    int i, a[6]; //change value of a[6] here when increasing/decreasing array size
    if(lo==hi)
    {
        printf("[");
        for(i=0;i<=hi;i++){
            //printf(" %d ", arr[i]);
            a[i] = arr[i];}
        for(i=0;i<=hi;i++)
            printf(" %d ",a[i]);
        printf("]\n");
        quicksort(a,0,5); //change value of quicksort() here when increasing/decreasing array size
        printf("[");
        for(i=0;i<=hi;i++)
            printf(" %d ",a[i]);
        printf("]\n\n");
        return;
    }
    else
    {
        for(i=lo;i<=hi;i++)
        {
            if(duplicate(arr,lo,hi))
            {
                swap(&arr[i], &arr[lo]);
                permute(arr,lo+1,hi);
                swap(&arr[i], &arr[lo]);
            }
        }
    }
}

int main()
{
    int arr[] = {1,2,3,4,5,6};
    //quicksort(test,0,4);
    permute(arr,0,5); //change value of permute() here when increasing/decreasing array size
    printf("Total comparisons : %d", comparisons/120); //change factorial value accordingly
    return 0;
}


// matrix multiplication
#include<stdio.h>
#include<stdlib.h>

int costMatrix[100][100];  //2-D array to store the cost for each pair of matrices
int parenthesis[100][100];  //2-D array to store the parenthesis for each pair of matrices

int multiplicationCost (int arr[], int i, int j)
{
    if (i == j)  //To multiply the same matrix the cost is 0
    {
        costMatrix[i][j] = 0;
        parenthesis[i][j] = 0;
        return 0;
    }
    int count;
    int min = 100000;  //Initialize the minimum cost to a large value
    int min_parenthesis;
    for (int k = i; k < j; k++)  // k loops from i to j - 1 to represent the different position of the parenthesis
    {
        count = multiplicationCost(arr, i, k) + multiplicationCost(arr, k + 1, j) + arr[i - 1] * arr[k] * arr[j];
        //recursive call to calculate the cost of multiplying the matrices from i to k and k + 1 to j
        if (count < min)  //update the minimum cost and the parenthesis position if a lower cost is discovered
        {
            min = count;
            min_parenthesis = k;
        }
    }
    parenthesis[i][j] = min_parenthesis;  //store the parenthesis position
    costMatrix[i][j] = min;  //store the minimum cost
    return min;
}

//function to print the parenthesis
void printParenthesis(int arr[], int i, int j)
{
    if (i == j) //if only one matrix is left, print the matrix
    {
        printf(" A%d ", i);
        return;
    }
    int k = parenthesis[i][j];  //get the parenthesis position
    printf("(");  //print the parenthesis
    printParenthesis(arr, i, k);  // Recursively put brackets around subexpression from i to k
    printParenthesis(arr, k + 1, j);  // Recursively put brackets around subexpression from k + 1 to j
    printf(")");  //print the parenthesis
}

int main()
{
int arr[] = {100, 50, 30, 10};  //input array
    int n = sizeof(arr) / sizeof(arr[0]); // size of array
    printf ("\nThe input matrices are:\n");
    for (int i = 0; i < n - 1; i++)
        printf ("A%d: %d x %d\n", i + 1, arr[i] , arr[i + 1]);
    //call the function to create the arrays
    multiplicationCost(arr, 1, n - 1);  //call the function to create the arrays
    printf("\nCost Matrix:\n");
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            printf("%d\t", costMatrix[i][j]);
        }
        printf("\n");
    }
    printf("\nParenthesis Matrix:\n");
    for (int i = 1; i < n; i++)
    {
        for (int j = 1; j < n; j++)
        {
            printf("%d\t", parenthesis[i][j]);
        }
        printf("\n");
    }
    printf ("\nThe minimum cost is %d", costMatrix[1][n - 1]);
    printf ("\nThe optimal multiplication strategy is: ");
    printParenthesis(arr, 1, n - 1);  //call the function to print the parenthesis
    printf("\n");
    return 0;
}