Show Bid Request
Minimal Spahing Tree
Bid Request Id: 36929
|
|
|
|
Posted by: |
seatiger74 (25 ratings)
(Software buyer rating 10 )
|
|
Non-action Ratio: |
Very Good - 3.23%
|
Buyer Security Verifications: |
Good
|
|
Approved on: |
Nov 24, 2002
10:18:51 PM EDT
|
|
Bidding Closes: |
Dec 3, 2002
10:23:45 PM EDT
|
|
Viewed (by coders): |
145 times
|
|
Deadline: |
12/5/2002
TIME EXPIRED
|
|
|
|
|
Description:
Write this program in C++
A company, Silver Products, Inc., wants to minimize shipping costs. It
ships to 5,000 points across the country. They have made available a data
file, silver.dat which you will take your
input from. The first line is the total number of vertices (5000) and
each line after that is an edge, of the form v1 v2 wt (3 integer values).
Setup a graphing arrangement where you can have a LARGE number of vertices
and edges (with vertices simply being numbers 1 to V, V= total number).
Implement Kruskal's algorithm in this environment so that you can compute the
minimal spanning tree of a connected graph. Kruskal generates a sequence of
edges as its output. To understand and use Kruskal, you will need code from
Chapter 6 on priority queues as well as some of the code from Chapter 8 on
disjoint sets.
Then invoke Kruskal and compute your minimal spanning tree. On the
result, show that the MST does span the graph by checking whether each and
every node is on at least one edge in the MST; thus print a list of those
that are not, or else output the message "MST does span the graph". (But
your code has to perform the check!).
As a final check, compute the average weight of the edges in the whole
graph and also the average weight of the edges in the minimal spanning
tree (the latter should be quite a bit less).
Finally print the MST; try to format it in 6 columns across the page
(print each edge as (nnnn nnnn); you do not have to print the weight of
each edge) so as not to use up too much paper.
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.
Platform:
I use Visual C++ 6.0 to run this program
Must be 100% finished and received by buyer on:
Dec 5, 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:
Please send the codes ontime
Additional Files:
This bid request includes IMPORTANT additional attached files. Please download and read fully before bidding.
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!
|
$20 (USD)
|
Nov 25, 2002
7:40:54 PM EDT
|
10
(Excellent)
|
|
|
Hi,
The program which I give you will be properly indented and well-commented.
Let me know if you are interested. I'll give you the program as soon as possible. Thanks.
|
|
|
|
|
|
|