data structures (java)

This is a Homework project for a Data Structures class that involves 4 parts. 1) Write the 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. Test the code and determine the time and space complexities of your code. Explain. (link to the class [login to view URL] included below) 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). [4 pts] Provide a high-level statement of a possible greedy heuristic for the minimum dominating set problem. (b) [3 pts] 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) [8 pts] 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 merge 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. (link to the class [login to view URL] included below) 4)Rewrite this program using a stack to simulate the recursion. The new code should stack the boundaries of only the larger of the segments 'left' and 'right'. Show that the stack space needed is O(log(n)). /** 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, [login to view URL](a, [login to view URL] -1); quickSort(0, [login to view URL] - 2); } ***Please download [login to view URL] and [login to view URL] FROM WEBSITE MENTIONEDIN DELIVERABLES ## Deliverables **Complete and fully-functional working program(s)in java in executable form as well as complete source code of all work done. **Complete ownership and distribution copyrights to all work purchased. *****Download the code for [login to view URL] and [login to view URL] from this website: Go here [login to view URL]~sahni/dsaaj/ and click on 'Programs' in the top left scroll down menu. Click on 'java codes for programs in text only' and follow directions. They are the java codes from the text. The codes are in a zip file. 1) Write the code for the public method [login to view URL](), which determines whether an undirected graph has a cycle. Base your code on either a Depth-First Search or a Breadth-First Search. Look at the methods dfs and bfs in Graph.java. Test the code and determine the time and space complexities of your code. Explain. 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). [4 pts] Provide a high-level statement of a possible greedy heuristic for the minimum dominating set problem. (b) [3 pts] 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) [8 pts] 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. (refer to [login to view URL] for this one also) 3)Write a merge 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. (Look at link at top of page for [login to view URL] class) 4)Rewrite this program using a stack to simulate the recursion. The new code should stack the boundaries of only the larger of the segments 'left' and 'right'. Show that the stack space needed is O(log(n)). /** 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, [login to view URL](a, [login to view URL] -1); quickSort(0, [login to view URL] - 2); } ## Platform Windows 98 Java platform