We want to find all palindromes (i.e., words that read the same forwards and bac
ID: 3861168 • Letter: W
Question
We want to find all palindromes (i.e., words that read the same forwards and backwards like “abba”) in a text file and how many times each palindrome appears. Someone has designed a distributed algorithm whereby each mapper will do the following:
for each line L in the text do
for each word W in line L do
{
create a string R that is the reverse of the word W;
if (R == W)
then output (W, 1) as a (key, value) pair;
}
a. Explain what each reducer would then do to give us the answer we want. Be specific!
b. Explain the I/O and memory complexity of this algorithm. Be specific!
Explanation / Answer
In the given algorithm we can see their that there are two loops nested in each other.
So obiously it will have time complexity of N*N.
What happening inside the algorithm is, first we are reading the whole text file.
Then in the first loop we are looping over each line one by one.Then in next loop we are looping
over each word one by one. while looping over each word we are reversing each word and checking
that is this the palindrome of the given word. if yes then we will store this word in the map with
starting value 1 and key as that palindrome number.
Complexity - Time complexity of this algorithm is very high. It is not opimized
Space complexity will be linear so it will not effect the program on high level.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.