Show Bid Request C++ project Bid Request Id: 35347 Bookmark in my 'To Do' list Posted by: blueonion (2 ratings) (Software buyer rating 10) Non-action Ratio: Very Good - 0.00% Buyer Security Verifications: Good Approved on: Nov 14, 2002 12:53:22 AM EDT Bidding Closes: Nov 15, 2002 12:00:00 PM EDT Viewed (by coders): 346 times Deadline: 11/16/2002 TIME EXPIRED Phase: 100% of work completed and accepted. Coder has been paid. Max Accepted Bid: Bidding is closed Project Type: Personal Project / Homework Help Bidding Type: Open Auction Categories: C++ / C Enter chat room for this bid request (0 active users at Jul 12, 2003 8:48:30 AM EDT) Description: Consider a set of variable-length strings (words). Each string has an arbitrary length and consist of only A-Z characters (with no space). Let the combined total length of all these strings be n characters. We want to sort the strings in O(n) time (you must handle the strings on a character by character basis in your program). Note that if the maximum word-length was a constant, or if all words had equal length, a simple radix sort would work. But a case of arbitrary lengths requires a more careful handling. This means that if we treat all words as if they all had the maximum length, the complexity could become O(n^2), which is undesirable. Write a program to implement the above algorithm. First read the stings from a file f. assume that each string start at the beginning of a new line, has an arbitrary length (possibly over 80) and ends with end-of-line characters. Store the stings sequentially in a character array S[0…n-1], and store the (start, length) attributes of the strings in another array A[0…n-1] of records. (The record A[i] has two fields: A[i].start is the starting index of string i. and A[i].length is the length of sting i. During the sorting phase the strings are never moved, only the attributes are moved. First describe an algorithm to sort these words in O(n) time using radix sort with some kind of pre-processing. Suppose we do this so in phase j (when sorting by column j) you have to deal only with those stings that have a true character in that column. In this phase your algorithm should not examine the length of all strings and that is why you need to have some kind of pre-processing. In order to get the bid you need to tell me what type of pre-processing you would apply to solve this problem. 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: the program should be in C++ and runs in borland 5.5 in Window environment with good comment. Must be 100% finished and received by buyer on: Nov 16, 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. 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! idleswell (73 ratings) in Saint John, New Brunswick Canada Bid id: 388,042   $32 (USD) Nov 14, 2002 9:39:08 AM EDT  9.75 (Excellent)     Hello, I will code your radix sort in 2 days effort. Here is the pre-processing I would do to handle the variable length of the strings: While reading the strings, I intend to prepare work lists of all strings that must be sorted at each step in the radix. Each string would appear in each work list from 1 through the length of that string. Then, when sorting each step in the radix, all the strings requiring sorting would be ready in the work list. With this preprocessing, you should never have to check the length of any strings while sorting. Your program coding will demonstrate clarity of design and supporting documentation. A IDLER Chief Software Architect Idleswell Software Creations           See 9 private reply(ies) to/from idleswell.