Problems and Teams 2
Due 4-29:
Results:
Yes
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 - Mangalji, Ali, Kinahan, Sean, Leeds, Andy
B - Darrah, Jeffrey, Sims, Woody, Cruz, Matt
C - Zhang, Tim, Foster, Zane, McCutchen, Sean
D - Luber, Jacob, Wolf, Dillon, Fisher, Kat
E - Castro, Diego, Moden, Kylie, Kurima-Blough, Zack
F - Thacker, Isaac, Zimdars, Zach, Witecki, Thomas
G - Kennedy, Julia, Ward, Josh, Bird, Alexa
Due 4-22:
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 - Foster, Zane, Luber, Jacob, Moden, Kylie
B - Bird, Alexa, Kurima-Blough, Zack, Sims, Woody
C - Thacker, Isaac, Ward, Josh, Fisher, Kat
D - Leeds, Andy, Zimdars, Zach, Mangalji, Ali
E - Zhang, Tim, Kinahan, Sean, Cruz, Matt
F - Wolf, Dillon, Kennedy, Julia, Witecki, Thomas
G - McCutchen, Sean, Castro, Diego, Darrah, Jeffrey
Due 4-15:
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 - Zimdars, Zach, Ward, Josh, Thacker, Isaac
B - Kennedy, Julia, Kurima-Blough, Zack, Bird, Alexa
C - Sims, Woody, Wolf, Dillon, Witecki, Thomas
D - Fisher, Kat, Kinahan, Sean, Darrah, Jeffrey
E - Foster, Zane, Cruz, Matt, Zhang, Tim
F - Luber, Jacob, Leeds, Andy, McCutchen, Sean
G - Moden, Kylie, Mangalji, Ali, Castro, Diego
Due 4-8:
Results:
Yes
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 - Thacker, Isaac, Kurima-Blough, Zack, Ward, Josh
B - Castro, Diego, Fisher, Kat, Mangalji, Ali
C - Cruz, Matt, Wolf, Dillon, Zhang, Tim
D - Kennedy, Julia, Bird, Alexa, McCutchen, Sean
E - Darrah, Jeffrey, Zimdars, Zach, Foster, Zane
F - Sims, Woody, Witecki, Thomas, Leeds, Andy
G - Moden, Kylie, Kinahan, Sean, Luber, Jacob
Due 4-1:
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-25
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 parameter, nearbyDistances, is an adjacency list representation of the graph. 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 - Leeds, Andy, Kennedy, Julia, Mangalji, Ali
B - Wolf, Dillon, Sims, Woody, Cruz, Matt
C - Kinahan, Sean, Castro, Diego, Zimdars, Zach
D - Luber, Jacob, Moden, Kylie, Darrah, Jeffrey
E - Ward, Josh, Zhang, Tim, Thacker, Isaac
F - Fisher, Kat, Witecki, Thomas, Kurima-Blough, Zack
G - Foster, Zane, McCutchen, Sean, Bird, Alexa