Assignment 04 Solution

Exercise 1. (30 points) Saving the Earth from aliens

In 2246 aliens declared war on humans. To save humanity, we need to disrupt the alien communication network while breaking the minimum possible number of links. You are tasked

with writing a set of utility methods to determine the global minimum cut of the network using

a randomized algorithm (contraction algorithm).

Here are the technical details about the network: the network is an instance of the class

Graph.java. Some examples of what the network could look like are described in the files

network_1.txt, network_2.txt, where the first line is the expected size of the min

cut and the following lines describe the edges, i.e. the line "a b" means that there is an

edge between node a and node b. To test your code, run: java GlobalMinCutTester

network_1.txt and java GlobalMinCutTester network_2.txt.




Your tasks:

• Implement Graph.contractEdge(). When contracting an edge e = (u, v), instead

of replacing u and v by single new supernode w as in the course slides, you will merge

the node u into v. More specifically, you will:

– Remove the edge e = (u, v), and remove the node u (use the removeNode()

method for that)

– Remove edges that had one end equal to u and other equal to v. Heads up: while

looping through edges and removing them, you may run into

ConcurrentModificationException depending on how you try doing it.

Thankfully Google and Stack Overflow still exist in 2246 and you can find multiple

ways to fix it.

– For all remaining edges, replace all occurrences of u with v

• Implement GlobalMinCut.global_min_cut(), which must return two lists of

nodes (characters) corresponding to the two partitions of the cut.

– For each node v, you will record the list S(v) of nodes that have been contracted into v

– Initially S(v) = v for each v

– Run the contraction algorithm. After each contraction of an edge e = (u, v) you must

update S(v), i.e. all the nodes that were in the supernode u must now be added to the

supernode v, because we just merged u into v

– Once you have only two nodes u and v left, return S(u) and S(v)

– For your convenience, the Graph class has several utility methods: getNbEdges(),

getNodes(), getEdge(), getExpectedMinCutSize() and others.

• Implement GlobalMinCut.global_min_cut_repeated(). This method is already almost done. Given a graph, this method should call global_min_cut() until

it either obtains the minimum cut or exceeds a large number of iterations, in which case you’ll know you did something wrong. More specifically, it has an int parameter maxIterations, we expect the algorithm to have found the min cut before then with high probability, it is used as a sanity check and to avoid infinite loops.

global_min_cut_repeated() also takes a Random object as a parameter, don’t

touch it and don’t worry about it, we only use it for grading so we can use seeds.

– You need to add a call to global_min_cut()

– Since global_min_cut() modifies the graph, you need to create copies of the

original graph at each iteration and pass the copy. Use the copy constructor

Graph(graph) provided.




2. (30 points) Rescuing Anatoly

The aliens are also interested in multiplication methods, especially the Karatsuba algorithm,

which is so fast they fear it could thwart the success of their invasion. They have gone back

in time to kidnap Anatoly Alexeyevich Karatsuba to force him to reveal his secrets. Your task

is to implement his algorithm to show aliens any human can be replaced with a small piece of

code and convince them to return him to his family.

To make a convincing point, you will need to compare the naive and Karatsuba divide-andconquer methods to multiply two integers x and y. You will implement a recursive version of

both algorithms in Multiply.java.

Your tasks:

• Implement the naive multiplication algorithm in naive(int size, int x, int

y)

• Implement the Karatsuba algorithm in karatsuba(int size, int x, int y)

• Evaluate the number of arithmetic operation of each method by keeping track of their

efficiency (or cost).

– The variable size is the size of the integers x and y, and is defined as the number

of bits used to encode them (Note: we assume that x and y have the same size). We

define the size as the number of bits starting from the right that are used in the

product.

– We define the cost as the number of brute force arithmetic operations of the (addition, subtraction, or multiplication) executed by the algorithm multiplied by the size

(in bits) of the integers involved in this operation (Note: We ignore the multiplication by powers of 2 which can be executed using a bit shift. Of course, this is a crude

approximation).

– In particular, for the base case (i.e. when the size of the integers is 1 bit), this cost

will be 1 (brute force multiplication of two integers of size 1). In the induction case,

the naive method executes 3 arithmetic operations of integer of size m (i.e. cost is

3 · m), in addition of the number of operations executed by each recursive call to the

function. By contrast, the Karatsuba algorithm requires 6 arithmetic operations of

size m on the top of the cost of the recursion.– Each method (i.e. naive and karatsuba) will return an integer array result

that stores the value of the multiplication in the first entry of the array (i.e. result[0]),

and the cost of this computation in the second entry (i.e. result[1])

• The output of your program will print a list of numbers such that the first number of each

row is the size of the integers that have been multiplied, the second number is the cost of

the naive method, and the third number the cost of the Karatsuba method.

If you do not submit your two java programs in a single zip file on MyCourses, the aliens will

take over the world (as well as university administration), and your assignment will have to be

sent to Mars for evaluation, causing a delay of several years in the grading process.