CS422, Algorithms

//Shawn O'Neil CS422 Linear Time Selection Winter 04
// found the 100th element (from beginning) in a list of 2,000,000, sorted last to first (2000000 ..... 0)
// in 50 seconds, using ~100 MBs of memory!

#include <iostream>
#include <string>

using namespace std;

string* getInput(int s);
string* breakIntoFifth(int n, string *input, int *fifthlength);
string getElement(string *input, int n, int k, bool median);
string linSelSort(string *input, int n, int k);

//handles input and output
//line 1: number of elements in input (s)
//lines 2 through s+1: inputs into the input array (str)
//line s+2: the element to look for
int main()
	{
	while(1)
		{
		int s = 0;
		int k = 0;
		
		cin >> s;
		if (s == 0)
				exit(0);
		else
			{
			string *str = getInput(s);
			cin >> k;
			string answer = linSelSort(str, s, k);

			//cout << "The " << k << "th element is " << answer << endl;
			cout << answer << endl;
			//delete[] str;
			}
		}
	}
	
//returns the k'th element in a list *input n long, in n time.
string linSelSort(string *input, int n, int k)
	{
	if(n < 6) return getElement(input, n, k, false);
	else
		{
		string output;
		int lengthoffifth = 0;
		string *fifth = breakIntoFifth(n, input, &lengthoffifth);
		string pivot = linSelSort(fifth, lengthoffifth, (int)lengthoffifth/2);
		string *bef = new string[n]; int befct = 0;
		string *eq = new string[n]; int eqct = 0;
		string *aft = new string[n]; int aftct = 0;
		
		for(int i = 0; i < n; i++)
			{
			if(pivot.compare(input[i]) > 0) //pivot is greater than input[i]
				{ bef[befct] = input[i]; befct++; }
			else if(pivot.compare(input[i]) == 0) //pivot is equal to input[i]
				{ eq[eqct] = input[i]; eqct++; }
			else if(pivot.compare(input[i]) < 0) //pivot is less than input[i]
				{ aft[aftct] = input[i]; aftct++; }
			}
		
		string *returning;
		if(k <= befct) 	
			{
			returning = bef;
			n = befct;
			}
		else if(k > befct+eqct) 
			{
			returning = aft;
			k = k - befct - eqct;
			n = aftct;
			}
		else return eq[0];
		output = linSelSort(returning, n, k);
		delete[] fifth;
		delete[] bef;
		delete[] eq;
		delete[] aft;
		//delete[] input;
		return output;
		}
	}
	
//breaks an array into chunks of five, returning an array 1/5 the size made out the medians of the chunks
string* breakIntoFifth(int n, string *input, int *fifthlength)
	{
	int lenoutput = 0;
	if(n%5 == 0) lenoutput = n/5;
	else lenoutput = (int)(n/5)+1;
	*fifthlength = lenoutput;
	string *output = new string[lenoutput];
	
	string *chunk = new string[5];
	int chunkpos = 0;
	int outputpos = 0;
	for(int i = 0; i < n; i++)
		{
		chunk[chunkpos] = input[i];
		if(chunkpos == 4 || i == n-1) //if we run out of room in our chunk or we are at the end of the input
			{
			output[outputpos] = getElement(chunk, chunkpos, 0, true);
			outputpos++;
			chunkpos = 0;
			}
		else
			chunkpos++;
		}
	delete[] chunk;
	return output;
	}

//given s, reads the next s lines from standard in, buildig and array of string to return
string *getInput(int s)
	{
	string *array;
	array = new string[s];
	string bogus;
	getline(cin, bogus);
	for(int i = 0; i < s; i++)
		{
		getline(cin, array[i]);
		}	
	return array;
	}
	
//brute force get an element from the list
//if median = true, returns the median
//else returns the kth element
//Bubble sort is constant time on a limited size input ;-)
string getElement(string *input, int n, int k, bool median)
	{
	if(n == 1) return input[0];
	string output;
	bool sorted = false;
	while(!sorted)
		{
		sorted = true;
		for(int i = 0; i < n-1; i++)
			{
			if(input[i].compare(input[i+1]) > 0)
				{
				string temp = input[i];
				input[i] = input[i+1];
				input[i+1] = temp;
				sorted = false;
				}
			}
		}
	if(median == true)
		return input[(int)n/2];
	else if(k <= n)
		return input[k-1];
	string sucker = "sucker, you asked for an element outside the list";
	return sucker;
	}

// Shawn O'Neil Dynamic Programming for optimal Matrix Multiplication,  Algorithms with Andy Poe Winter 04 

#include <iostream>
using namespace std;

int* getInput(int nummats);
void computeTable(int nummats, int* dimsarray);
void printOut(int **mults, int **divides, int nummats, int row, int col);

//Main method, calls IO and handes the case for only 1 matrix.
int main()
	{
	int nummats = 0;
	cout << "Please enter number of matrices:  ";
	cin >> nummats;
	if(nummats == 1)
		cout << "You need zero multiplications." << endl;
	else
		{
		int *dimsarray = getInput(nummats);
		computeTable(nummats, dimsarray);
		}
	}

//given a number of matrices, and an array of dimensions (size 1+nummats)
//computes the table of the least amount of multiplies from matrices a through b
//where this is stored in mults[a][b] (arrays start at 0, that is the number
//of mults required for the first through third arrays are stored in mults[0][2])
//and computes the appropropriate divide point for each multipilication in divides
void computeTable(int nummats, int* dimsarray)
	{
	int **mults = new int*[nummats];
	int **divides = new int*[nummats];
	for(int i = 0; i < nummats; i++)
		{
		mults[i] = new int[nummats];
		divides[i] = new int[nummats];
		}
	for(int i = 0; i < nummats; i++)
		for(int j = 0; j < nummats; j++)
			{mults[i][j] = -1; divides[i][j] = -1;}
	for(int i = 0; i < nummats; i++)
		mults[i][i] = 0;
	
	int y = 0;
	for(int i = 1; i < nummats; i++)
		{
		y = 0;
		for(int x = i; x < nummats; x++)
			{
			//here is where the order we want happens within the array, for x,y
			//so what is the least number of multiplications to multiply arrays y through x?
			//cout << x << "," << y << endl;
			//int othermults = mults[x-1][y];
			//if(mults[x][y+1] < othermults) othermults = mults[x][y+1];
			int togethermults = 0;
			if(x-y < 2)
				{
				togethermults = dimsarray[y]*dimsarray[x]*dimsarray[x+1];
				}
			else
				{
				for(int div = y; div < x; div++) 	//divide after the divide number
					{
					int temp = dimsarray[y]*dimsarray[div+1]*dimsarray[x+1];
					temp += mults[div][y];
					temp += mults[x][div+1];
					if(temp < togethermults || togethermults == 0) 
						{
						togethermults = temp;
						divides[x][y] = div;
						}
					}
				}
			
			mults[x][y] = togethermults;
			//increment the y at the end
			y++;
			}
		}
	cout << "You need " << mults[nummats-1][0] << " multiplications." << endl;
	printOut(mults, divides, nummats, 0, nummats-1);
	cout << endl;
	}


//given a divides matrix and a row and column, prints out
//the parenthatized multiplation pattern for the optimal
//matrix multiplication of matrices row through column (again starting at 0)
// nummults = 5, 1,2,3,4,5,6 should be (((( 1 2 ) 3 ) 4 ) 5 )
// or in my format, (((( 0 1 ) 2 ) 3 ) 4 )
void printOut(int **mults, int **divides, int nummats, int row, int col)
	{
	//cout << "row is " << row << " col is " << col << endl;
	if(col-row == 0) cout << " " << row+1 << " ";
	else if(col-row == 1) cout << "( " << row+1 << "  " << row+2 << " )";//cout << "( "<< row << " " << row+1 << " )" << " ";
	else
		{
		int divide = divides[col][row];
		cout << "(";
		printOut(mults, divides, nummats, row, divide);

		printOut(mults, divides, nummats, divide+1, col);
		cout << ")";
		}
	}


//handes input, given a number of matrices, asks for the dimensions and returns them in an array
int* getInput(int nummats)
	{
	int *array;
	array = new int[nummats+1];
	for(int i = 0; i < nummats+1; i++)
		{
		if(i == 0) cout << "Please enter the number of rows in matrix 1:  ";
		else if(i == nummats) cout << "Please enter the number of columns in matrix " << nummats << ":  ";
		else cout << "Please enter the number of columns in matrix " << i << " and rows in matrix " << i+1 << ":  ";
		cin >> array[i];
		}
	return array;
	}

//Shawn O'Neil RSA encrypt/decrypt and factor to crack, this will run slow ;-)

#include <iostream>
using namespace std;

int AtoEmodM(int A, int e, int M);
int findPhiM(int M);
int findD(int e,int PhiM);


//Main method, handles input and output, YAY!!!!!!
int main()
	{
	string command;
	int N;
	int e;
	int M;
	while(command != "QUIT")
		{
		cin >> command;
		if(cin.eof()) return 0;
		if(command == "ENCRYPT")
			{
			cin >> N;
			cin >> e;
			cin >> M;
			cout << AtoEmodM(M,e,N) << endl;
			}
		else if(command == "DECRYPT")
			{
			cin >> N;
			cin >> e;
			cout << findD(e, findPhiM(N)) << endl;
			}
		command = "bogusnesssdude";
		}
	}

//finds D given, e, PhiM where (d*e)%PhiM = 1
int findD(int e, int PhiM)
	{
	int* row0 = new int[3];
	int* row1 = new int[3];
	int* row2 = new int[3];
	row0[0] = 0; row0[1] = PhiM; row0[2] = 0;
	row1[2] = 1; row1[1] = e;
	row2[1] = 7334;
	while(row2[1] > 1)
		{
		row1[0] = row0[1]/row1[1];
		row2[2] = row0[2]-(row1[0]*row1[2]);
		row2[1] = row0[1]-(row0[1]/row1[1]*row1[1]);
		
		int* temp = row0;
		row0 = row1;
		row1 = row2;
		row2 = new int[3];
		for(int i = 0; i < 3; i++) row2[i] = row1[i];
		delete[] temp;
		}
	
	int answer = row2[2];
	while(answer < 0)
		answer = answer+PhiM;
	return answer;
	}

//Factors M to the first two factors it finds p and q, and returns (p-1)(q-1)
int findPhiM(int M)
	{
	int p = 2;
	int q = 0;
	while(M/p*p != M) p++;
	q = M/p;
	p--;q--;
	return p*q;
	}
	
//returns A^e%M in a fast manner
int AtoEmodM(int A, int e, int M)
	{
	int lastleft = 1;
	int nextleft = A;
	int runningproduct = 1;
	while(e >= 1)
		{
		if(e/2*2 != e) runningproduct = runningproduct * nextleft % M;
		lastleft = nextleft;
		nextleft = lastleft * lastleft % M;
		e = e/2;
		}
	return runningproduct;
	}