Problems and Teams

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 - Witecki, Thomas, Castro, Diego, Fisher, Kat

B - Mangalji, Ali, Ward, Josh, Kurima-Blough, Zack

C - Zimdars, Zach, Darrah, Jeffrey, Wolf, Dillon

D - Thacker, Isaac, Kennedy, Julia, Luber, Jacob

E - McCutchen, Sean, Moden, Kylie, Leeds, Andy

F - Kinahan, Sean, Sims, Woody, Zhang, Tim

G - Foster, Zane, Bird, Alexa, Cruz, Matt

Due 2-25

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 - Kurima-Blough, Zack, Thacker, Isaac, Ward, Josh

B - Moden, Kylie, Leeds, Andy, Witecki, Thomas

C - Mangalji, Ali, Bird, Alexa, Luber, Jacob

D - Wolf, Dillon, Sims, Woody, Darrah, Jeffrey

E - Kennedy, Julia, Kinahan, Sean, Castro, Diego

F - Zimdars, Zach, Fisher, Kat, Foster, Zane

G - McCutchen, Sean, Cruz, Matt, Zhang, Tim

Due 2-18

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 - Bird, Alexa, Fisher, Kat, Cruz, Matt

B - Castro, Diego, Wolf, Dillon, Moden, Kylie

C - Sims, Woody, Kurima-Blough, Zack, Foster, Zane

D - Kinahan, Sean, Mangalji, Ali, Zhang, Tim

E - McCutchen, Sean, Kennedy, Julia, Luber, Jacob

F - Witecki, Thomas, Leeds, Andy, Thacker, Isaac

G - Zimdars, Zach, Ward, Josh, Darrah, Jeffrey

Due 2-11

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 - Darrah, Jeffrey, Foster, Zane, Kurima-Blough, Zack

B - Fisher, Kat, Sims, Woody, Thacker, Isaac

C - Ward, Josh, Castro, Diego, Witecki, Thomas

D - Kennedy, Julia, Moden, Kylie, Luber, Jacob

E - Wolf, Dillon, Cruz, Matt, Zhang, Tim

F - Mangalji, Ali, McCutchen, Sean, Leeds, Andy

G - Zimdars, Zach, Kinahan, Sean, Bird, Alexa

Due 2-4

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 - Foster, Zane M., Thacker, Isaac M., Leeds, Andrew S.

B - Kennedy, Julia Y., Zhang, Timothy Y., Darrah, Jeffrey W.

C - Witecki, Thomas A., Fisher, Kathleen M., Luber, Jacob M.

D - Mangalji, Ali, Wolf, Timothy D., Bird, Alexa D.

E - Moden, Kylie J., Ward, Joshua R., Zimdars, Zachrey W.

F - Sims, Woodrow B., McCutchen, Sean E., Cruz, Matthew G.

G - Kinahan, Sean P., Castro, Diego J., Kurima-Blough, Zackery K.

Due 1-28

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

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:

A - Witecki, Thomas A., Sims, Woodrow B., Castro, Diego J.

B - Kinahan, Sean P., Mangalji, Ali, Thacker, Isaac M.

C - Zhang, Timothy Y., Cruz, Matthew G., Bird, Alexa D.

D - Zimdars, Zachrey W., Luber, Jacob M., McCutchen, Sean E.

E - Leeds, Andrew S., Fisher, Kathleen M., Kennedy, Julia Y.

F - Foster, Zane M., Moden, Kylie J., Wolf, Timothy D.

G - Kurima-Blough, Zackery K., Ward, Joshua R., Darrah, Jeffrey W.

Due 1-21

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);

So an example call might look like eval("3*(x+2)",vars);, where vars is declared as map<string,double> vars; and you say vars["x"] = 5.0;.

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