Show Bid Request
Maps or Associative Arrays
Bid Request Id: 23597
|
|
|
|
Posted by: |
fadiii (2 ratings)
(Software buyer rating 10 )
|
|
Non-action Ratio: |
Above Average - 33.33%
|
Buyer Security Verifications: |
Good
|
|
Approved on: |
Aug 3, 2002
7:05:27 PM EDT
|
|
Bidding Closes: |
Aug 4, 2002
11:00:00 PM EDT
|
|
Viewed (by coders): |
172 times
|
|
Deadline: |
8/5/2002
TIME EXPIRED
|
|
|
|
|
Description:
Your assignment is to implement the map abstract data type whose specifications appear below and use it to:
implement a rudimentary spelling checker,
implement a program that checks anagrams,
implement a program that finds words which occur the same number of times in two text files,
link your map implementation with our program (top.c) to find the most commonly used words in a file.
Specification of Map
The specification for the interface to the map module is given to you in the map.h file. You must make and justify all design decisions for your implementation, based on the following important requirements:
We will test your map implementation under the assumption that its interface is as described in map.h. Thus, you must not change the interface specification.
You must implement the map, test it appropriately, and then report your effort in a test report (see below).
Binary Search Trees are not allowed (not that they are bad). You must use some kind of a hash table as it is a very powerful tool for searching.
Implement the programs described below.
Description of Programs
You must use C++. However, no STL is allowed. For C++ programs use extension .cc.
Deliverables:
Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
Complete copyrights to all work purchased.
You must submit four files, named map.h, map.cc, spell.cc, anagram.cc, and comm_freq.cc:
map.h
Contains the header file that defines the interface for your implementation. Remember, you must not alter our portion of the interface specification, you can only add to the header file those declarations necessary for your implementation.
map.cc
Contains your implementation of the map module. You will probably want to define other routines in here, but they must be declared static so that they cannot be used outside this file. You are free to copy some of the utility routines for manipulating map items that are already provided in our example map.c
spell.cc
Contains a main program, and some other functions you may find useful, for implementing a primitive spelling checker. The parameters are as follows:
spell [-f dictionary] [file]
If no dictionary is given, spell uses ~cfadii/public/words. If no file is given, spell reads from stdin. spell works by creating a map, then adding all the words in the dictionary as indices to the map, using any value (1 is fine). It then reads the file word by word, ignoring punctuation (i.e. it only looks at strings of consecutive alphabetic characters) and checks to see if they are in the map.
Warning: the words in the file may not be capitalized properly. Watch for this. You might want to try each potential word as-is, as well as with its first letter changed to lower-case, with all letters changed to lower case, etc. Try to do whatever is reasonable and then document it.
anagram.cc
Contains the main program, and other functions for finding words that are anagrams of each other. (For example: some of the anagrams of caret are: cater, crate, react, and trace.) Its invocation is:
anagram [file]
If no file is given, anagram reads from stdin. anagram works by reading the file one word at a time, translating each word into lower-case as it reads. It then stores each word in the map, indexed by its signature. (Here a signature is the letters of the word in alphabetical order. The signature of all the example words above is "acert", while the signature of anagram is "aaagmnr".) Before storing a word, it checks to see if a word with the same signature is already stored in the map. If so, it prints out the word already in the map along with the current word, but does not store the new word. So, if the following words (caret cater crate react trace) are fed into anagram the output produced might look like:
% echo caret cater crate react trace > anagram.data
% anagram anagram.data
caret cater
caret crate
caret react
caret trace
Check your output for the ~cfadii/public/words file mentioned above. (But do not do it with our implementation of map.c, see below.)
comm_freq.cc
Contains a main program, and some other functions you may find useful, which when called as:
comm_freq file1 file2
writes to stdin the list of words which occur in both files the same number of times. Each line of output contains an integer followed by alphabetically sorted list of words which occur this many times in both files. The output is sorted by the integer giving the frequency in decreasing order and the words in each line are sorted alphabetically.
You must also try map.h and a compiled version of YOUR map.c (in map.o) with our main program in ~cfadii/public/ass2/top.c which contains the main program, and other functions for finding the most used words in a file. Its parameters are:
top [-n cnt] [file]
where cnt is an integer. If the -n option is not given, then the top 10 words are printed, otherwise the top cnt words are. If no file is given, top reads from stdin. top works by adding each word to a map, with value equal to the old value for this word +1
Platform:
UNIX
Must be 100% finished and received by buyer on:
Aug 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:
I need the project completed by monday night at around 10:00 pm us and canada mountain time (GMT -7:00)
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)
|
|