Problems and Teams
Due 5-2:
Results:
Problems:
Remember that the topic for this week is multithreading. So all of these should be done involving C++ libraries to support that.
#1 - Write a parallel matrix multiply. You can put it in a .cpp file and give it the following signature. Remember that these will be running on a 32 core machine. The inputs will range from small to very large.
vector<vector<double>> pMatrixMult(const vector<vector<double>> &a,const vector<vector<double>> &b);
#2 - Write a parallel mergesort. Put it in a file called "pmergesort.h" with the following signature. Remember that these will be running on a 32 core machine. The inputs will range from small to very large.
template<typename T>
void pmergesort(vector<T> &v);
#3 - Crafting
You are a great minecraftsman in the land of Minerim. You are tasked with looking at the market values of items that you can craft and then deciding, based on your inventory of raw materials, what items to craft in order to maximize your profit. You will do so by completing the following function in a .cpp file of your choosing.
int craft(const vector<Item> &inventory, const vector<pair<string,vector<Item>>> &recipes, const map<string,int> &values);
Put the following definition of Item in a file called "item.h" and include it in your .cpp. I will do the same so don't submit this file to the server, just your .cpp.
struct Item {
string name;
int amount;
};
The first argument to the function is the items that you start with. The second argument is the recipes. This is a vector of pairs with the item names in first and the list of things you need to make them in second. The last argument is a map you use to look up the values of the items. You want to return the maximum value of item value * amount of items that you can create using your inventory. There will be no more than 60 items in the initial inventory and no more than 10 recipes. The recipes form a dag and they will be given in an order that is a valid topological sort on that dag.
Teams:
A - James, Kendrick W., Miller, J. Hunter, Ha, Vivian
B - Wehner, Zacharias K., Fan, Irene, Kennedy, Rodney M.
C - Yin, Oliver, Schrock, Bryan R., Peake, Caulan J.
D - Garrick, Daniel J., Compton, Campbell B., Solcher, Zachary J.
E - Lamm, Allison R., Liu, Lu, Fox, Liam M.
F - Do, NamChi T., Conner, Zachary T., Bierman, Robert F.
G - Langbert, Zachary H., Steinbach, Peter A., Von Rosenberg-Miesch, Garrett C.
H - Pauls, Brittney U., Lavallee, Samantha D.
Due 4-23:
Results:
Problems:
#1 - Convex Hull
vector<int> convexHull(const vector<tuple<double,double>> &points);
The tuples in the input are (x,y) pairs. The return vector is the indices of the points in the convex hull in order going around the points. The first vertex should be the lowest point and the points should go around the hull in the counter clockwise direction.
#2 - Closest Points
tuple<int,int> closestPoints(const vector<tuple<double,double>> &points);
Returns a tuple with the indexes of the two closest points. The input tuples are (x,y) pairs.
#3 - String matching
int substringLocation(const string &a, const string &b);
Find the location of the first occurrence of b in a. If b does not occur in a, return -1.
Teams:
A - Fox, Liam M., Lavallee, Samantha D., Do, NamChi T.
B - Wehner, Zacharias K., Yin, Oliver, Pauls, Brittney U.
C - Compton, Campbell B., Conner, Zachary T., Miller, J. Hunter
D - Kennedy, Rodney M., Liu, Lu, Langbert, Zachary H.
E - Garrick, Daniel J., Ha, Vivian, Von Rosenberg-Miesch, Garrett C.
F - Bierman, Robert F., James, Kendrick W., Solcher, Zachary J.
G - Schrock, Bryan R., Fan, Irene, Steinbach, Peter A.
H - Lamm, Allison R., Peake, Caulan J.
Due 4-16:
Results:
Problems:
#1 - Doc Brown is working on a new design for his flux capacitor. He has a bunch of new data that he wants to analyze. Unfortunately, the overpriced license on his software for doing curve fitting has expired. He has turned to you to write software that will do the job for him.
template<class T,class F>
vector<double> fitFuncs(const vector<T> &data,const vector<F> &functions);
The type T will have members called .x and .y to get components of the data. The x and y will have type double. The type F is callable and takes a single double and returns a single double.
To help you understand the use of this function, consider the example of doing a fit for some data to a quadratic. So you want the form a*x^2+b*x+c that comes as close as possible to the specified data points. Your function would be passed the data points as well as a vectors of functions that represent x^2, x, and 1. Your return vector would have the values of a, b, and c.
Put your code in a file called "LinearFit.h".
#2 - Remember back in High School when you had to balance chemical equations? It's time to make a computer do that for you. For this problem you will be passed an unbalanced form of a chemical equation. You are supposed to return the lowest integer multiples of coefficients that balance the equation.
tuple<vector<int>,vector<int>> chemBalance(const string &equ);
The unbalanced equations might look like this: "CH4+O2=H2O+CO2". Element names will be a single uppercase letter or one uppercase followed by one lowercase. The return value has the integer coefficients for the terms to the left of the equals sign in the first vector and those to the right in the second vector. For the example input you would return {{1,2},{2,1}}. This represents 1*CH4+2*O2=2*H2O+1*CO2.
To understand how this relates to matrix math, consider the example above written in the following way: a*CH4+b*O2=c*H2O+d*CO2. Because the umber of elements of each type on each side must balance this leads to the following system of linear equations for C, H, and O respectively.
a = d
4*a = 2*c
2*b = c+2*d
We can expand this out by putting in coefficients for all the equations.
1*a+0*b = 0*c+1*d
4*a+0*b = 2*c+0*d
0*a+2*b = 1*c+2*d
This system is underdetermined because we have 4 unknowns and only 3 equations. To solve it, we assume that one of the coefficients is one. I typically assume the last coefficient is 1 and then move all constant terms to the right and all non-constant terms to the left. This produces the following:
1*a+0*b-0*c =1
4*a+0*b-2*c = 0
0*a+2*b-1*c = 2
Hopefully you can see how this has the form Ax=y, where A={{1,0,0},{4,0,-2},{0,2,-1}}, x={a,b,c}, and y={1,0,2}. Given this form, you can use your preferred technique to solve for x.
Put the code in whatever .cpp file you want.
Teams:
A - Fan, Irene, Von Rosenberg-Miesch, Garrett C., James, Kendrick W.
B - Conner, Zachary T., Lamm, Allison R., Do, NamChi T.
C - Yin, Oliver, Pauls, Brittney U., Solcher, Zachary J.
D - Peake, Caulan J., Miller, J. Hunter, Garrick, Daniel J.
E - Kennedy, Rodney M., Wehner, Zacharias K., Steinbach, Peter A.
F - Schrock, Bryan R., Compton, Campbell B., Fox, Liam M.
H - Ha, Vivian, Langbert, Zachary H., Lavallee, Samantha D.
G - Bierman, Robert F., Liu, Lu
Due 4-9:
Results:
Problems:
#1 - Shortest path using LP.
double shortestPathLP(int start,int end,const vector<vector<tuple<int,double>>> &graph);
The graph is an adjacency list with the int as the index and the double as the distance. The largest input you will be given has 150 vertices for a fairly sparse graph.
#2 - Minimum cost flow problem using LP.
double minimumCostFlowLP(int source,int sink,double totFlow,const vector<vector<tuple<int,,doubledouble>>> &graph);
The tuple contains vertex number, capacity, and cost per flow respectively. return the total cost of your solution.
#3 - Maximum flow using LP.
double maximumFlowLP(int source,int sink,const vector<vector<tuple<int,double>>> &graph);
The graph is an adjacency list with the index of the destination and a flow capacity. Return the value of the maximum flow.
Teams:
A - Liu, Lu, Compton, Campbell B., Pauls, Brittney U.
B - Yin, Oliver, Schrock, Bryan R., Fox, Liam M.
C - Ha, Vivian, Lavallee, Samantha D., Garrick, Daniel J.
D - Von Rosenberg-Miesch, Garrett C., Steinbach, Peter A., Lamm, Allison R.
E - Kennedy, Rodney M., Solcher, Zachary J., Wehner, Zacharias K.
F - Peake, Caulan J., Langbert, Zachary H., Miller, J. Hunter
G - James, Kendrick W., Bierman, Robert F., Conner, Zachary T.
H - Do, NamChi T., Fan, Irene
Due 4-2:
Results:
Problem:
#1 - Pete (the traveling sales person from last week's problems) has been expanding his courier network and he needs to know if the current network can handle the orders he is getting. All of his orders come in at one city and go out to the others. He is paying kids to bike things between cities and he knows how much weight can go between each pair of cities in his network each day. He doesn’t care exactly how long it takes for things to get from the delivery spot to their destination, as long as the courier network can keep up so that in a steady state there aren’t items piling up in any given city.
You are given the roads he has couriers working on and how many pounds of inventory can be carried down each day in a day. These have a direction as Pete has arranged for couriers to only carry inventory one way and just ride back not carrying anything. You also have how many pounds of items are to be sold in each city each day. Assume the number of pounds received in Pete’s home town is equal to the total orders. Your program needs to tell Pete if the courier network can handle the orders.
vector<tuple<int,int,int>> courierLoads(const vector<int> &orders, const vector<tuple<int,int,int>> &capacities);
The first input is the number of lbs of orders for each city. The first element will be 0. The second input is routes in the courier network. The values in each tuple are start city, end city, lbs of capacity. There will be no anti-parallel edges. You should return the flows in the same tuple format. If it isn't possible for the courier network to make the deliveries, return an empty vector. The maximum input size is 1000 cities and fairly dense.
Teams: None
Due 3-26
Results:
Problems:
#1 - Traveling Salesman Pete has amassed a dominant position in a vast empire of retail outlets for low quality goods. He needs to know how to get from his house to various places in the minimum distance and what that distance is. He is going to provide you with information on the distances between nearby locations and wants you to figure out the rest.
tuple<vector<int>,vector<int>> distanceFromHome(const vector<vector<tuple<int,int>>> &nearbyDistances);
The first index of the input is the location that Pete services. His house is at index 0. The vector for each location contains a tuple of indexes and distances. This first element in the returned tuple is distances from his home to each other location. The second vector is where you should come from to get to each vertex. That value should be -1 if you don't come there from anywhere. Note that distances can't be negative. You can have up to 2 million vertices and 200 million edges.
This is a non-templated function so simply write a .cpp file.
#2 - A local cross-country ski team is trying to determine some good routes through a plot of land that they have access to. They have had their team members all assign difficulties to branches of paths between junctions. The difficulty assignments can be negative for sections that are mostly downhill. They would like for you to return information on the difficulty in getting from any one location to any other location along the minimum difficulty path as well as information on those paths.
tuple<vector<vector<int>>,vector<vector<int>>> crossCountryChallenge(const vector<vector<int>> &difficulties);
The input is a complete matrix of difficulties. Note that it is not symmetric because the challenge of getting from point A to point B on skis might not be the same as going the other way around. Indeed, it might be possible to get from A to B, but not from B to A. If you can't get from one place to another they have given it a difficulty of 1 billion. The first element in the returned tuple should be a matrix of shortest path distances. The second element is a predecessor matrix for the routes in the shortest paths. The diagonal values in the predecessor matrix need to be -1. You can safely use 1 billion as the value of infinity. The maximum number of vertices in 500.
This is a non-templated function so simply write a .cpp file.
Teams:
A - Conner, Zachary T., Yin, Oliver, Peake, Caulan J.
B - Garrick, Daniel J., Miller, J. Hunter, Liu, Lu
C - Fan, Irene, Schrock, Bryan R., Fox, Liam M.
D - Lavallee, Samantha D., Compton, Campbell B., Pauls, Brittney U.
E - Solcher, Zachary J., Bierman, Robert F., James, Kendrick W.
F - Von Rosenberg-Miesch, Garrett C., Lamm, Allison R., Do, NamChi T.
G - Steinbach, Peter A., Langbert, Zachary H., Kennedy, Rodney M.
H - Ha, Vivian, Wehner, Zacharias K.
Due 3-19
Results:
Problems:
#1 - The city planners of Stupidville have this thing where they really like one way roads. Unfortunately, they aren't very good at planning them out and they have set up some really odd situations where you literally can't get one place from another. Lots of people in town simply ignore the rules and drive the wrong way occasionally, but you want to reduce this as much as possible. You have collected data on different locations that are significant to you and the one way direct connections. Now you need to write a program that tells you which groups of locations you can get around without breaking laws. So you want to return the different clusters of locations where each one can be reached from all the others without breaking a law.
vector<set<int> > drivingLegal(const vector<vector<int> > &roadTo);
The roadTo variable stores an adjacency list representation of the town. So roadTo.size() is the number of locations. Each subvector stores the indices of places you can get to directly via the one way roads. The input can have up to one million locations and 100 million different roads.
No templates so call your .cpp whatever you want.
#2 - Recently one of the frat parties at UC (short for Underfunded College) got a little out of hand and some of the members took little joy rides on large construction machinery. The result of this escapade is that all the sidewalks were destroyed. The college lacks the funds to rebuild a proper sidewalk system. Instead, they are going to build the minimum set of sidewalks to connect all of the buildings. You are supposed to help them figure out what those sidewalks should be. They are giving you the locations of the buildings as x, y coordinates on the campus. You are supposed to return how many unit lengths of sidewalks they have to build along with a list of the buildings that are directly connected to get that.
tuple<double,vector<tuple<int,int> > > sidewalkPlan(const vector<tuple<double, double> > &buildingLocations);
The argument is a vector of tuples with one element for x and the other for y for each of the buildings. You are to assume the buildings have no spatial extent so they are joint points. The return is a tuple with the total length of sidewalk as the first element and a vector of tuples giving the indices of the buildings to make sidewalks between. The input can go up to 20,000 buildings. (No idea how they build that many without proper funding, but somehow they did.) For the tuple<int,int> values that you return, the first value should be less than the second.
No templates so call your .cpp whatever you want.
Teams:
A - Solcher, Zachary J., Kennedy, Rodney M., Schrock, Bryan R.
B - Garrick, Daniel J., Do, NamChi T., Conner, Zachary T.
C - Bierman, Robert F., Fox, Liam M., Lamm, Allison R.
D - Peake, Caulan J., Fan, Irene, Steinbach, Peter A.
E - Von Rosenberg-Miesch, Garrett C., Pauls, Brittney U., Langbert, Zachary H.
F - Compton, Campbell B., Liu, Lu, Wehner, Zacharias K.
G - Ha, Vivian, Miller, J. Hunter, Lavallee, Samantha D.
H - James, Kendrick W., Yin, Oliver
Due 2-26
Results:
Problems:
#1 - Write a Fibonacci heap with min-heap ordering. Your heap should be done in a class with the following definition.
template<typename T>
class FibHeap {
public:
FibHeap();
NodeRef insert(const T &t);
const T &minimum();
const T extractMinimum();
void unionWith(FibHeap &other); // Makes this heap the union of itself and other. Leaves other in empty state.
void decreaseKey(const NodeRef & nr,const T &newValue);
void deleteNode(const NodeRef & nr,const T &negInf);
bool isEmpty();
};
The type T will have comparison operators based on priority. Make it so that your heap can't be copied. You can decide what the type NodeRef is. The exact type will depend on your implementation details. You need to include a typedef or using statement that associates that name with a type. That should go in the public section of your class. That way FibHeap<T>::NodeRef can be used to access that type by outside code. The only requirement is that it must be possible to declare and use a vector<NodeRef>. Put your code in a file called FibHeap.h.
#2 - Write a van Emde Boas Tree.
class VanEmdeBoasTree {
public:
VanEmdeBoasTree(unsigned long universe);
bool search(unsigned long key);
void insert (unsigned long key);
void remove(unsigned long key);
long minimum();
long maximum();
long successor(unsigned long key);
long predecessor(unsigned long key);
};
The value universe is one greater than the maximum key value. Put your code in a file called VanEmdeBoas.h.
#3 - Write a data structure for representing disjoint sets.
template<typename T>
class DisjointSet {
public:
DisjointSet(const T &data);
void unionSets(DisjointSet &ds);
const T &getMarker();
};
Put your code in a file called DisjointSet.h. Note that the way I have these methods set up with "getMarker" you probably want to have the "Find-Set" method from the book in your class as a private method that helps the others.
Teams:
A - Yin, Oliver, Fox, Liam M., James, Kendrick W.
B - Ha, Vivian, Conner, Zachary T., Fan, Irene
C - Bierman, Robert F., Peake, Caulan J., Liu, Lu
D - Von Rosenberg-Miesch, Garrett C., Miller, J. Hunter, Compton, Campbell B.
E - Lamm, Allison R., Lavallee, Samantha D., Pauls, Brittney U.
F - Do, NamChi T., Langbert, Zachary H., Wehner, Zacharias K.
G - Garrick, Daniel J., Solcher, Zachary J., Steinbach, Peter A.
H - Schrock, Bryan R., Kennedy, Rodney M.
Due 2-19
Results:
Problems:
#1 - Write a function that, given a connection matrix, will solve the traveling salesman problem. You should be able to handle up to 23 cities. The function you write should have the following signature.
int shortestCycle(const vector<vector<int>> &connects);
The connects variable is set up so that connects[i][j] gives you the cost of going from i to j. Direction matters, it does not have to be symmetric. All solutions will be less than a billion. The connection values will all be positive except the diagonal, which is zero. Submit a .cpp file with this function in it.
#2 - For this problem you will determine whether a setup for the pegs game can be completed. Write the following function. The board is passed to you as a 2-D vector of bools. A value of true represents a peg. A false represents an empty hole. The board will not have more than 30 holes.
bool canWin(const vector<vector<bool>> &board);
Submit a .cpp file with this function in it.
#3 - Write a function to do Huffman encoding of a string. The message you are to encode will be in the string argument. The encoded version should be in the encoding vector.
void huffman(const string &message, vector<bool> &encoding);
You are allowed to use library calls for your priority queue. Take note of the fact that a string is composed of type char so there are only 256 possible values for each element.
The message can be anything small enough to fit in memory. In other words, it could be billions of characters. Submit a .cpp file with this function in it.
Teams:
A - Wehner, Zacharias K., Liu, Lu, Yin, Oliver
B - Pauls, Brittney U., Ha, Vivian, Schrock, Bryan R.
C - Conner, Zachary T., Peake, Caulan J., James, Kendrick W.
D - Compton, Campbell B., Bierman, Robert F., Solcher, Zachary J.
E - Langbert, Zachary H., Fan, Irene, Do, NamChi T.
F - Steinbach, Peter A., Miller, J. Hunter, Lamm, Allison R.
G - Kennedy, Rodney M., Garrick, Daniel J., Lavallee, Samantha D.
H - Von Rosenberg-Miesch, Garrett C., Fox, Liam M.
Due 2-12
Results:
Problems: (This week is dynamic programming so that is how you are supposed to solve these.)
#1 - You get to solve the integer weight 0/1 knapsack problem and give back both the maximum value and a set of items the reaches that value. The 0/1 knapsack problem works in the following way. You have a knapsack that can hold a specified maximum weight. You can't go over that weight. You have a number of objects to choose from and each one has a weight and a value. You need to find the maximum value of objects you can put in your knapsack. If the weights are allowed to be fractional the only solutions to this problem are exponential. However, if the weights are integers you can construct a solution that is polynomial in time and memory on the number of items and the weight the knapsack can hold. Write a function that has the following signature.
pair<double,vector<int>> knapsack(int weightLimit, const vector<int> &weights, const vector<double> &values);
The first value in the return pair should be the maximum value. The second element is the indices of which items you put in the pack to get that value. Note that the second part isn't unique. This is fine as long as what you return actually gives the proper total value and fits in the pack. My helpful hint is that your recursion would recurse on the item being considered and the weight left in the knapsack. The maximum inputs will have 80,000 items in the knapsack and 5000 weight.
Note that this isn't templated so you will submit a .cpp with a name of your choosing. I will include the function declaration in my test code. The .cpp file should have the function above as well as whatever other functions it needs, but not a main.
#2 - This problem is a relative of the longest common subsequence problem. Unlike DNA, RNA does not automatically include a second strand of bases that are matched up. As a result, RNA strands tend to fold back on themselves so that one piece of the strand will match up with a second piece of the strand in a way so that the base pairs match up. You can see examples of this here and here. As with DNA, there are four bases in RNA. These are typically denoted as C, G, A, and U. The meaning of the letters isn't significant to us. What does matter is that C and G like to match up and A and U like to match up.
To keep things simple, I don't want you to have to worry about a lot of the details of loops or gaps in the chaining. Instead, you are to write a function that takes a string of bases (everything will be 'C', 'G', 'A', or 'U') and returns the maximum number of base pairs that can be matched up. Your matching can have "bubbles" in it or skip arbitrary numbers of bases before it bends back around. So if the string you were given were "CCACUGAACAGUG" your answer would be 5 because the CACUG near the beginning matches up with the reverse of CAGUG at the end. Note that because all I am asking for is the maximum number of matching bases, you can make some of the assumptions that help the LCS algorithm in terms of efficiency.
As a longer example, the first figure I linked to above would correspond to the string "ACGUGCCACGAUUCAACGUGGCACAG". While the picture shows 8 pairs matched up, the method I am asking you to program would return 11 on that string because it would match the two Us in the loop with two of the As the the C with the G in the loose ends. Your function should have the following signature.
int matchingBases(string strand);
You can only have one "loop". This simplification allows you to starting walking from both ends of the string heading toward one another and only skip non-matches. The maximum input is 40,000 characters long.
Note that this isn't templated so you will submit a .cpp with a name of your choosing. I will include the function declaration in my test code. The .cpp file should have the function above as well as whatever other functions it needs, but not a main.
Teams:
A - Fox, Liam M., Schrock, Bryan R., Steinbach, Peter A.
B - Ha, Vivian, Solcher, Zachary J., Miller, J. Hunter
C - Von Rosenberg-Miesch, Garrett C., Peake, Caulan J., Kennedy, Rodney M.
D - Do, NamChi T., James, Kendrick W., Yin, Oliver
E - Lamm, Allison R., Lavallee, Samantha D., Liu, Lu
F - Wehner, Zacharias K., Fan, Irene, Pauls, Brittney U.
G - Compton, Campbell B., Bierman, Robert F., Langbert, Zachary H.
H - Conner, Zachary T., Garrick, Daniel J.
Due 2-5
Results:
Problems:
#1 - For this problem you should write a radix sort with the signature shown below. The arguments begin and end will be random access iterators. The value keyFunc is a callable such that keyFunc(*begin) gives you an int.
template<typename T,typename K>
void radixSort(T begin,T end,K keyFunc);
Because this function is templated, it needs to go into a header file. Call it "radix.h".
#2 - Implement a bucket sort with the signature shown below. The arguments begin and end will be random access iterators. The value keyFunc is a callable such that keyFunc(*begin) gives you a double.
template<typename T,typename K>
void bucketSort(T begin,T end,K keyFunc);
Because this function is templated, it needs to go into a header file. Call it "bucket.h". Note that I am checking your results against a stable sort. So you need to make sure the way you sort your buckets is stable.
#3 - Write both of the order stats functions from the book. The first uses a random partitioning. This is average case O(n), but it has a worst case of O(n^2). The second uses the method they describe to make sure that the worst case is still O(n).
template<typename T,typename C,typename S>
T randomOrderStat(T begin, T end,C lt,S index);
template<typename T,typename C,typename S>
T linearOrderStat(T begin, T end,C lt,S index);
The begin and end are random access iterators. The lt value is a callable that gives a less-than like that for the quicksort. The type S is the size type for this collection and index is the index of the iterator to the value you should return.
Because this function is templated, it needs to go into a header file. Call it "order.h".
Teams:
A - Kennedy, Rodney M., Ha, Vivian, Von Rosenberg-Miesch, Garrett C.
B - Pauls, Brittney U., Fox, Liam M., Lamm, Allison R.
C - Fan, Irene, Wehner, Zacharias K., Lavallee, Samantha D.
D - Bierman, Robert F., Schrock, Bryan R., James, Kendrick W.
E - Yin, Oliver, Do, NamChi T., Conner, Zachary T.
F - Liu, Lu, Garrick, Daniel J., Miller, J. Hunter
G - Peake, Caulan J., Steinbach, Peter A., Compton, Campbell B.
H - Solcher, Zachary J., Langbert, Zachary H.
Due 1-29
Results:
Problems:
#1 - For this problem you will write a cell division discrete event simulation that is based on a research project done in the math department a number of years ago looking at population growth in cell cultures. The code you submit needs to have a function with the following signature.
int numCells(double endTime, double minSplit, double maxSplit);
At time 0 you start with one cell and it splits immediately. Each time a cell splits, both halves will split again at some random time in the future. That time between splits is uniformly distributed between minSplit and maxSplit. Each cell from a split will use a different random value for its next split time. I want you to generate the random value using the following expression. maxSplit > minSplit > 0
minSplit + rand()*(maxSplit-minSplit)/RAND_MAX;
Both rand and RAND_MAX are defined in cstdlib. Do NOT call srand in the code you submit. I will be setting the seed myself for testing purposes. Your function should return the number of cells you have when the next split time is greater than endTime.
Note that for your function to return the same answer as mine, you have to pull random numbers for splits in the order that the cells split.
#2 - Write a heapsort that uses the normal ordering of the type T. Your function should have the following signature.
template<typename T> void heapsort(T begin, T end);
The begin and end variables are random access iterators. For this problem you need to submit your function in a file named heapsort.h for the autotester to work.
#3 - Write a quicksort that takes an argument for the sort order. Your function should have the following signature.
template<typename T,typename C> void (quicksortT begin, T end,const C <);
The begin and end variables are random access iterators. The object lt should be callable with two arguments and return a bool. So in your code, you can write things like the following.
if(lt(v1,v2)) ...
For this problem you need to submit your function in a file named quicksort.h for the autotester to work.
Teams:
Team A - Lamm, Allison R., Solcher, Zachary J., Schrock, Bryan R.
Team B - Wehner, Zacharias K., James, Kendrick W., Pauls, Brittney U.
Team C - Miller, J. Hunter, Conner, Zachary T., Von Rosenberg-Miesch, Garrett C.
Team D - Do, NamChi T., Garrick, Daniel J., Lavallee, Samantha D.
Team E - Fan, Yiran, Liu, Lu, Ha, Vivian
Team F - Kennedy, Rodney M., Fox, Liam M., Yin, Oliver
Team G - Bierman, Robert F., Peake, Caulan J., Langbert, Zachary H.
Team H - Steinbach, Peter A., Compton, Campbell B.
Due 1-22
Results:
Problems:
#1 - Write an efficient Strassen's method of matrix multiplication using a nice class for a matrix. Note that your class needs to be able to represent submatrices efficiently. The test code will use matrices that are always a square that is a power of two in size so you don't have to worry about what to do when that isn't the case. The matrices will not be larger than 2^13 on each side.
Make your class called Matrix. In needs to have the following elements. Note that you will probably need to add more things that I haven't included. Use the file names matrix.h and matrix.cpp for the header and source files respectively.
// This class only exists so that you can do things like m[r][c].
class Row {
public:
int operator[](int c) const;
int &operator[](int c);
class const_iterator {
public:
bool operator==(const const_iterator& that);
bool operator!=(const const_iterator& that);
const_iterator &operator++(); // prefix
const_iterator operator++(int); // postfix
int operator*();
};
const_iterator begin() const;
const_iterator end() const;
};
class Matrix {
public:
Matrix(int n);
Matrix(const std::vector<std::vector<int>> &m);
Matrix operator*(const Matrix &m2) const;
const Row operator[](int r) const;
Row operator[](int r);
class const_iterator {
public:
bool operator==(const const_iterator& that);
bool operator!=(const const_iterator& that);
const_iterator &operator++(); // prefix
const_iterator operator++(int); // postfix
Row operator*();
};
const_iterator begin() const;
const_iterator end() const;
};
#2 - One of my favorite divide and conquer problems, as many of you know, is expression parsing. This doesn't have to be done in a divide and conquer way, but there can be benefits to doing so. For this problem you will write such a parser in C++. Your parser needs to be able to handle +, -, *, and / as well as sqrt, sin, cos, and tan. Lastly, it needs to be able to include variables. The expressions will always be properly formatted using the standards you are used to in programming languages. So it will be 3*x, not 3x. Handle parentheses properly.
You need to write a function like the following and put it in a .cpp file.
double eval(const std::string &expr,const std::map<std::string,double> &vars);
Note that the test code is going to call this function multiple consecutive times using the same expression. You can use that information to optimize if you want.
#3 - For this problem you are to write a function that can find the ith, jth, kth, etc. element of a sequence of unordered values based upon a user specified ordering. So if you had N numbers (say doubles) and you wanted to find the quartiles you could call your function passing it the values N/4, N/2, and 3*N/4 as the indices, as well as information on how to compare the doubles.
You need to make a file called order.h and put your implementation to the following function inside of it.
template<typename T,typename C>
T &findNth(std::vector<T> &data,int index,const C &comp);
The type T is the data you are storing. You are allowed to alter the vector that is passed in, moving things around. The type C is a callable object that takes two arguments of type T. It should return a negative value if the first argument comes before the second, a positive value if the first argument comes after the second, or zero if the order of those two doesn't matter.
You are allowed to use library sorts, but you can't use a library method that does exactly what you are supposed to be writing.
Teams: None. Individual work.