CS 136 Assignment 10

Due Monday, April 6 at 11:59 AM sharp (noon).

Please read the preamble in Assignment 1.

Only the C language features introduced in this course are allowed.


In your code, you do NOT have to check that the value returned from malloc (or realloc) is invalid (NULL).

You may assume that all C strings are null terminated: you do not have to assert this.

If a requires statement specifies that a structure is "valid", you may assume this, and you do not have to assert it.


Assignment 10 Problem 1. [15 Marks for correctness and efficiency.]

Write a C module mmstack.c that implements a Min/Max Stack ADT (MMStack) as described in mmstack.h.

We have provided a simple test-mmstack.c for you.

Note: we highly recommend you attempt to implement this problem on your own before revealing any tips.
Highlight the text in your browser to reveal the Tips.

TIP 1:

To achieve the desired efficiency for mms_length, add a length field to your mmstack wrapper structure.

TIP 2:

To achieve the desired efficiency for mms_max & mms_min, use an augmented linked list with two extra fields per node.


Assignment 10 Problem 2. [35 Marks]

Write a C module count.c that implements a Count ADT as described in count.h.

You will implement this ADT in two different ways, using two different data structures.
  1. [15 Marks for correctness and efficiency.]
    For part A, the integers are in the range 1..100. Use an array to implement the ADT.

  2. [20 Marks for correctness and efficiency]
    For part B, there is no restriction on the integers. Use a BST to implement the ADT.
We have provided a simple test-count.c for you (the tests are briefly described in count.h)

Note: we highly recommend you attempt to implement this problem on your own before revealing any tips.
Highlight the text in your browser to reveal the Tips.

TIP 1: (part A)

To store the counts, you can simply create a fixed array of size 101, where a[n] corresponds to the count for the number n (and a[0] is unused).

TIP 2: (part B)

You will want to use an augmented BST: for each node you will want a field to store the number (key), and a field for its current count.


Note: Problems 3 and 4 are necessary to solve Problem 5.

We have provided binary (.o) module solutions for problems 3 and 4. You can use these in two ways. You can use them to first develop your test programs for problems 4 and 5 before implementing a solution. You can also use them to complete problem 5 if you are unable to finish problem 3 and/or 4.


Assignment 10 Problem 3. [15 Marks for correctness and efficiency.]

Write a C module strqueue.c that implements the StrQueue ADT module described in strqueue.h.

In problem 5 we have provided a file2strqueue module that you may find useful for your testing.

Assignment 10 Problem 4. [20 Marks for correctness and efficiency.]

Write a C module dictionary.c that implements the Dictionary ADT module described in dictionary.h using a BST.


Assignment 10 Problem 5. [15 Marks for correctness.]

For this problem, you must write a C program spellcheck.c that implements a "Spell Checker" program. We have provided an initial spellcheck.c to get you started (you are not required to use this file).

First, read in words from a wordlist.txt file and generate a Dictionary of those words (we did this for you in the provided spellcheck.c).

Next, read in pairs of words from an autocorrect.txt file and generate a second Dictionary of those pairs of words. For each pair, the first word is the "key" and the second word is the "value".

Finally, read in words from the keyboard (or .in file). For each word, print out the spell-checked word according to the following rules. (Print it according to the first rule that it matches).
  1. Words that contain characters other than letters and the apostrophe (') are printed surrounded by underscores ('_'). For example, the word "Spider-Man!" would be printed as "_Spider-Man!_".
  2. Words whose lower-case equivalents appear in the wordlist dictionary are printed normally. For example, the word "AlgoRithM" would be printed as "AlgoRithM" if the word "algorithm" appears in the wordlist. You can assume the wordlist is all lower-case.
  3. Words that are a key in the autocorrect dictionary are replaced with the value of that key in the autocorrect dictionary, surrounded by asterisks. No case converions should be performed. For example, if the pair ("teh","the") is in the autocorrect dictionary, the word "teh" would be printed as "*the*". However, this rule would not apply to the word "TEH" unless that was also a key in the autocorrect dictionary.
  4. Words where none of the previous rules apply are printed surrounded by square brackets ('[',']'). For example, the word "asdf" would be printed as "[asdf]" (assuming it is not in the wordlist or the autocorrect dictionary).
After every word, print a space, except after every tenth word and after the last word. In those cases, print the newline character ('\n') instead. That is, you should print 10 words per line, and the last line should have a newline (and no space) at the end even if it contains fewer than 10 words. See the sample tests below if you are unclear on the format.

For this problem, we have provided a module (file2strqueue.c and file2strqueue.h) that will read in text (from the keyboard or a text file) and produce a StrQueue (P4) of all of the words.

We have provided a sample wordlist.txt and autocorrect.txt for you, but we may use different versions to test your program. The wordlist we provided has been conveniently sequenced to produce a balanced tree when inserted into your Dictionary.

For convenience, you may assume that no word is longer than 100 characters.

Here is a sample spellcheck.in and spellcheck.expect file.