Problems and Teams

#1 - Shortest path using LP.

double shortestPathLP(int start,int end,const vector<vector<tuple<int,double>>> &graph);

The graph is an adjaceny 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 start,int end,double totFlow,const vector<vector<tuple<int,double,double>>> &graph);

The tuple contains vertex number, capacity, and cost per flow respectively. return the total cost of your solution.

#3 - Multicommodity flow using LP.

double multicommodityFlowLP(const vector<tuple<int,int,double>> &commodities,const vector<vector<tuple<int,double>>> &graph);

Teams:

#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 and 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:

#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. 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:

#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:

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. (Dione's memory can handle 26, but you don't want to wait that long.) 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 empy 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:

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. 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:

Problems:

#1 - Order Statistics Tree: Write an augmented BST that includes at least the following. Note that you can add more, but I will be calling these methods so if you don't implement them your code won't compile with my tests.

template<class K,class T>

class OrderStatTree {

public:

OrderStatTree();

// Adds data under the given key. Returns whether this is a replace (no duplicate keys).

// If true, the variable replaced has the value that was there before.

bool add(const K &key, const T &data, T &replaced);

// Removed the entry for the given key. Returns where it was found.

// If it was found, that data for that key will be in data.

bool remove(const K &key, T &data);

// Return the number of elements in the tree.

int size() const;

// Return a const reference to the data associated with the given key.

const T &get(const K &key) const;

// Return a non-const reference to the data associated with the given key.

T &get(const K &key);

// Returns a const reference to the data at the specified index in the tree.

const T &operator[](int index) const;

// Returns a non-const reference to the data at the specified index.

T &operator[](int index);

// Returns the index of a particular key.

int indexOf(const K &key) const;

};

The type K is the key type that you will sort on. It will have comparison operators. The type T is the data associated with the keys. Put this is a file called "StatTree.h".

All of my big tests will use random key values.

#2 - Interval tree

template<class T>

class IntervalTree {

public:

IntervalTree();

// Adds the given interval to the tree.

void add(const std::pair<T,T> &interval);

// Removes the specified interval. Returns whether such an interval was found. Use == for interval equality.

bool remove(const std::pair<T,T> &interval);

// Returns whether there is a conflicting interval for the one passed in. If there is, the value will be in conflict.

bool conflictingInterval(const std::pair<T,T> &interval,std::pair<T,T> &conflict) const;

// Finds all intervals in the tree that conflict with the one passed in. The conflicting intervals are pushed back on conflicts.

// They should appear in order first by start time, then by end time.

void allConflictingIntervals(const std::pair<T,T> &interval,vector<std::pair<T,T>> &conflicts) const;

};

The std::pair<T,T> is an interval. The type T wll have comparison operators on it. Other than that you don't know what it is. Also, all intervals you are given will have the first element of the pair smaller than the second element. Put this in a file called "IntervalTree.h".

All of my big tests will use random intervals. Note that unlike for #1, you can have duplicate intervals or multiple intervals that use the same start value. Note that intervals that "touch" are not considered to conflict. So pair<int,int>(3,5) and pair<int,int>(5,7) do not conflict. This implies these are open intervals. This is different from the book which considers closed intervals.

#3 - Write a data structure to do the following operations.

template<class T>

class ElementPQ {

public:

ElementPQ();

// This method will be called to tell you how many events to expect in the next round of using the PQ.

// This will always be called at the beginning when the queue is empty.

void setEstimatedEventCount(int n);

// Adds the specified event to the queue.

void add(const T &pc);

// Tells if the queue is empty.

bool isEmpty() const;

// Tells the next event on the queue. Can fail miserably is calle don empty queue.

T peek() const;

// Removes and returns the next event from the queue. Can fail miserably if calle don empty queue.

T removeNext();

// Removes all events involves the specified element.

void removeAllInvolving(unsigned int elem);

};

The type T will have at least the following a double called time, which is what you use for your priority, elem1 and elem2, which are unsigned ints. The values of elem1 and elem2 will always be different. The peek and removeNext methods take off the thing with the smallest value of time. Your inputs will have uniformly distributed times between [0.0,1.0). When a removeAllInvolving call is made, you remove all events involving that numbered element whether it is elem1 or elem2. Put this in a file called "ElementPQ.h".

All of my big tests will use random times and element numbers.

Teams:

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. The last argument, digits, is the number of decimal digits you have to include in the sort. So if the keys range from 0-999 then digits will be 3.

template<class T,class K> void radixSort(T begin,T end,K keyFunc,int digits);

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. That double will always be between min and max, inclusive.

template<class T,class K> void bucketSort(T begin,T end,K keyFunc,double min,double max);

Because this function is templated, it needs to go into a header file. Call it "bucket.h".

#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<class T,class C,class S> T randomOrderStat(T begin, T end,C lt,S index);

template<class T,class C,class 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:

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<class T> void heapsort(T begin, T end);

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<class T,class C> void quicksort(T begin, T end,C lt);

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: