Show Bid Request
data structures (java)
Bid Request Id: 38048
|
|
|
|
Posted by: |
LaurenWalters (1 ratings)
(Software buyer rating 10 )
|
|
Non-action Ratio: |
Very Good - 0.00%
|
|
Posted: |
Dec 2, 2002
10:02:32 PM EDT
|
|
Bidding Closes: |
Dec 5, 2002
10:00:00 AM EDT
|
|
Viewed (by coders): |
221 times
|
|
Deadline: |
12/5/2002 5:00:00 PM
TIME EXPIRED
|
|
|
|
|
Description:
This is a Homework project for a Data Structures class that involves 4 parts.
1) Write the code for the public method Graph.cycle(), 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 Graph.java 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 Graph.minDominatingSet(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 Chain.java 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 : a.length - 1] using the quick sort method */
public static void quickSort(Comparable [] a)
{
QuickSort.a = a;
if (a.length <= 1) return;
//move largest element to right end
MyMath.swap(a, a.length - 1, MyMath.max(a, a.length -1);
quickSort(0, a.length - 2);
}
***Please download Graph.java and Chain.java 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 Graph.java and Chain.java from this website: Go here http://www.cise.ufl.edu/~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 Graph.cycle(), 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 Graph.minDominatingSet(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 Graph.java 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 Chain.java 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 : a.length - 1] using the quick sort method */
public static void quickSort(Comparable [] a)
{
QuickSort.a = a;
if (a.length <= 1) return;
//move largest element to right end
MyMath.swap(a, a.length - 1, MyMath.max(a, a.length -1);
quickSort(0, a.length - 2);
}
Platform:
Windows 98
Java platform
Must be 100% finished and received by buyer on:
Dec 5, 2002 5:00:00 PM EDT
Deadline legal notes: All times are expressed in the time zone of the site EDT (UT - 5). If the buyer omitted a time, then the deadline is 11:59:59 PM EDT on the indicated date.
Remember that contacting the other party outside of the site (by email, phone, etc.) on all business projects < $500 (before the buyer's money is escrowed) is a violation of both the software buyer and seller agreements.
We monitor all site activity for such violations and can instantly expel transgressers on the spot, so we thank you in advance for your cooperation.
If you notice a violation please help out the site and report it. Thanks for your help.
|
|
|
Bidding/Comments:
|
All monetary amounts on the site are in United States dollars.
Rent a Coder is a closed auction, so coders can only see their own bids and comments. Buyers can view every posting made on their bid requests. |
See all rejected bids (and all comments)
| Name |
Bid Amount
|
Date |
Coder Rating |
|
|
This bid was accepted by the buyer!
|
$40 (USD)
|
Dec 3, 2002
10:08:02 AM EDT
|
9.3
(Superb)
|
|
|
I can do your job.
I have strong point at alogorithm and data structure.
will be finished with in your deadline
|
|
|
|
|
|
|
