IT 279
\nFall, 2022
\nCaliff
\nProgramming Assignment 2:
\nWorking with Dictionaries
\nDue date for Part 1: Monday, September 26, 2022 at 11:55 pm
\nDue date for Part 2: Wednesday, October 5, 2022 at 11:55 pm
\nRemember that this is an individual assignment. Do not discuss with your classmates (or
\nothers) and do not search for code on the web. You are encouraged to come to me for
\nhelp.
\nDescription:
\nYou are developing a C++ program that does spell checking on a text file. The program
\nwill take 3 command line parameters which are names for:
\n1) a file with a list of correctly spelled words
\n2) a text file to check
\n3) an output file for the structure of the dictionary (not relevant to the task, but
\nimportant for grading your data structure accuracy).
\nThe program will first build a dictionary from the word list. Then it will check the file,
\nprinting information about each misspelled word and suggestions for possible corrections
\nto standard output. Finally, it will print the dictionary structure to the specified output
\nfile.
\nFormat of spelling output
\nFor each misspelled word print the word and the line it was found on followed by
\ninformation about the suggestions found, followed by a blank line. Examples:
\nsaed on line 5
\nSuggested corrections:
\nsaved
\nsad
\nremirmand on line 6
\nNo suggestions found
\nNote that the first line of the file is line 1, not line 0. We want this output to be human friendly, and most humans start counting at 1, rather than 0. Use tabs for the indentation
\nof the suggested words.
\nHow to generate suggestions
\nAs suggested corrections, list any words in the dictionary that are obtainable by applying
\nany of the following rules (one at a time):
\n1. Add one letter to the word (at any position)
\n2. Remove one letter from the word
\n3. Exchange adjacent characters
\nThere is an opportunity to earn extra credit by thoughtfully expanding the suggestion list.
\nSee below.
\nYou will be starting with a partial program, which includes a dictionary, implemented as
\na basic binary search tree and the framework of the actual program spell checking
\nprogram.
\nYou will be filling in the part of the program that reads the word list and build the
\ndictionary as well as the part that does the actual spell checking.
\nThen you will also be modifying the dictionary to be an AVL tree implementation. Note
\nthat your book does have some useful reference code to help you get started with the
\nAVL tree conversion.
\nFor part 1, you will submit your program file and your AVL tree implementation, based
\non the binary search tree implementation you were given. The program you submit must
\nwork with either your Dictionary implementation or the provided Dictionary with NO
\nchanges whatsoever. If the program does not compile with either Dictionary version, it
\nwill be considered a compile-time error (automatic F).
\nFor part 2, you will create a new Dictionary with the exact same interface (i.e. the same
\npublic function signatures) but implemented as a hash table using double hashing to
\nhandle collisions. You will submit your program with that Dictionary. The program must
\nstill work with both the original Dictionary and your hash table with no modifications. If
\nyour AVL tree had issues and you have fixed it for an improved grade, you may also
\nresubmit the AVL version of the Dictionary.
\nSimplifying Assumptions:
\n\u25aa We don\u2019t care about case; convert everything to lower case when reading from all
\nfiles.
\n\u25aa Words are strings of letters (a-z). Treat everything that isn\u2019t a letter as breaking
\nup words. Note that this means you may have multiple \u201dwords” on a single line in
\nyour word list \u2013 both should be entered in the dictionary. It also means that you
\nmay have duplicates in your word list, which must be appropriately handled.
\n\u25aa Each line ends with a newline character.
\n\u25aa All files are in the same directory as the program.
\nStarting and sample files:
\nYou will find Dictionary.h, Dictionary.cpp, and startingSpellChecker.cpp in
\n\/home\/ad.ilstu.edu\/mecalif\/it279\/Program3. Make sure you read them carefully, including
\nall comments and understand how the code works. You will be adding code to all of these
\nfiles. You should not be removing anything from any files for part 1. For part2, you will
\nlargely replace the contents of the Dictionary files, but make sure that you do not modify
\nthe prototypes\/headers of the public methods, and that you do not remove or add any
\npublic methods.
\nYou will also find a set of .txt files. I have provided dictionary files in multiple sizes
\nalong with test1.txt, a file with several misspellings.
\nYou have been given a simple test program (test_dictionary.cpp) along with correct
\noutput for the BST you were given as well as the AVL and hash table versions you will
\nbe creating.
\nI have also provided sample output from the spellchecker program. Note that the
\ndictionary structure output can be used to determine whether you are producing a correct
\nAVL tree. The hash table version of the dictionary structure output can be used to
\nexamine your hash table. In addition to the standard output files, I have provided output
\nfrom printing the dictionary in order for each dictionary so that you can check those with
\na separate little program. Note that the output from that will not vary from one
\nimplementation to another.
\nHash table details:
\nYou will use double hashing. The prime numbers that you will use for your hash table
\nsizes are {101, 211, 431, 863, 1733, 3469, 6947, 13901, 27803, 55609, 111227, 222461,
\n444929, 889871}. The prime numbers for your double hashing will be {97, 199, 421,
\n859, 1723, 3467, 6917, 13883, 27799, 55603, 111217, 222437, 444901, 889829}.
\nUse the hash function from figure 5.4 in your textbook.
\nRehash immediately before adding an entry that will push the table above 50% full.
\nExtra Credit Opportunity:
\nA and B programs may earn a small amount of extra credit for improving on the
\nalgorithm to generate suggested corrections. Requirement for extra credit:
\n1) You must indicate in the textbox in your ReggieNet submission that you have
\ndone the extra credit and you must explain how you are generating additional
\nsuggested words and indicate which dictionary file to use for your sample
\ninput\/output demonstrating your work.
\n2) You must have an optional 4
\nth command line parameter. If the 4th parameter is
\nprovided (whatever the contents of it), then your program will generate the
\nadditional suggestions. If there is no 4th command line parameter, the program
\nmust stick to the specified suggestions.
\n3) You must provide an input file and sample output that demonstrates your
\nadditional suggestions. Please try to use sample input that doesn’t generate many
\nsuggestions outside of your extra credit modifications. This will help in assessing
\nhow effective your additions were.
\n4) The additions must be thoughtful. An “improvement” that simply generates a
\nhuge number of suggestions without regard to whether they might make sense
\nwill not gain additional credit.
\nSubmission requirements:
\nWhen you use them, all versions of the dictionary must be in files named Dictionary.h
\nand Dictionary.cpp. However, we need to separate them out for submission. So your
\nAVL tree will be submitted as AVL_Dictionary.h and AVL_Dictionary.cpp. Your hash
\ntable will be submitted as Hash_Dictionary.h and Hash_Dictionary.cpp. The grading
\nprocess will rename your files before compiling.
\nRemember that your program file must work with the original Dictionary files as
\nsubmitted. Submit a single zip containing only the source code files (no folders, no data
\nfiles, no executables, no test files, not even any makefiles for this) and your sample test
\nand output files if doing extra credit.
\nA validation script will be provided that will help you determine whether your
\nsubmission zip file is correct. It is your responsibility to make sure that your program
\ncompiles successfully when you give the validation script your zip file. The validation
\nscript will NOT test your code for you; it will only make sure your program compiles.
\nFailure to submit your program in accordance with instructions will result in a grade
\nreduction.
\nGrading Standards:
\nPrograms will be graded in accordance with the provided Program Grading Criteria.
\nPart 1 will be 40% of the grade and Part 2 will be 60% of the grade. If you correct issues
\nwith part 1 when submitting part 2, you will receive half of the difference between the
\noriginal grade for part 1 and the grade that part of program would earn with the
\ncorrections.<\/p>\n","protected":false},"excerpt":{"rendered":"
IT 279 Fall, 2022 Califf Programming Assignment 2: Working with Dictionaries Due date for Part 1: Monday, September 26, 2022 at 11:55 pm Due date\u2026<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8802,7317,8805,8804,8803],"tags":[7676,7670,7555,3503,7673,7554,7550,7672,7671,7553,7551,7558,7556,7674,7552,7675,7557,7324],"class_list":["post-97334","post","type-post","status-publish","format-standard","hentry","category-dissertation-help-london","category-dissertation-help-online","category-dissertation-tutor","category-expert-assignment-help","category-university-assignment-help","tag-assignment-help-uk-no-1-writing-services-company","tag-assignment-uk-assignment-writing-service-assignment-help","tag-assignment-writer","tag-assignment-writing-help","tag-assignment-writing-help-in-london","tag-assignment-writing-service-uk-essays","tag-assignment-writing-service-uk-with-20-off-assignment-help","tag-best-assignment-writing-service-uk","tag-best-essay-writing-services-in-uk-online-essay-help","tag-cheap-assignment-writing-service-uk","tag-cheap-uk-assignment-writing-services","tag-custom-assignment-writing-and-proofreading-service","tag-online-assignment-help-uk","tag-uk-assignment-writing","tag-uk-assignment-geek","tag-uk-assignment-help-services-from-best-writing-experts","tag-uks-1-experts-proofreaders-hire-our-thesis-advisors","tag-university-assignment-help"],"_links":{"self":[{"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/posts\/97334","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/comments?post=97334"}],"version-history":[{"count":0,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/posts\/97334\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/media?parent=97334"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/categories?post=97334"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.studyproessays.com\/help\/wp-json\/wp\/v2\/tags?post=97334"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}