Recently, there has been somewhat of a public health scare related to the presence of a bacterium, cryptosporidium, in the water supply system of several municipalities. It has come to our attention that a band of literary terrorists is spreading the bacterium by cleverly and secretly embedding it in novels. You have been hired by a major publishing company to search a new novel for the presence of the word cryptosporidium. It is known that the terrorists have resorted to insertion of punctuation, capitalization, and spacing to disguise the presence of cryptosporidium; finding instances of the word requires more than doing a simple word search of the text. For example, in a highly publicized case, one page ended with the sentence “Leaving his faithful companion, Ospor, to guard the hallway, Tom crept slowly down the stairs and entered the darkened crypt” while the next page began with “Ospor, I dium, HELP!” cried Tom, as the giant bats he had disturbed flew around his head. Disaster was narrowly averted when a clerk luckily caught what he thought was a typo and changed “I dium” to “I’m dying” just as the book went to press. Since this publisher handles many books, it is essential that each one be scanned as quickly as possible. To accomplish this you have proposed to use many computers in parallel to divide the task into smaller chunks; each computer would search only a portion of a text. If successful, you stand to make a sizeable commission from the sale of networked computers to the publisher. Alternative approaches are as follows:
1. Divide the text into sections of equal size and assign each section to a single processor. Each processor checks its section and passes information (about whether it found cryptosporidium in its section, portions of the bacterium as the first or last characters of its section, or no evidence of the bacterium at all) back to a master, which examines what was passed back to it and reports on the book as a whole.
2. Divide the text into many more small sections than there are processors and use a workpool approach, in which faster processors effectively do more of the total work, but in essentially the same manner as described in the preceding approach.