Structures

1) Write code for the public method [login to view URL](), which determines whether an undirected graph has a cycle. Base your code on either a DFS or a BFS. 2) Let G=(V, E) be an undirected graph. A subset S of vertices of G is a dominating set iff for every vertex u in V-S, there is an edge between u and some vertex in S. A minimum dominating set is a dominating set of minimum size. The problem of finding a minimum dominating set in a graph is NP-hard. (a). Provide a high-level statement of a possible greedy heuristic for the minimum dominating set problem. (b) Give an example of a graph on which your heuristic actually produces a minimum dominating set and also one example on which it does not. (c) Redefine the heuristic of (a) into the public method [login to view URL](int [] dominatingSet) that returns the size of the smallest set found and put the vertices of this set into the array dominatingSet. Test your code. 3)Write a merger sort code that works on chains of elements . The output should be a sorted chain. Make your sort method a member of the class Chain or of a class that extends Chain. 4) Rewrite the code under Deliverables using a stack to simulate the recursion. The new code should stack the boudaries of only the larger of the segments left and right. ## Deliverables 1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done. 2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request. 3) Complete ownership and distribution copyrights to all work purchased. Each programs should include a main method which tests the program. Code for problem 4: /** sort a[0: [login to view URL] - 1] using the quick sort method public static void quickSort(Comparable[] a) { QuickSort.a = a; if([login to view URL] <= 1) return; // move largest element to right end [login to view URL](a, [login to view URL] - 1, MyMath,max(a, [login to view URL] - 1)); quickSort(0, [login to view URL] - 2); } If one decides to take on this project I will provide more information and code that can be extended. ## Platform Windows XP ## Deadline information More time can be provided if needed.