algoprep

actselector.cpp

#include <iostream>
#include <cstdlib>
#include <algorithm>
#include "algoprep.h"
using namespace std;

struct activity {
int s;
int f;
};

bool operator< (activity a, activity b) {
return (a.f < b.f);	
}

activity *actselector(activity* actlist, int n, int* nia) {
activity* A = NULL;
A = new activity[n];
int ni = 0;
A[ni] = actlist[0];
ni++;
int j = 0;
for(int i = 1; i < n; i++) {
	if(actlist[i].s >= actlist[j].f) {
	A[ni] = actlist[i];
	ni++;
	j = i;	
	}
}
*nia = ni;
return A;
}

int main() {
	cout << "Number of activities: ";
	int n;
	cin >> n;
	activity* actlist = NULL;
	actlist = new activity[n];
	for(int i = 0; i < n; i++) {
		cout << "Start time of activity " << i << ":" << endl;
		cin >> actlist[i].s;
		cout << "Finish time of activity " << i << ":" << endl;
		cin >> actlist[i].f;
	}
	cout << "Sorting activity list..." << endl;
	sort(actlist, actlist+n);
	cout << "Sorted activity list: " << endl;
	for(int i = 0; i < n; i++) {
		cout << "actlist[" << i << "] = {s: " << actlist[i].s << ", f: " << actlist[i].f << "}" << endl;	
	}
	cout << "Starting activity selector..." << endl;
	activity *A;
	int nia;
	A = actselector(actlist, n, &nia);
	cout << "Selected activities: " << endl;
	for(int i = 0; i < nia; i++) {
		cout << "A[" << i << "] = {s: " << A[i].s << ", f: " << A[i].f << "}" << endl;
	}
return EXIT_SUCCESS;
}

algoprep.cpp

#include <iostream>
#include <cstdlib>
using namespace std;

struct bst {
int key;
bst* left;
bst* right;
bst* p;
};

void display_tab(int *tab, int n) {
cout << "***display_tab***" << endl;
for(int i = 0; i < n; i++) {
cout << tab[i] << " ";
}
cout << endl << "*****************" << endl;
return;
}

void display_tab_part(int *tab, int begin, int end) {
cout << "***display_tab_part***" << endl;
for(int i = begin; i <= end; i++) {
cout << tab[i] << " ";
}
cout << endl << "**********************" << endl;
return;
}

void display_matrix(int **matrix, int n, int m) {
cout << "***display_matrix***" << endl;
for(int i = 0; i < n; i++) {
	for(int j = 0; j < m; j++) {
	cout << matrix[i][j] << " ";	
	}
	cout << endl;
}
cout << "********************" << endl;
}

int* gen_tab(int *tab, int n, int rbegin, int rend) {
cout << "***gen_tab***" << endl;
srand(time(NULL));
for(int i = 0; i < n; i++) {
tab[i] = (rand()%(rend-rbegin+1))+rbegin;	
}
return tab;
}

int** gen_matrix(int **matrix, int n, int m, int rbegin, int rend) {
cout << "***gen_matrix***" << endl;
srand(time(NULL));
for(int i = 0; i < n; i++) {
	for(int j = 0; j < m; j++) {
matrix[i][j] = (rand()%(rend-rbegin+1))+rbegin;	
}
}
return matrix;
}

int* swap_tab(int *tab, int a, int b) {
	cout << "***swap_tab***" << endl << "tab[" << a << "] = " << tab[a] << " <-> tab[" << b << "] = " << tab[b] << endl << "**************" << endl;
int tmp;
tmp = tab[a];
tab[a] = tab[b];
tab[b] = tmp;
return tab;
}

void inorderbstwalk(bst* node) {
	if(node != NULL) {
		inorderbstwalk(node -> left);
		cout << node -> key << endl;
		inorderbstwalk(node -> right);
	}
}

bst *bstsearch(bst* node, int k) {
	if(node == NULL || k == node -> key) {
	return node;	
	}
	if(k < node -> key) {
	return bstsearch(node -> left, k);	
	} else {
	return bstsearch(node -> right, k);	
	}
}

bst *bstminimum(bst* node) {
	while (node -> left != NULL) {
		node = node -> left;
	}
	return node;
}

bst *bstmaximum(bst* node) {
	while (node -> right != NULL) {
	node = node -> right;	
	}
	return node;
}

bst *bstsuccessor(bst* node) {
	if(node -> right != NULL) {
		return bstminimum(node -> right);
	}
	bst* y = node -> p;
	while(y != NULL && node == node -> right) {
	node = y;
	y = y -> p;	
	}
	return y;
}

bst *bstinsert(bst* root, bst* z) {
	bst* y = NULL;
	bst* x = root;
	while(x != NULL) {
	y = x;
	if(z -> key < x -> key) {
	x = x -> left;	
	} else {
	x = x -> right;	
	}
	}
	z -> p = y;
	if(y == NULL) {
		root = z;
	} else if(z -> key < y -> key) {
	y -> left = z;	
	} else {
	y -> right = z;
	}
	return root;
}

bst *bstremove(bst* root, bst* z) {
	bst *y;
	if(z -> left == NULL || z -> right == NULL) {
		y = z;
	} else {
		y = bstsuccessor(z);
	}
	bst *x;
	if(y -> left != NULL) {
		x = y -> left;
	} else {
	x = y -> right;	
	}
	if(x != NULL) {
	x -> p = y -> p;	
	}
	if(y -> p == NULL) {
	root = x;
	return root;	
	} else if(y == y -> p -> left) {
		y -> p -> left = x;
	} else {
	y -> p -> right = x;	
	}
	if(y != z) {
	z -> key = x -> key;	
	}
	return y;
}

algoprep.h

#ifndef _ALGOPREP_H
#define _ALGOPREP_H
struct bst {
int key;
bst* left;
bst* right;
bst* p;
};
void display_tab(int*, int);
void display_tab_part(int*, int, int);
void display_matrix(int**, int, int);
int* gen_tab(int*, int, int, int);
int** gen_matrix(int**, int, int, int, int);
int* swap_tab(int*, int, int);
void inorderbstwalk(bst*);
bst *bstsearch(bst*, int);
bst *bstminimum(bst*);
bst *bstmaximum(bst*);
bst *bstsuccessor(bst*);
bst *bstinsert(bst*, bst*);
bst *bstremove(bst*, bst*);
#endif

bst.cpp

include <iostream>
#include <cstdlib>
#include "algoprep.h"
using namespace std;

int main() {
bst* root = NULL;
cout << "Number of ints: " << endl;
int num;
cin >> num;
for(int i = 0; i < num; i++) {
	cout << "Int: " << endl;
	int x;
	cin >> x;
	bst* act = NULL;
	act = new bst;
	act -> key = x;
	act -> left = NULL;
	act -> right = NULL;
	act -> p = NULL;
	root = bstinsert(root, act);	
}
cout << "BST Inorder Walk" << endl;
inorderbstwalk(root);
cout << "Number to search in the tree: " << endl;
int search;
cin >> search;
bst* sret = bstsearch(root, search);
if(sret == NULL) {
cout << "Number not found." << endl;	
} else {
cout << "Found number " << sret -> key << " at " << sret << endl;	
}
bst* min = bstminimum(root);
bst* max = bstmaximum(root);
cout << "Minimum: " << min -> key << " at " << min << endl << "Maximum: " << max -> key << " at " << max << endl;
bst* rsuc = bstsuccessor(root);
cout << "Root successor: " << rsuc -> key << " at " << rsuc << endl;
cout << "Removing tree..." << endl;
for(int i = 0; i < num; i++) {
root = bstremove(root, root);	
}
return EXIT_SUCCESS;
}

countingsort.cpp

#include <iostream>
#include <cstdlib>
#include "algoprep.h"
using namespace std;

int *countingsort(int *A, int *B, int n, int k) {
int *C = NULL;
C = new int[k];
for(int i = 0; i<k;i++) {
C[i] = 0;	
}
for(int i = 0; i<n;i++) {
cout << "Incrementing C[A[" << i << "]] -> C[" << A[i] << "]..." << endl;
C[A[i]]++;
}
cout << "C: " << endl;
display_tab(C, k);
for(int i = 1; i<k; i++) {
cout << "C[" << i << "] = C[" << i << "] + C[" << i-1 << "]..." << endl;
C[i] = C[i] + C[i-1];
}
cout << "C: " << endl;
display_tab(C, k);
for(int i = n-1; i >= 0; i--) {
cout << "B[C[A[" << i << "]]-1] -> B[C[" << A[i] << "]-1] -> B[" << C[A[i]]-1 << "] = A[" << i << "]..." << endl;
B[C[A[i]]-1] = A[i];
cout << "Decrementing C[A[" << i << "]] -> C[" << A[i] << "]..." << endl;
C[A[i]]--;
}
cout << "A: " << endl;
display_tab(A, n);
cout << "B: " << endl;
display_tab(B, n);
cout << "C: " << endl;
display_tab(C, k);
return B;
}

int main() {
int *tab = NULL;
tab = new int[10];
int *sorted = NULL;
sorted = new int[10];
cout << "Generating array..." << endl;
tab = gen_tab(tab, 10, 0, 100);
cout << "Generated array:" << endl;
display_tab(tab, 10);
cout << "Starting countingsort..." << endl;
sorted = countingsort(tab, sorted, 10, 100);
cout << "After sorting:" << endl;
display_tab(sorted, 10);
return EXIT_SUCCESS;	
}

insertionsort.cpp

#include <iostream>
#include <cstdlib>
#include "algoprep.h"
using namespace std;

int* insertionsort(int *A, int n) {
	int step = 1;
	for(int j = 1; j < n; j++) {
		cout << "Step: " << step << endl;
		int key = A[j];
		cout << "key: " << key << endl;
		int i = j-1;
		cout << "i: " << i << endl;
		while(i>=0 && A[i] > key) {
			cout << "Copying " << A[i] << " in place of " << A[i+1] << endl;
			A[i+1] = A[i];
			i--;
			cout << "i: " << i << endl;
			}
			cout << "Copying " << key << " in place of " << A[i+1] << endl;
		A[i+1] = key;
		display_tab(A, n);
		step++;
	}
	return A;
}

int main() {
int *tab = NULL;
tab = new int[10];
cout << "Generating array..." << endl;
tab = gen_tab(tab, 10, 0, 100);
cout << "Generated array:" << endl;
display_tab(tab, 10);
cout << "Starting insertionsort..." << endl;
tab = insertionsort(tab, 10);
cout << "After sorting:" << endl;
display_tab(tab, 10);
return EXIT_SUCCESS;
}

matrixmultiply.cpp

#include <iostream>
#include <cstdlib>
#include <unistd.h>
#include "algoprep.h"
using namespace std;

int **matrixmultiply(int **A, int xa, int ya, int **B, int xb, int yb, int **C) {
	if(ya != xb) {
	cerr << "Size error! Exiting..." << endl;
	exit(EXIT_FAILURE);	
	}
	C = new int*[xa];
	for(int i = 0; i < xa; i++) {
	C[i] = new int[yb];	
	}
	for(int i = 0; i < xa; i++) {
		for(int j = 0; j < yb; j++) {
		C[i][j] = 0;
		for(int k = 0; k < ya; k++) {
		C[i][j] += A[i][k] * B[k][j];	
		}
		}
	}
	return C;
}

int main() {
int **A = NULL;
A = new int*[5];
for(int i = 0; i<5; i++) {
A[i] = new int[5];	
}
int **B = NULL;
B = new int*[5];
for(int i = 0; i<5; i++) {
B[i] = new int[5];	
}
cout << "Generating matrix A..." << endl;
A = gen_matrix(A, 5, 5, 0, 100);
cout << "Generated matrix A:" << endl;
display_matrix(A, 5, 5);
sleep(1);
cout << "Generating matrix B..." << endl;
B = gen_matrix(B, 5, 5, 0, 100);
cout << "Generated matrix B:" << endl;
display_matrix(B, 5, 5);
cout << "Starting matrixmultiply..." << endl;
int** C = NULL;
C = matrixmultiply(A, 5, 5, B, 5, 5, C);
cout << "After multiplying - matrix C:" << endl;
display_matrix(C, 5, 5);
return EXIT_SUCCESS;
}

mergesort.cpp

#include <iostream>
#include <cstdlib>
#include <cmath>
#include "algoprep.h"
using namespace std;

int* merge(int* A, int p, int q, int r) {
	cout << "Merging: " << endl;
	display_tab_part(A, p, q);
	display_tab_part(A, q+1, r);
	int x = q;
	for(int i = x+1; i<=r; i++) {
		for(int j = p; j <= x; j++) {
			if(A[j] >= A[i]) {
				int tmp = A[i];
				for(int k = i; k > j; k--) {
				A[k] = A[k-1];	
				}
				A[j] = tmp;
				x++;
				break;
			}
		}
	}
	cout << "Merged: " << endl;
	display_tab_part(A, p, r);
	return A;
}

int* mergesort(int* A, int p, int r) {
	cout << "Sorting: " << endl;
	display_tab_part(A, p, r);
	int q;
	if(p<r) {
		q = floor((p+r+1)/2)-1;
	cout << "q: " << q << endl;
	A = mergesort(A, p, q);
	A = mergesort(A, q+1, r);
	A = merge(A, p, q, r);
	}
	return A;
}

int main() {
int *tab = NULL;
tab = new int[10];
cout << "Generating array..." << endl;
tab = gen_tab(tab, 10, 0, 100);
cout << "Generated array:" << endl;
display_tab(tab, 10);
cout << "Starting mergesort..." << endl;
tab = mergesort(tab, 0, 9);
cout << "After sorting:" << endl;
display_tab(tab, 10);
return EXIT_SUCCESS;
}

quicksort.cpp

#include <iostream>
#include <cstdlib>
#include "algoprep.h"
using namespace std;

int partition(int *tab, int p, int r) {
int pivot = tab[r];
cout << "Pivot: " << pivot << endl;
cout << "p: " << p << endl;
cout << "r: " << r << endl;
int i = p - 1;
cout << "i: " << i << endl;
for(int j = p; j < r; j++) {
	if(tab[j] <= pivot) {
	i++;
	tab = swap_tab(tab, i, j);
	}
}
tab =  swap_tab(tab, i+1, r);                 
return i+1;
}

int *quicksort(int* tab, int p, int r) {
	if(p < r) {
		cout << "Partitioning array:" << endl;
	display_tab_part(tab, p, r);
	int q = partition(tab, p, r);
	cout << "Sorting array:" << endl;
		display_tab_part(tab, p, q-1);
	tab = quicksort(tab, p, q-1);
	cout << "Sorting array:" << endl;
		display_tab_part(tab, q+1, r);
	tab = quicksort(tab, q+1, r);
	}
	return tab;
}

int main() {
int *tab = NULL;
tab = new int[10];
cout << "Generating array..." << endl;
tab = gen_tab(tab, 10, 0, 100);
cout << "Generated array:" << endl;
display_tab(tab, 10);
cout << "Starting quicksort..." << endl;
tab = quicksort(tab, 0, 9);
cout << "After sorting:" << endl;
display_tab(tab, 10);
return EXIT_SUCCESS;	
}

randquicksort.cpp

#include <iostream>
#include <cstdlib>
#include "algoprep.h"
using namespace std;


int partition(int *tab, int p, int r) {
int pivot = tab[r];
cout << "Pivot: " << pivot << endl;
cout << "p: " << p << endl;
cout << "r: " << r << endl;
int i = p - 1;
cout << "i: " << i << endl;
for(int j = p; j < r; j++) {
	if(tab[j] <= pivot) {
	i++;
	tab = swap_tab(tab, i, j);
	}
}
tab =  swap_tab(tab, i+1, r);
return i+1;
}

int randpartition(int *tab, int p, int r) {
srand(time(NULL));
int i = rand()%(r-p+1)+p;
cout << "randpartition: i: " << i << endl;
tab = swap_tab(tab, i, r);
return partition(tab, p, r);
}

int *randquicksort(int* tab, int p, int r) {
	if(p < r) {
		cout << "Partitioning array:" << endl;
		display_tab_part(tab, p, r);
	int q = randpartition(tab, p, r);
	cout << "Sorting array:" << endl;
		display_tab_part(tab, p, q-1);
	tab = randquicksort(tab, p, q-1);
	cout << "Sorting array:" << endl;
		display_tab_part(tab, q+1, r);
	tab = randquicksort(tab, q+1, r);
	}
	return tab;
}

int main() {
int *tab = NULL;
tab = new int[10];
cout << "Generating array..." << endl;
tab = gen_tab(tab, 10, 0, 100);
cout << "Generated array:" << endl;
display_tab(tab, 10);
cout << "Starting random quicksort..." << endl;
tab = randquicksort(tab, 0, 9);
cout << "After sorting:" << endl;
display_tab(tab, 10);
return EXIT_SUCCESS;	
}