Extra Credit Assignment 3
This extra credit assignment is worth 10 points (two homework assignments). You wont get any credit until you get the full credit (i.e., if you turn in a half completed project, you wont get any credit). You may submit it as many times as possible. This assignment must be completed by November 31st.
Your task is to find good solutions to the
weighted mincut problem using any of the two algorithms below:
Weighted mincut: You have a graph with weighted edges. You divide the
graph into two parts. Each part has
half the vertices. Now total the weights of edges that go from one part
to another and try to minimize that.
This cut has a weight of 2. There are 4 nodes on each side.
Make sure to test graphs of different densities, varying edge weights, different sizes, etc. Don't just work
with one type of graph!
Your job is to conduct scientific experiments (i.e., use the scientific method) comparing and contrasting the two methods you chose. Make sure to test each algorithm with different parameters several times.
Be very careful in making the tests fair. That is,
implement them in the same language, make them both as efficient as possible, and implement them in how they are intended to be implemented. Your assignment will be looked at very closely to make sure these conditions are met.
Does one method work better in some situations and why? Is one faster in general? Does one take up more memory than the other? Answer these questions and other important questions with empirical data backing your statements.
You are encouraged to find implementations online (as long as you understand them; the implementation may be slow!) and in published papers. Just be sure to cite your sources!
What to turn in:
- Your source code
- A writeup discussing your findings