The University of Melbourne
School of Computing and Information Systems
COMP10002 Foundations of Algorithms
Semester 1, 2021
Assignment 2
Due: 4pm Tuesday 25th May 2021
Version 1.0
1
Learning Outcomes
In this assignment you will demonstrate your understanding of dynamic memory allocation, linked data
structures, and search algorithms. You will further extend your skills in program design and implementation.
2
The Story...
Text analysis and understanding is becoming prevalent in our daily lives. For example, intelligent personal
assistant apps such as Apple Siri and Google Now process user requests by first converting voice to text with
a speech recognition algorithm, and then analysing the text and finding answers to the requests. Finally,
the answers found are read out by a text to speech (TTS) algorithm.
To help computers understand a sentence, there are a few standard preprocessing steps. Two preprocessing
steps of interest in this assignment are called stemming and Part-Of-Speech (POS) tagging.
Stemming reduces a word to its stem (that is, the root form). See the following example:
Sentence:
After stemming:
she
she
sells
sell
seashells
seashell
Here, ��sells�� is the third-person present form of ��sell��; ��seashells�� is the plural form of ��seashell��.
After stemming, the two words are reduced to their respective root forms. The word ��she�� is already in its
root form, and hence is unchanged.
POS tagging assigns parts of speech to each word, such as noun, verb, etc. See the following example:
Sentence:
POS tag
she
pronoun
sells
verb
seashells
noun
There are various algorithms for stemming and POS tagging. The core of those algorithms are linguistic
rules (such as ��remove the ending ��s�� of a plural noun to obtain its singular form��) and statistics (such as
how often ��cook�� is used as a verb instead of a noun). Dictionaries are also used to support those algorithms.
In this assignment, you will implement an algorithm for stemming and POS tagging using a dictionary.
Note that you do not need to have any knowledge in linguistics to complete this assignment.
1
3
Your Task
You are given a dictionary (with at least one and up to 100 unique words) and a sentence to be
processed in the following format.
$allocate
vt
#0allocated1allocated2allocating
$sell
vt vi n
#0sold1sold2selling3sells
$she
n pron
#3they
$the
art
#
$zebra
n
#3zebra
**********
she sells seashells
The input starts with a list of unique dictionary words sorted alphabetically. Each word takes three lines.
Line 1 starts with ��$��, which indicates the start of a word and is followed by the word itself (e.g., ��sell��).
There are up to 22 lower-case English letters in each word, with no upper-case letters or special characters.
Line 2 contains the possible POS tags of the word separated by space (e.g., ��vt��, ��vi��, and ��n�� represent
verb used with object, verb used without object, and noun, respectively). You may assume up to 5 POS
tags per word and up to 4 lower-case English letters per POS tag. (Hint: You may use either a single
string or an array of strings to store the POS tags �C the former is simpler.)
Line 3 starts with ��#��, which indicates the ending line of a word in the dictionary. It is followed by the
variation forms of the word. Each word can have up to 4 forms where each variation form may contain
up to 25 lower-case English letters:
1. Form ��0�� is the past tense form (e.g., ��sold��);
2. Form ��1�� is the past participle form (e.g, ��sold��);
3. Form ��2�� is the present participle form (e.g., ��selling��);
4. Form ��3�� is the plural form (e.g., ��sells��, note this is not the third-person present form).
The variation forms follow the rules below:
? A word may have (1) no variation forms, (2) the first three forms (such as a verb), (3) only the last
form (such as a noun), or (4) all four forms (such as a word that can be either a verb or a noun). You
do not need to check the POS tags to verify the variation forms that a word has.
? The forms of a word always appears in the ascending order, e.g., ��$0sold1sold2selling3sells��, not
��$3sells0sold2selling1sold��.
? The variation forms of a word can be the same (e.g., Forms 0 and 1 of ��sell�� are both ��sold��).
? A variation form of a word can be the word itself (e.g., Form 3 of ��zebra�� is still ��zebra��).
? You may assume that any two words in the dictionary will not share the same variation forms (e.g.,
the variation forms of ��allocate�� and ��sell�� are all different). You may also assume that any word
will not be a variation form of another word (e.g., ��allocate�� is not a variation form of any other
word in the dictionary).
(Hint: You do not need to understand what these variation forms mean for the assignment. You may simply
use a single string to store all variation forms of a word. For Stage 4, optionally, you can separate the
different variation forms and store them in multiple strings, which will help make the search process faster.)
2
The line ��**********�� indicates the end of the dictionary and the start of a given sentence.
The sentence given will occupy one line, where the words are separated by a single space. The sentence will
contain at least one word, but there is no upper limit on the number of words or the number of
characters in the sentence. Each word may contain up to 25 lower-case English letters. There will
be no punctuation marks (e.g., ��,�� or ��.��).
You will perform stemming and POS tagging on the sentence by consulting the given dictionary.
3.1
Stage 1 - Read One Dictionary Word (Up to 3 Marks)
Your first task is to design a struct to represent one word. You will then read in one word from the input
data (using standard input functions with input redirection; no file input operations needed), and output it
in the following format.
==========================Stage 1==========================
/* 26 ��=��s each side */
Word 0: allocate
POS: vt
Form: 0allocated1allocated2allocating
3.2
Stage 2 - Read the Whole Dictionary (Up to 7 Marks)
Next, continue to finish reading the whole dictionary. You need to design a proper data structure to store
the words read in. An array of struct��s will do the job nicely. When this stage is done, your program
should output: the total number of words in the dictionary and the average number of variation forms per
word (up to two digits after the decimal point, by using ��%.2f�� in the printf() function). The output of
this stage based on the sample input is as follows.
==========================Stage 2==========================
Number of words: 5
Average number of variation forms per word: 1.80
3.3
Stage 3 - POS-Tag the Words in Sentence (Up to 13 Marks)
Your third task is to read in the given sentence, break it into words, store the words in a linked data structure,
and output the words together with their POS tags one at a line. The output of your program in this stage
for the example above should be:
==========================Stage 3==========================
she
n pron
sells
NOT_FOUND
seashells
NOT_FOUND
Hint: You may used the getword() function (Figure 7.13 in the textbook, link to source code available in
lecture slides) to read the words in the sentence. You may modify the linked list in listops.c (link to source
code available in lecture slides) to store the words. You are free to use other linked data structures (e.g.,
queue, stack, etc) if you wish. Make sure to attribute the use of external code properly.
For POS tagging, you will use the binary search algorithm (Hint: You may use the binary_search() func-
tion, link to source code available in lecture slides, or bsearch() provided in stdlib.h) to look up each
word from the sentence in the dictionary. If the word is found, then output the word and all POS tags of
the word. If the word is not found, then output the word and ��NOT_FOUND��.
In this sample output, ��sells�� has not been matched because we are not considering the root forms of the
words in this stage. In real systems, stemming should happen before POS tagging. This is because, without
stemming, a word (e.g., ��sells��) that is not in its root form may not be found in the dictionary. In this
assignment, we perform POS tagging first because it is a simpler task.
If you are not confident with using linked data structures, you may use an array of strings to store the
words, assuming a maximum of 20 words in the sentence. However, if you do so, the full mark of this stage
will be reduced by 2 marks. Similarly, if you use sequential search for POS tagging instead of binary search,
the full mark of this stage will also be reduced by 2 marks.
3
3.4
Stage 4 - Stem the Words in Sentence (Up to 15 Marks)
The final task is stemming, that is, for each word in the given sentence, you need to look up its root form
from the dictionary, and output the root form. If a word is already in its root form, or the word cannot be
found in the dictionary, then simply output the word itself as the root form. Further, you need to perform
POS tagging on this root form. The output of your program in this stage for the example above should be
as follows (note a final newline character ��\n�� at the end of the output).
==========================Stage 4==========================
she
she
n pron
sells
sell
vt vi n
seashells
seashells
NOT_FOUND
At the end of your submission file, you need to add a comment that states the worst-case time
complexity of your root form search algorithm, and explains why it has that time complexity,
assuming that there are s words in the sentence and d words in the dictionary, each dictionary
word has up to f variation forms, and each form has a maximum length of m characters.
Hint: A simple approach is that, for every word in the sentence, apply sequential search on the dictionary
words and variation forms to look up the word. This is allowed for Stage 4 and will not incur mark penalties.
As a challenge (no bonus marks), see if you can use binary search instead of sequential search to find the
root form, for better efficiency. Note: if you use binary search in both Stages 3 and 4, you should not write
more than one binary search function. You should use function pointers to customise the behaviour of the
binary search function for different use cases.
4
Submission and Assessment
This assignment is worth 15% of the final mark. A detailed marking scheme will be provided on Canvas.
You need to submit your code in Grok Learning (https://groklearning.com) for assessment.
Submission will NOT be done via Canvas. Instead, you will need to:
1. Log in to Grok Learning using your student login details.
2. Navigate to the Assignment 2 module of our subject COMP10002 2021 S1: Foundations of Algorithms.
3. Place all your code in the program.c tab window (including any function from listops.c used).
4. Compile your code by clicking on the Compile button.
5. Once the compilation is successful, click on the Mark button to submit your code. (You can submit
as many times as you want to. Only the last submission made before the deadline will be marked.
Submissions made after the deadline will be marked with late penalties as detailed at the end of this
document. Do not press the Mark button after the deadline unless a late submission is intended.)
6. Two sample tests will be run automatically after you make a submission.
Make sure that your
submission passes these sample tests.
7. Two hidden tests will be run for marking purpose. Results of these tests will not be available until
after the submissions are marked.
You can (and should) submit both early and often �C to check that your program compiles correctly on
our test system, which may have some different characteristics to the lab machines and your own machines.
You will be given a sample test file test0.txt and the sample output test0-output.txt. You can test your
code on your own machine with the following command and compare the output with test0-output.txt:
mac: ./program < test0.txt
/* Here ��<�� feeds the data from test0.txt into program */
Note that we are using the following command to compile your code on the submission system (we name
the source code file program.c).
gcc -Wall -std=c99 -o program program.c
4
The flag ��-std=c99�� enables the compiler to use a more modern standard of the C language �C C99. To
ensure that your submission works properly on the submission system, you should use this command to
compile your code on your local machine as well.
You may discuss your work with others, but what gets typed into your program must be individual work,
not from anyone else. Do not give a (hard or soft) copy of your work to anyone else; do not ��lend�� your
memory stick to others; and do not ask others to give you their programs ��just so that I can take a look
and get some ideas, I won��t copy, honest��. The best way to help your friends in this regard is to say a
very firm ��no�� when they ask for a copy of, or to see, your program, pointing out that your ��no��, and their
acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program that
undertakes deep structural analysis of C code identifying regions of similarity will be run over all submissions
in ��compare every pair�� mode. See https://academichonesty.unimelb.edu.au for more information.
Deadline: Programs not submitted by 4pm Tuesday 25th May 2021 will lose penalty marks at the
rate of 2 marks per day or part day late. Late submissions after 4pm Friday 28th May 2021 will not be
accepted. Students seeking extensions for medical or other ��outside my control�� reasons should email the
lecturer at jianzhong.qi@unimelb.edu.au. If you attend a GP or other health care professional as a result of
illness, be sure to take a Health Professional Report form with you (get it from the Special Consideration
section of the Student Portal), you will need this form to be filled out if your illness develops into something
that later requires a Special Consideration application to be lodged. You should scan the HPR form and
send it in connection with any non-Special Consideration assignment extension requests.