Saving the Earth from aliensIn 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 taskedwith writing a set of utility methods to determine the global minimum cut of the network usinga randomized algorithm (contraction algorithm).Here are the technical details about the network: the network is an instance of the classGraph.java. Some examples of what the network could look like are described in the filesnetwork_1.txt, network_2.txt, where the first line is the expected size of the mincut and the following lines describe the edges, i.e. the line a b means that there is anedge between node a and node b. To test your code, run: java GlobalMinCutTesternetwork_1.txt and java GlobalMinCutTester network_2.txt.
Your tasks: Implement Graph.contractEdge(). When contracting an edge e = (u, v), insteadof replacing u and v by single new supernode w as in the course slides, you will mergethe 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: whilelooping through edges and removing them, you may run intoConcurrentModificationException depending on how you try doing it.Thankfully Google and Stack Overflow still exist in 2246 and you can find multipleways to fix it. For all remaining edges, replace all occurrences of u with v Implement GlobalMinCut.global_min_cut(), which must return two lists ofnodes (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 mustupdate S(v), i.e. all the nodes that were in the supernode u must now be added to thesupernode 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() untilit either obtains the minimum cut or exceeds a large number of iterations, in which case youll 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, donttouch it and dont 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 theoriginal graph at each iteration and pass the copy. Use the copy constructorGraph(graph) provided.
2. (30 points) Rescuing AnatolyThe 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 backin time to kidnap Anatoly Alexeyevich Karatsuba to force him to reveal his secrets. Your taskis to implement his algorithm to show aliens any human can be replaced with a small piece ofcode 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 ofboth algorithms in Multiply.java.Your tasks: Implement the naive multiplication algorithm in naive(int size, int x, inty) 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 theirefficiency (or cost). The variable size is the size of the integers x and y, and is defined as the numberof bits used to encode them (Note: we assume that x and y have the same size). Wedefine the size as the number of bits starting from the right that are used in theproduct. 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 crudeapproximation). In particular, for the base case (i.e. when the size of the integers is 1 bit), this costwill 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 is3 m), in addition of the number of operations executed by each recursive call to thefunction. By contrast, the Karatsuba algorithm requires 6 arithmetic operations ofsize m on the top of the cost of the recursion. Each method (i.e. naive and karatsuba) will return an integer array resultthat 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 eachrow is the size of the integers that have been multiplied, the second number is the cost ofthe 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 willtake over the world (as well as university administration), and your assignment will have to besent to Mars for evaluation, causing a delay of several years in the grading process.
Reviews
There are no reviews yet.