CS 136 Assignment 10

Due Friday, April 4 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 PRE-condition is that a structure is "valid", you may assume this, and you are not required to to assert it.


Assignment 10 Problem 0. [10 BONUS Marks]

Use the Seashell environment to complete one of the following Assignment 10 questions.

To login into Seashell, visit:

https://www.student.cs.uwaterloo.ca/seashell/

Complete the seashell feedback form: seashell-feedback.txt and submit it to marmoset.

Submissions with good quality feedback will receive the full 10 marks.

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.


Assignment 10 Problem 2. [35 Marks + 5 Marks Bonus]

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 + 5 bonus efficiency marks (for order).]
    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 it's current count.

TIP 3: (order)

To determine order(c,k) in O(n) time, you will want to traverse data "in order" [see A9 for how to traverse your BST in order].



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.

Problem 3: strqueue.o [VirtualBox], strqueue.o [Mac Labs], strqueue.o [Seashell].
Problem 4: dictionary.o [VirtualBox], dictionary.o [Mac Labs], dictionary.o [Seashell].

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 word according to the following formatting specifications: 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.1 and spellcheck.expect.1 file.