Homework # 2: Circle the Word with OpenMP

CS 4000
Homework # 2: Circle the Word with OpenMP
(30 pts.)
Consider the following problem. Given an n×n matrix of characters, and a list of words,
output the location of the lexicographically first occurrence of each word in the matrix. This
is very similar to the somewhat popular “Circle the Word” puzzles that you may have played
before. Consider the following matrix of characters.
m m y a l c g y e a
s v x g g e f i t k
n y g y r v j x n s
p u b b e f q j p p
j b i r t r l h u t
g l e s s o m m a x
w j j h m g l c k r
m g b s a e s r o h
n w v i h f t y v e
o l p f r f d c a j
Can you find the words “horse”, “gerbil”, “hamster”, “fish”, “cat”, and “frog” in this matrix
of characters? (Note that any individual word can appear in any of 8 directions within the
the matrix. However, the letters must be contiguous.)
Your task is to write a program that outputs the location of the first character (x, y) of
the lexicographically first occurrence of each word from the list in the matrix. (If a word
appears twice, at the locations (x1, y1) and (x2, y2), the lexicographically first of these two
is (x1, y1) if x1 < x2 or x1 == x2 and y1 < y2.) The natural approach is to search the vector
via brute force. (For this problem, the words on the list may not be limited to dictionary
words.)
For testing purposes, you will solve this problem by implementing a single class called
“CircleTheWordSolver” with at least one public member function
vector<pair<int, int> > word_locations(
vector<vector<char> > &puzzle,
vector<string> &wordlist);
This member function will return the lexicographically first word locations of all the
words in the list wordlist. If the word does not appear in the puzzle, return h−1, −1i for
the location.
I have provided a test harness Test_Harness.cc that reads in the data and produces the
output. Your solutions should work the provided test harness.
1. (10 pts.) Implement CircleTheWordSolver without using any parallelism.
Implement your program in C++ and provide adequate documentation. Test input/output examples will be provided to help you debug your code. Your program
should be reasonably efficient.
2. (20 pts.) Use OpenMP to implement a parallel version of the program that you implemented in part #1. Compare your program’s running time to your original program.
Your program should be at least 75% efficient on a four core machine on input of a
1000 x 1000 puzzle with a word list of 500 words.
Implement your class in C++ and provide adequate documentation.