 C++ Programming Algorithms

Subject Computer Science C-Family Programming

Question

1. In this problem, you are required to write a program to implement the ClosestPair algorithm

2. In this problem, you are required to write a program to implement the LongestCommonSubsequence algorithm

Once your program in implemented, you can demonstrate that it works using the sequences
X = <s, k, u, l, l, a, n, d, c, r, o, s, s, b, o, n, e, s>
and
Y = <l, u, l, l, a, b, i, e, s, f, o, r, b, a, b, i, e, s>.

3. In this problem, you are required to write a program to implement the NaïveBayes algorithm

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

1.

PointPair ClosestPair(vector<pair<int, int> > &pX, vector<pair<int, int> > &pY, int n)
{
vector<pair<int, int> > pXL, pXR, pYL, pYR, pYC;
PointPair clPL, clPR, clP;
int j, k;
double minDistance;

// if the number of points is not greater than 3, find closest pair by brutal force
if (n <= 3)
{
clP = BruteForce(pX, n);
}
else
{
int middle = (n - 1) / 2; // the element in the middle of the array
int x = pX[middle].first;
int y = pX[middle].second;
pXL.resize(n);
pXR.resize(n);
pYL.resize(n);
pYR.resize(n);
// split the array in two
// make the first half array
for (int i = 0; i <= middle; i++)
{
pXL[i] = pX[i];
}
j = 0;
// make the second half array
for (int i = middle + 1; i < n; i++)
{
pXR[j] = pX[i];
j++;
}
j = 0;
k = 0;

//split the other array to two
for (int i = 0; i < n; i++)
{
// put in first array the points where x is less than in middle element, or same with y not greater than the middle elements and the number of elements in first array is less than the half of number of all elements
if ((pY[i].first < x) || ((pY[i].first == x) && (pY[i].second <= y) && (j <= middle)))
{
pYL[j] = pY[i];
j++;
}
else // else put point to the second array
{
pYR[k] = pY[i];
}
}
clPL = ClosestPair(pXL, pYL, j); // call the function recursivaly with left points
clPR = ClosestPair(pXR, pYR, k); // call the function recursivaly with right points
clP = MinPair(clPL, clPR); // find the minimum distance comparing the minimum distances returned from recursive calls
minDistance = distance(clP.p1, clP.p2);
// make an array with points closer than minimum distance to the splitting line
for (int i = 0; i < n; i++)
{...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

Parsing Line Input in C++ \$28.00
Programming
Computer Science
C++
Classes
ASCII Files
Individual Words
Arrays
Reverse Order
OOP
Functions
Algorithms
Parsing Lines
Strings
Loops
Output
Memory Leaks
One Line Object
C: Multiple Programs \$68.00
C
Computer
Science
Remove
Occurrences
Character
String
Pointer
Functioin
Local
Rmchr
Rmstr
Record
Monitor
Screen
Program For Retail Store Using C++ \$30.00
Programming
C++
Computer Science
Coding
Walmart
Amazon
Sales
Products
Prices
Structures
Orders
Arrays
CSV Files
Variables
Statements
Prototypes
Pointers
A C++ Class That Will Manage an Encrypted Password \$48.00
C++