c++ – Don

September 29, 2012 Software Development Post a Comment

Merge Sort Example in C++

A merge sort is a O(n log n) sorting algorithm. I show in this example how to implement a merge sort in c++ using recursion. This algorithm is a divide & conquer based algorithm.

/*****************************************************************************
* Merge Sort has O(nlogn) compute time. Splits the list into two sublists then
* merges them back together sorting them
*****************************************************************************/
void mergeSort(list<int> &myList)
{
list<int> listOne;
list<int> listTwo;

bool sorted = false;
while (!sorted)
{
split(myList, listOne, listTwo);
if (listTwo.size() == 0)
sorted = true;
merge(myList, listOne, listTwo);
}
return;
}

/*****************************************************************************
* Splits a list into 2 lists
*****************************************************************************/
void split(list<int> &myList, list<int> &listOne, list<int> &listTwo)
{

listOne.resize(0);
listTwo.resize(0);

//While not at end of list
list<int>::iterator it = myList.begin();
while (it != myList.end())
{
int lastItem = 0;
while (it != myList.end() && *it >= lastItem)
{
listOne.push_back(*it);
lastItem = *it;
it++;
}

lastItem = 0;
while (it != myList.end() && *it >= lastItem)
{
listTwo.push_back(*it);
lastItem = *it;
it++;
}
}
return;
}

/*****************************************************************************
* Merges 2 lists taking the smaller number each time from both lists. Then
* copies the remaining numbers over if there are any left
*****************************************************************************/
void merge(list<int> &merged, list<int> &listOne, list<int> &listTwo)
{
merged.resize(0);
list<int>::iterator itOne = listOne.begin();
list<int>::iterator itTwo = listTwo.begin();
while (itOne != listOne.end() || itTwo != listTwo.end())
{
if (*itOne < *itTwo)
{
merged.push_back(*itOne);
itOne++;
}
else
{
merged.push_back(*itTwo);
itTwo++;
}
}
//Reached end of list One
if (itOne == listOne.end())
while (itTwo != listTwo.end())
{
merged.push_back(*itTwo);
itTwo++;
}
else //Reached end of list Two
while (itOne != listOne.end())
{
merged.push_back(*itOne);
itOne++;
}
return;
}

Merge Sort Algorithm:

Divide the unsorted list into n sublists until each list contains 1 element. If the list has 1 element it is sorted!
Repeatedly merge the sublists to produce new sublists until there is only 1 sublist remaining. The final list will be sorted!

August 16, 2011 Software Development Post a Comment

Understanding Properties of Relations with C++

I’m going to attempt to explain relations and their different properties. This was a project in my discrete math class that I believe can help anyone to understand what relations are. Before I explain the code, here are the basic properties of relations with examples. In each example R is the given relation.

Reflexive – R is reflexive if every element relates to itself. {(1,1) (2,2)(3,3)}

Irreflexive – R is irreflexive if every element does not relate to itself. {(1,2) (1,3) (2,1) (2,3) (3,1) (3,2)}

Symmetric – R is symmetric if a relates to b (a->b), then b relates to a (b->a). {(1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2)}

Antisymmetric – R is antisymmetric if a relates to b (a->b), and b relates to a (b->a), then a must equal b (a = b). {(3,2) (3,3)}
– is antisymmetric
– is not antisymmetric

Asymmetric – if a relates to b (a->b), then b does not relate to a (b!->a). {(1,2) (3,1) (3,2)}

Transitive – if a relates to b (a->b), and b relates to c (b->c), then a relates to c (a->c).
– is transitive
– is not transitive

Now that we understand the properties we can talk about the code. The code takes in one argument from the command line that is the file with the Relation. The file needs to contain the relation in a matrix form like the examples above with the first number the size of the matrix. Here is an example:

The file above would be the following relation: {(1,2) (2,3)}. There are spaces to separate each cell of the matrix. After given a relation the program will output which properties hold and which ones don’t. We can study the source code to see how to test for each condition. I do not claim this program to be the most efficient way to determine the different relation properties. Please leave in the comments any questions or ideas that you might have.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334

/***************************************************************************
* Program:
*    Relations as Connection Matrices
* Author:
*    Don Page
* Summary:
*    Represents relations as connection (zero-one) matrices, and provides
*    functionality for testing properties of relations.
*
***************************************************************************/

#include <cmath>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <assert.h>
using namespace std;

class Relation
{
private:
bool** mMatrix;
int mSize;

void init()
{
mMatrix = new bool*[mSize];
for (int i = 0; i < mSize; i++)
{
mMatrix[i] = new bool[mSize];
}
}

public:
Relation(int size)
{
mSize = size;
init();
}

Relation& operator=(const Relation& rtSide)
{
if (this == &rtSide)
{
return *this;
}
else
{
mSize = rtSide.mSize;
for (int i = 0; i < mSize; i++)
{
delete [] mMatrix[i];
}
delete [] mMatrix;
init();
for (int x = 0; x < mSize; x++)
{
for (int y = 0; y < mSize; y++)
{
mMatrix[x][y] = rtSide[x][y];
}
}
}
return *this;
}

Relation(const Relation& relation)
{
mSize = relation.getConnectionMatrixSize();
init();
*this = relation;
}

~Relation()
{
for (int i = 0; i < mSize; i++)
{
delete [] mMatrix[i];
}
delete [] mMatrix;
}

bool isReflexive();
bool isIrreflexive();
bool isNonreflexive();
bool isSymmetric();
bool isAntisymmetric();
bool isAsymmetric();
bool isTransitive();
void describe();

int getConnectionMatrixSize() const
{
return mSize;
}

bool* operator[](int row) const
{
return mMatrix[row];
}

bool operator==(const Relation& relation)
{
int size = relation.getConnectionMatrixSize();
if (mSize != size)
{
return false;
}
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (mMatrix[i][j] != relation[i][j])
{
return false;
}
}
}
return true;
}

/****************************************************************************
* Returns product of 2 square matrices. Algorithm used from Rosen's Discrete
* Mathematics and Its Applications p.253
***************************************************************************/
Relation operator * (const Relation& relation)
{
// assume multiplying square matrices
assert(mSize == relation.getConnectionMatrixSize());
Relation product(mSize);
for (int i = 0; i < mSize; i++)
{
for (int j = 0; j < mSize; j++)
{
product.mMatrix[i][j] = 0;
for (int k = 0; k < mSize; k++)
{
product.mMatrix[i][j] = product.mMatrix[i][j] ||
(mMatrix[i][k] && relation.mMatrix[k][j]);
}
}
}

return product;
}

/****************************************************************************
* Matrix A is less than Matrix B iff there is a 1 in B everywhere there
* is a 1 in A
***************************************************************************/
bool operator <= (const Relation& relation)
{
for (int i = 0; i < mSize; i++)
{
for (int j = 0; j < mSize; j++)
{
if (mMatrix[i][j] && !relation.mMatrix[i][j])
return false;
}
}
return true;
}

};

ostream& operator<<(ostream& os, const Relation& relation)
{
int n = relation.getConnectionMatrixSize();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
os << relation[i][j] << " ";
}
os << endl;
}
return os;
}

istream& operator>>(istream& is, Relation& relation)
{
int n = relation.getConnectionMatrixSize();
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
is >> relation[i][j];
}
}
return is;
}

/****************************************************************************
* Relation Member Functions
***************************************************************************/
/****************************************************************************
* R is Reflexive if M[i][i] = 1 for all i
***************************************************************************/
bool Relation::isReflexive()
{
for (int i = 0; i < mSize; i++)
{
if (!mMatrix[i][i])
return false;
}
return true;
}

/****************************************************************************
* R is Irreflexive if M[i][i] = 0 for all i
***************************************************************************/
bool Relation::isIrreflexive()
{
for (int i = 0; i < mSize; i++)
{
if (mMatrix[i][i])
return false;
}
return true;
}

/****************************************************************************
* R is Nonreflexive if R is either not reflexive or not irreflexive. There
* is a more efficient way to test for nonreflexive, but for learning purposes
* I chose this inefficient way.
***************************************************************************/
bool Relation::isNonreflexive()
{
return (!(isReflexive() || isIrreflexive()));
}

/****************************************************************************
* R is Symmetric if for each M[i][j] = 1 , M[j][i] = 1 for all i,j
***************************************************************************/
bool Relation::isSymmetric()
{
for (int x = 0; x < mSize; x++)
{
for (int y = 0; y < mSize; y++)
{
if (mMatrix[x][y] && !mMatrix[y][x])
return false;
}
}
return true;
}

/****************************************************************************
* R is AntiSymmetric if for each M[i][j] = 1 and M[j][i] = 1, then i = j
* for all i,j
***************************************************************************/
bool Relation::isAntisymmetric()
{
for (int x = 0; x < mSize; x++)
{
for (int y = 0; y < mSize; y++)
{
if (mMatrix[x][y] && mMatrix[y][x] && (x != y))
return false;
}
}
return true;
}

/****************************************************************************
* R is Asymmetric if M[i][j] = 1, then M[j][i] != 1 for all i,j
***************************************************************************/
bool Relation::isAsymmetric()
{
for (int x = 0; x < mSize; x++)
{
for (int y = 0; y < mSize; y++)
{
if (mMatrix[x][y] && mMatrix[y][x])
return false;
}
}
return true;
}

/****************************************************************************
* R is Transitive if R^2 <= R. Another way to test if a relation is
* transitive would be if M[i][j] = 1, and M[j][k] = 1, then M[i][k] = 1.
* This would require 3 nested for loops.
***************************************************************************/
bool Relation::isTransitive()
{
Relation relation = *this;
Relation product = relation * relation;
return (product <= relation);
}

/****************************************************************************
* Describes the matrix after testing
* Reflextivity, Irreflextivity, NonReflextivity, Symmetry, AntiSymmetry,
* Asymmetry, and Transitivity
***************************************************************************/
void Relation::describe()
{
cout << "\nThe relation represented by the " << mSize << "x" << mSize << " matrix\n";
cout << *this << "is\n";
cout << (isReflexive() ? "" : "NOT ") << "Reflexive\n";
cout << (isIrreflexive() ? "" : "NOT ") << "Irreflexive\n";
cout << (isNonreflexive() ? "" : "NOT ") << "Nonreflexive\n";
cout << (isSymmetric() ? "" : "NOT ") << "Symmetric\n";
cout << (isAntisymmetric() ? "" : "NOT ") << "Antisymmetric\n";
cout << (isAsymmetric() ? "" : "NOT ") << "Asymmetric \n";
cout << (isTransitive() ? "" : "NOT ") << "Transitive.\n";
}

int main(int argc, char* argv[])
{
for (int i = 1; i < argc; i++)
{
string file = argv[i];
ifstream inFile(file.c_str());

if (inFile.is_open())
{
int size;
inFile >> size;
Relation relation(size);
inFile >> relation;
inFile.close();
relation.describe();
}
else
{
cout << "Unable to open " + file;
}
}

return 0;
}

June 18, 2011 Software Development Post a Comment

Bayesian Spam Filter

And God said let their be spam. And ever since, there was spam. It seems like spam these days never ends. It is a constant battle with no winners or losers. Sort of like the war on terrorism. But that’s a topic for another day. However, we are not all doomed. At least for now, thanks to Thomas Bayes and his bayesian spam filtering. So how does this bayes theorem work anyways? Let’s say a given spam has the word ‘free’ in it. We all know nothing is free these days. Bayes theorem states the following:

P(A|B) = [ P(B|A) * P(A) ] / P(B)
Read as: The probability of A given B is equal to the probability of B given A times the probability of A divided by the probability of B.

In our case lets specialize this formula to spam:
P(S|W) = [ P(W|S) * P(S) ] / [P(W|S) * P(S)] + [P(W|H) * P(H)]

Looks complicated I know. But it really isn’t.

P(S|W) is the probability that a message is a spam, knowing that the word “free” is in it.
P(S) is the overall probability that any given message is spam.
P(W|S) is the probability that the word “free” appears in spam messages.
P(H) is the overall probability that any given message is not spam (aka ham).
P(W|H) is the probability that the word “free” appears in ham messages.

But it does get complicated because we are dealing with multiple words. For multiple words the formula gets a little complicated.

P(S) = p(w1) * p(w2) * … / (p(w1) * p(w2)* … ) + (q(w1) * q(w2) * …)

Now that we have the details taken care of lets look at the code to a simple bayesian spam filter written in c++.

/***************************************************************************
* Program:
*    Bayesian Spam Filter
*
* Author:
*    Don Page
*
* Summary:
*    This program reads in a hypothetical list of words and frequencies
*    in both spam and ham e-mail messages and then uses Bayesian
*    inference to determine whether hypothetical e-mail messages are spam
*    or not. The program's judgment may be wrong in some cases, but such
*    is the case with industrial-strength spam filters as well.
******************************************************************************/

#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <ctype.h>

using namespace std;
class Words
{
private:
int numWords;
string words[200];
float spam[200];
float ham[200];
public:
Words();
int getIndex(string pWord);
float getSpam(string pWord);
float getHam(string pWord);
void insertWord(string pWord, float pSpam, float pHam);

};

/******************************************************************************
* Default Constructor
******************************************************************************/
Words::Words()
{
numWords = 0;
}

/******************************************************************************
* INPUT: pWord - Word to insert
*        pSpam - Probability of spam
*        pHam - Probability of ham
******************************************************************************/
void Words::insertWord(string pWord, float pSpam, float pHam)
{
words[numWords] = pWord;
spam[numWords] = pSpam;
ham[numWords]   = pHam;
numWords++;
}

/******************************************************************************
* Read words and their probabilities of being ham and spam from file
******************************************************************************/
Words* readWords(ifstream& words)
{
string word;
float spam;
float ham;
Words* myWords = new Words();

while(!words.eof())
{
words >> word;
words >> spam;
words >> ham;
myWords->insertWord(word, spam, ham);
}

return myWords;
}

/******************************************************************************
* Checks if word is inside spam list. Returns prob of spam or -1 if !found
******************************************************************************/
float Words::getSpam(string pWord)
{

int index = getIndex(pWord);
if (index != -1) // found
return spam[index];
else
return -1.0; // not found
}

/******************************************************************************
* Checks if word is inside ham list. Returns prob of ham or -1 if !found
******************************************************************************/
float Words::getHam(string pWord)
{

int index = getIndex(pWord);
if (index != -1) // found
return ham[index];
else
return -1.0; // not found
}

/******************************************************************************
* Finds a given word inside list of words. Returns -1 if not found
******************************************************************************/
int Words::getIndex(string pWord)
{
//Convert string to lowercase
for (int i = 0; i < pWord.length(); i++)
pWord[i] = tolower(pWord[i]);

int i = 0;
for (; words[i] != pWord && i < numWords; i++);

// Check to see if word was found
if (words[i] == pWord)
return i;
else
return -1;
}

/******************************************************************************
* Process each message using Bayes theorem to calculate if message is Spam
* or Ham. See below for Bayes thereom on multiple words.
* P(S) = p(w1) * p(w2) * ... / (p(w1) * p(w2)* ... ) + (q(w1) * q(w2) * ...)
******************************************************************************/
void processMessages(Words* words, ifstream& messages)
{
int message = 1;
string word;

float probSpam;
float probHam;
string cleanWord = "";
messages >> word;
while(!messages.eof())
{

messages >> word; // First word is message
probSpam = 0.0;
probHam = 0.0;
while (word != "MESSAGE" && !messages.eof()) // New message
{

//Parse word
for (int i = 0; i < word.length(); i++)
{
if (isalpha(word[i]))
{
cleanWord += word[i];
}
if (!isalpha(word[i]) || i == word.length() - 1) // Check cleanWord if it's spam
{
if (cleanWord.length() > 0)
{

float temp = words->getSpam(cleanWord);
if (temp > -1.0) // If Spam Calculate new probSpam
probSpam != 0.0 ? probSpam *= temp : probSpam = temp;

temp = words->getHam(cleanWord);
if (temp > -1.0) // If Ham Calculate new probHam
probHam != 0.0 ? probHam *= temp : probHam = temp;
cleanWord = "";

}
}

}// for
messages >> word;
}// while
// Should we reject message?
float threshold = probSpam / (probSpam + probHam);
cout << "Message " << message << " has a " << threshold << " probability of being spam, ";
if (threshold < .9) // Accept
cout << "so let it through.\n\n";
else // Reject
cout << "so reject it.\n\n";
message++;
}
return;
}

/******************************************************************************
* Opens two input files, words.txt and messages.txt, reads in the words and
* their spam/ham frequencies, and with that data processes the messages
* to determine if they (the messages) are spam or not.
*
* DO NOT MODIFY ANYTHING BELOW THIS LINE!
******************************************************************************/
int main(int argc, const char* argv[])
{
// Set decimal precision for output.
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);

if (argc < 3)
{
cerr << "Usage: " << argv[0] << " [words file] [messages file]\n";
exit(1);
}

ifstream words(argv[1]);

ifstream messages(argv[2]);

if (words.fail() || messages.fail())
{
cerr << "File opening failed.\n";
exit(1);
}

processMessages(readWords(words), messages);

return 0;
}

March 7, 2010 Software Development Post a Comment

Extended Euclidean Algorithm in C++

Writing an Extended Euclidean Calculator that calculates the inverse of a modulus can get pretty difficult. However writing a good algorithm and going through step by step can make the process so much easier. So we want to find a’ or inverse of a so that a * a’ [=] 1 (mod b). In other words we are trying to find an integer (a’) when multiplied by a and then divided by b gives you a remainder of 1. In order to find this number(a’), we have to work the Euclidean Algorithm backwards which is referred to as the Extended Euclidean Algorithm.

March 6, 2010 Software Development 4 Comments

Modular Exponentiation in C++

Modular Exponentiation is way of calculating the remainder when dividing an integer b (Base) by another integer m (Modulus) raised to the power e(Exponent). Fast modular exponentiation of large numbers is used all the time in RSA to encrypt/decrypt private information over the internet. Whenever you go to a secure site you are using RSA which deals with modular exponentiation.So lets understand modular exponentiation with c++!

March 6, 2010 Software Development 3 Comments

Fibonacci Calculator C++

The fibonacci sequence is as follows :

$0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots.$

Each successive number is equal to the sum of the two preceding numbers. If you wanted to find the 5th number of the sequence it would be 5.

F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂
0	1	1	2	3	5	8	13	21	34	55	89	144

This program is implemented with a double linked list. Each Fibonacci number stored as a sequence of integers inside of a list. For example to calculate the 6th number of the Fibonacci sequence it would start out with f1 and f2 lists that have a single node with 1 inside.

July 10, 2009 Software Development Post a Comment

How do I search for a filename in c++

Are you writing a program and need to know how to search for a specific file name? After searching around at msdn.microsoft.com and some trial and error I can show you how. I will be using FindFirstFile and FindNextFile to do my search.

June 14, 2009 Software Development 4 Comments

Sudoku Program in C++

Sudoku is one of my favorite games and I really enjoyed writing a sudoku solver. This sudoku procedural program was written in the language c++. The sudoku program allows you to input a board via a text file and allows you to save your progress. If you get stuck, the program can finish the board. I also spent the time to implement a colored board into the program. If you don’t understand the rules of sudoku or how to play sudoku then you can go here.

Search Site

Tag: c++