Show Bid Request
Structures
Bid Request Id: 36043
|
|
|
|
Posted by: |
SimuGD (14 ratings)
(Software buyer rating 10 )
|
|
Non-action Ratio: |
Very Good - 0.00%
|
Buyer Security Verifications: |
Good
|
|
Approved on: |
Nov 18, 2002
8:25:33 PM EDT
|
|
Bidding Closes: |
Nov 22, 2002
8:44:45 PM EDT
|
|
Viewed (by coders): |
175 times
|
|
Deadline: |
11/27/2002
TIME EXPIRED
|
|
|
|
|
Description:
1) Write 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.
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 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 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: 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);
}
If one decides to take on this project I will provide more information and code that can be extended.
Platform:
Windows XP
Must be 100% finished and received by buyer on:
Nov 27, 2002 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.
Special Conditions / Other:
More time can be provided if needed.
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!
|
$99 (USD)
|
Nov 19, 2002
2:17:23 AM EDT
|
9.82
(Excellent)
|
|
|
| Hello,
I can do this problems for you.
I have stong experince with Java ans Algorithms.
Regards,
Marius.
|
|
|
|
|
|
|