Month: November 2017

spellchecker

Posted on by cs daixie
This assignment requires you to create four files: SpellChecker.h, SpellChecker.cpp, WordCounts.h
and WordCounts.cpp
. The class definitions should be in the .h files and the implementation of the
methods in the .cpp files. Your main.cpp file should be used to test your implementation of your
classes. You can create a project in CodeBlocks to create the main.cpp file and add the two classes to
the project. CodeBlocks can create projects (use console application template) and will create the .h
and the .cpp files when you add classes to the project. Code Blocks will compile each file for you and
link them into the project executable for testing.
You should
NOT be using the #include
“SpellChecker.cpp”
and #include “WordCounts.cpp” in your main file to include your code
into
main.
1. Once you have your code running on your virtual machine (VM), submit a zip file with
main.cpp, SpellChecker.h, SpellChecker.cpp, WordCounts.h and WordCounts.cpp to the
autograder
COG .
2.
You must also submit your code to Moodle to get full credit for the assignment.
● 10 points: Comments at the top of your source files should include your name,
recitation
TA, and the assignment and problem number.
● 10 points: Algorithm descriptions comments in your code submission to describe
what
your code is doing.
● 10 points: Code in your
main() function that is testing the functions in
SpellChecker.cpp
and WordCounts.cpp. 10 points will be deducted if the
main.cpp you submit to moodle does not have code testing the functions you have
written in
SpellChecker.cpp and WordCounts.cpp. Remember that COG does
not run your
main(), it runs its own main. (Code you write in main() will not
impact
your COG runs).
● NEW starting with this assignment! 10 points: Proper and consistent indentation of
the code. You will have 10 points deducted if the indentation is missing or if the code
in
the files is using an inconsistent style.
Part
I
In this part of the assignment, you are to create a class,
SpellChecker
. You will define some class
data members, member methods and helper functions. The class methods will be used to check the
spelling of words and assess the word count across documents. Elements of this assignment are
intentionally vague; at this point in the semester, you should be able to make your own decisions
about appropriate data structures for storing and looking up data, as well as defining helper
functions. You can assume that your code will never be storing more than 10,000 valid or corrected
words.
SpellChecker
should have at least the following Public members:
● string language
: the name of the language this spell checker is using (i.e. “English”, “Spanish”,
“Italian”,
“Hindi”, …)
SpellChecker
should have at least the following Private members:
● char
start_marker: used for marking the beginning of an unknown word in a string
● char
end_marker: used for marking the end of an unknown word.
SpellChecker
should have three constructors:
● Default
Constructor, the one with no arguments.
● Second
constructor that takes a string for the object’s language
.
● Third constructor that takes a string for the object’s
language and two filenames as
parameters. The first filename specifies the file with correctly spelled words and the second
filename
specifies the misspelled words with their corrections.
You
will be dealing with two different files:
● The
data in the first filename supplies a list of correctly spelled words, one word per line:
● The data in the second filename contains a list of misspelled words and their correct
spellings.
The word and its correction are separated by a tab character (‘\t’):

It is
very important you understand the format of this file. The correctly spelled words may have
spaces
in them! For example a file that converts common texting abbreviations into words:

The constructor with the filename arguments should open the files and read them into an
appropriate data members of the class. To find if a
word is a valid spelling or is a misspelling, you
should
think about storing the words in the right structure so that it’s easy to search and access it.
SpellChecker
should also include the following public methods:
● bool readValidWords(string filename)
: this method should read in a file in exactly the
same way as detailed in the description of the constructor. This file will have the format
specified for correctly spelled words. This method should return a boolean of whether or not
the file was successfully read in. This method should add the words from the file to the list of
words
already contained in the object.
● bool readCorrectedWords(string filename)
:
this method should read in a file in exactly
the same way as detailed in the description of the constructor. The file will have the format
specified for the wrongly spelled words and their corrected spellings. This method should
return a boolean of whether or not the file was successfully read in. This method should add
the
words from the file to the list of words already contained in the object.
● Setters and Getters for the markers to be used for unknown words (see description of
marker
use below).
○ bool
setStartMarker(char begin)
○ bool
setEndMarker(char end)
○ char
getStartMarker()
○ char
getEndMarker()

string repair(string sentence)
: Repair will take in a string of multiple words, strip out all
the punctuation, ignore the case and return the sentence with all misspellings replaced or
marked.
For example: here are what the following calls would return:
If you cannot find a word in the list of valid words or in the list of misspelled words (for
instance, if the word is misspelled beyond recognition), you should just return the misspelled
words with the
start_marker in front and the end_marker at the end. For example: if
start_marker
and end_marker are both ‘~’, the call:
● (Challenge Problem) repairFile(string input_filename, string output_filename)
: Repair
will process all the lines in the input file and write the repaired lines to the output file. The
resulting file would still have all of the punctuation, but with individual words corrected.
One way to break this down into simpler tasks would be to first check each stripped word for
spelling. The second task would be to replace the corrected word within the sentence will all
its
punctuation.
Testing
Testing of your class and all of its methods is now in your hands. You must determine the test cases
that will test if your implementation returns the correct results in all conditions. For example, you
would need to write code that will declare SpellChecker objects with each of the possible
constructors, to verify that each of those methods will create and initialize the object correctly. The
same must be done for each of the other public methods to verify that your implementation works
correctly
in all possible conditions and ordering of calls to those methods.
Once
you are satisfied that your code works as intended, submit it to COG for its evaluation.

Part
II
In this part of the assignment, you are to create a class,
WordCounts
. You will define some class data
members, member methods and helper functions. The class methods will be used keep a running
count of the number of times each word is being used. You can assume that there will never be more
than 10,000 unique words being counted. Your class will provide the following public methods to
support
counting word usage:
● void tallyWords(string sentence):
This function will take in a string of multiple words,
remove the punctuation, and increment the counts for all words in the string. If a word is not
already in the list, add it to the list. This function is used to keep
a running count of each
unique word processed; that means multiple calls to the function should update the count of
the
words, not replace them. If we call the function three times:
The count for the words “the” and “fox” should be 2, the count for the words “brown”, ”red”,
”blue”,
“cat”, and “teh” should be 1.
● int getTally (string word)
: return the current count of the given word. If the word is not
found
to be in the current list of words, return 0.
● void
resetTally(): reset all word counts to zero.
● int mostTimes(string words[], int counts[], int n)
: find the n most common words in
the text that has been counted and return those words and counts in via the arrays given as
parameters.
Assume the arrays are large enough to hold the number of elements requested.
Testing
Testing of your class and all of its methods is now in your hands. You must determine the test cases
that will test if your implementation returns the correct results in all conditions. For example, you
would need to write code that will declare
WordCounts objects with each of the possible
constructors, to verify that each of those methods will create and initialize the object correctly. The
same must be done for each of the other public methods to verify that your implementation works
correctly
in all possible conditions and ordering of calls to those methods.
Once
you are satisfied that your code works as intended, submit it to COG for its evaluation.

Implementation of Monitor

Posted on by cs daixie
The goal of this problem is to solve an inter-thread communication problem called Sleeping Stylist using semaphores.
There are 40 customers but only 1 stylist in a hair salon. In the salon, there are 5 chairs that customers can sit and
wait for the stylist. Since there is only one stylist, only one customer can get a haircut at a time. If there are no
customers in the salon, the stylist sleeps. When a customer enters the salon, he/she wakes up the stylist and then
waits for the stylist to get ready. The stylist then takes the customer. If the stylist is busy with a customer and more
customers arrive, they sit and wait in the 5 waiting chairs. If a customer enters the salon and it is full (there are
already 5 waiting customers while a customer is getting a haircut), the customer leaves to go shopping and then
comes back later to try to get a haircut again. Every customer must eventually get a haircut (no starvation).
When the stylist nishes with a customer, it takes the next waiting customer. If there are no waiting customers,
the stylist goes back to sleep. The pseudocode is given in Figure 1. Note that the pseudocode only suggests a
guideline. Feel free to add more parameters, variables, and functions as you think necessary.
You will use the pthread package to create 40 customer threads and 1 stylist thread. The program will be
called “sleepingStylistSem.c”. Use a delay loop to slow down each thread (see the pseudocode) by adjusting the
loop bound so that you get a steady stream of customers to compete to get haircuts by the stylist. You want to
ensure that your program can demonstrate its operation when the salon is not full and when the salon is full. Also
make sure that we can see the gradual build up of customers waiting in the chairs. You must complete your
work in csce.unl.edu. Use POSIX semaphore (sem init, sem get, sem post, etc.). Also note that OS-X unlocks
semaphores differently.
3
Sleeping Stylist with Monitor (40 pts)
The goal of this problem is to create your own monitor to provide synchronization support for the sleeping stylist
problem. You will use the pthread package to create 40 customer threads and 1 stylist thread. There are 5 waiting
chairs in the salon. You then need to use a semaphore to create your entry queue.
You also need to create your own Condition Variables (CVs). That is, you CANNOT USE the CV type
provided by the pthread library (e.g., pthread cond init). Condition variables are used to suspend processes or
threads that cannot continue executing due to a specic monitor state (e.g. the stylist is busy). They are also used
to awaken suspended processes or threads when the conditions are satisable. To create your own CVs, follow the
following steps:
1. You will create a new variable type called CV. To do this, you will create a new structure called cond.
The structure consists of an integer variable that indicates the number of threads blocked on a condition
variable and a semaphore used to suspend threads. Your implementation must follow the signal-and-wait
discipline. If your implementation follows a signal-and-continue discipline, you would automatically
lose 20 points. There are three operations that your CV will support. They are:
(a) count(cv)—returns the number of threads blocked on the cv.
(b) wait(cv)— relinquishes exclusive access to the monitor and then suspends the executing threads.
/ ==== s l e e p i n g S t y l i s t S e m . c ====//
# d e f i n e CHAIRS 5
# d e f i n e DELAY 100000 / /
a d j u s t
t h i s
v a l u e
s e m a p h o r e mutex = 1 ,
s t y l i s t = 0 c u s t o m e r s = 0 ;
i n t
w a i t i n g = 0 ;
v o i d main ( v o i d )
{
/ /
c r e a t e 40 c u s t o m e r
t h r e a d s and 1
s t y l i s t
t h r e a d
/ /
don ’ t
f o r g e t
t o
j o i n
t h r e a d s
}
v o i d
s t y l i s t ( v o i d )
{
i n t
j ;
w h i l e ( 1 ) {
down(& c u s t o m e r s ) ;
down(& mutex ) ;
w a i t i n g = w a i t i n g 1 ;
up (& s t y l i s t ) ;
up (& mutex ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
c u t
h a i r
}
}
v o i d c u s t o m e r ( v o i d )
{
i n t
j ;
w h i l e ( 1 ) {
down(& mutex ) ;
i f
( w a i t i n g < CHAIRS) {
w a i t i n g = w a i t i n g + 1 ;
up (& c u s t o m e r s ) ;
up (& mutex ) ;
down(& s t y l i s t ) ;
break ;
}
e l s e {
up (& mutex ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
go s h o p p i n g
}
}
}
Figure 1: Pseudo-code for the sleeping stylist problem using semaphores
(c) signal(cv)—unblocks one thread suspended at the head of the cv blocking queue. The signaled thread
resumes execution where it was last suspended. The signaler exits the monitor and suspends itself at
the entry queue
.
You should pay special attention to the following questions during your implementation:
(a) How would you guarantee that only one thread is inside the monitor at one time?
(b) How would you make sure that a suspended thread (due to wait) resumes where it left off?
(c) How would you initialize the necessary data structures to support your monitor and make them visible
to all threads?
(d) How would you produce the necessary debugging information that you can use to verify the correctness
of your implementation? For example, what output will you need to show that your implementation
follows the signal-and-wait discipline and not signal-and-continue. How can you show that the num-
ber of waiting threads and the corresponding counter is consistent? How can you show how many
customers have already got their haircuts and how many are still trying? Remember, you’ll need to
convince the grader that your implementation follows our specication precisely.
2. You will create function mon checkCustomer that manages the waiting list and takes a customer to the
styling chair. It rst invokes signal on condition variable stylistAvailable to indicate that the stylist is not
busy. If the salon is empty, it then invokes wait on the condition variable customerAvailable to put the
stylist to sleep.
3. You will create function mon checkStylist that puts a customer on the waiting list if the salon is not
full. If the stylist is sleeping or busy, it rst invokes wait on the condition variable stylistAvailable. It also
invokes signal on condition variable customerAvailable to indicate that a customer is waiting.
4. You will create function customer, stylist, and salonState.
Note that the pseudocode given in Figure 2 provides a guideline on how to program your monitor. However,
this pseudo-code may have incorrect logics. It is part of your responsibility to identify faults and implement a
correctly working monitor.
These functions and your CVs will be implemented in a separate C le. Thus, you should at least have two C
source les, monitor.c and sleepingStylistMon.c. You can compile monitor.c using -c ag (e.g. gcc -c monitor.c).
This will give you the object le (monitor.o) that can be linked to your sleepingStylistMon.c (gcc sleepingStylist-
Mon.c monitor.o). You must complete this part in csce.unl.edu.
4
Submission (10 pts)
Create a zip le that has all your solutions and submit it through canvas. The step to create proper directory
structure is as follows:
1. Create a directory called lastname hw3 (replace lastname with the submitter’s lastname). If you are working
with your partner, only one submission is needed.
2. Create subdirectories: prob1 and prob2 under lastname hw3.
3. Place your solutions in the proper directory. Provide README.txt le for each problem. To earn 10 points,
each README le should:
Provide the name of every member on your team.
Specify the instruction on how to test your solution.
Document the amount of time you spent on each problem.
Quantify the level of challenge from 0 to 5 (5 is most difcult) for each problem.
4. Once all solutions are properly stored, zip the folder lastname hw3 and submit the zip le through canvas.
Note that canvas will only take .zip extension. If you use other means to compress your le, the system will
not accept it. You can use “zip -r” command in csce.unl.edu to zip your folder.
/ / ==== s l e e p i n g S t y l i s t M o n . c ====//
# d e f i n e DELAY 100000 / /
a d j u s t
t h i s
v a l u e
v o i d main ( v o i d )
{
/ /
c r e a t e 40 c u s t o m e r
t h r e a d s and a
s t y l i s t
t h r e a d
/ /
don ’ t
f o r g e t
t o
j o i n
t h r e a d s
}
v o i d s a l o n S t a t e ( v o i d )
/ /
p r i n t how many c u s t o m e r s a r e
w a i t i n g
{
/ /
p r i n t
t h e
s t a t e
o f
t h e
w a i t i n g
c h a i r
u s i n g
t h e
f o l l o w i n g
/ /
f o r m a t :
f i r s t
u s e d
c h a i r :
l a s t
u s e d
c h a i r :
c o u n t
\n .
}
v o i d
s t y l i s t
( v o i d )
{
/ /
add more v a r i a b l e s
a s n e e d e d
i n t
j ;
w h i l e ( 1 ) {
s a l o n S t a t e ( ) ;
m o n c h e c k C u s t o m e r ( ) ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
c u t
h a i r
}
}
v o i d c u s t o m e r ( v o i d )
{
/ /
add more v a r i a b l e s
a s n e e d e d
i n t
j ;
w h i l e ( 1 ) {
s a l o n S t a t e ( ) ;
i f
( m o n c h e c k S t y l i s t ( ) )
break ;
f o r ( j = 0 ; j < DELAY ;
j + + ) ;
/ /
go s h o p p i n g
}
}
/ / ===== m o n i t o r . c ===== / /
# d e f i n e CHAIR 5
c o n d s t y l i s t A v a i l a b l e ,
c u s t o m e r A v a i l a b l e ;
i n t c u s t o m e r = 0 ;
i n t
s t y l i s t = 0 ;
/ /
add more v a r i a b l e s
a s n e c e s s a r y
( e . g . a s e m a p h o r e f o r
e n t r y q u e u e )
v o i d m o n c h e c k C u s t o m e r ( )
{
s t y l i s t = s t y l i s t + 1 ;
s i g n a l ( s t y l i s t A v a i l a b l e ) ;
/ /
s t y l i s t ’ s r e a d y t o
c u t
h a i r
i f
( c u s t o m e r == 0 )
/ /
do n o t u s e w h i l e
h e r e
w a i t ( c u s t o m e r A v a i l a b l e ) ;
c u s t o m e r = c u s t o m e r 1 ;
}
i n t
m o n c h e c k S t y l i s t ( )
/ /
T h i s
f u n c t i o n may h a v e
f a u l t s .
/ /
I f
y o u t h i n k
i t
d o e s ,
y o u ’ l l
n e e d t o
f i x
i t .
{
i n t
s t a t u s = 0 ;
i f
( c u s t o m e r < CHAIRS) {
c u s t o m e r = c u s t o m e r + 1 ;
s i g n a l ( c u s t o m e r A v a i l a b l e ) ;
i f
( s t y l i s t == 0 )
/ /
do n o t u s e w h i l e
h e r e
w a i t ( s t y l i s t A v a i l a b l e ) ;
s t y l i s t = s t y l i s t 1 ;
s t a t u s = 1 ;
}
r e t u r n
s t a t u s