Show Bid Request
Simple hashing
Bid Request Id: 66006
|
|
|
|
Posted by: |
Cougar (23 ratings)
(Software buyer rating 10 )
|
|
Non-action Ratio: |
Very Good - 18.64%
|
Buyer Security Verifications: |
Excellent
|
|
Approved on: |
May 31, 2003
10:16:58 AM EDT
|
|
Bidding Closes: |
Jun 1, 2003
12:15:36 PM EDT
|
|
Viewed (by coders): |
147 times
|
|
Deadline: |
6/2/2003
TIME EXPIRED
|
|
|
|
|
Description:
Every compiler sets up symbol tables. Write 3 c++ procedures to implement symbol tables in 3 different ways.
Using double hashing (meth1)
Using direct chaining hashing (meth2)
Using a balanced binary search tree (AVL tree)(meth3)
The input is a sequence of strings consisting of upper and lower case letters and digits; strings must be inserted according to the following rule:
Meth3 if the first character of the string is upper case letter
Meth2 if the first character of the string is lower case letter
Meth1 if the first character of the string is a digit
Reject any strings that contain other characters (with appropriate message)
There is no limit on the length of the sequence (applies mainly to meth3). There is one sequence feeding all their symbol tables in arbitrary (interleaved) order.
At the end, print out all symbol tables, the hash tables as (index, content)-pairs, the search tree contents in order.
Test your program thoroughly; in particular, you must demonstrably get collisions for meth 1 and 2.Various assumptions will have to be made by you (e.g. length of strings, hash functions, format of input etc). You must carefully state and fully justify them in the outside documentation.
Program style:
Do not use global variables
Avoid goto
Any read must be followed by a write
For each procedure and function give a brief description
Document assumption
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:
C++
Must be 100% finished and received by buyer on:
Jun 2, 2003 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 |
|
|
|
|
|
N/A
|
May 31, 2003
11:34:11 AM EDT
|
9.74
(Excellent)
|
|
|
The simplest method to include
a balanced binary tree in a C++
program is to use the map object
from the STL. A map has balanced
binary tree preformance (because
of the balanced tree encapsulated
inside) without any of the
hassles maintaining pointers.
I can provide references to the
analysis, if necessary.
A map would be excellent if you
are only investigating performance
of various hashing strategies,
but not too exciting if your
markers need to see that you
can balance a binary tree.
However, STL objects are the
only way to implement 3 hashes
within your alloted budget.
A IDLER
Chief Software Architect
Idleswell Software Creations
|
|
|
|
|
This bid was accepted by the buyer!
|
$15 (USD)
|
May 31, 2003
7:51:26 PM EDT
|
9.74
(Excellent)
|
|
|
| Hello,
I will code your program using
objects from the C++ STL within
a day. I have implementations
for hash chaining (with STL
lists), double hashing, and
balance binary trees (as a STL
map) ready to modify for your
symbol table.
A IDLER
Chief Software Architect
Idleswell Software Creations
|
|
|
|
|
|
|