Boolean Algebra on the Internet

In case you were convinced that search engines work by magic and pixie dust, this lesson is here to prove otherwise. Actually, search engines are fancy computer programs (and here it is a programming class, how convenient). They have two parts. The behind the scenes part occurs when Google runs some fancy programs called web crawlers to search the internet and see what is there. They store their findings in a big file. When you run a search, the second half kicks in. Google gathers your request and searches in its file. It returns things that match what you want.

Now for the exciting part: how does Google make those matches? The same as any other program. With a boolean expression!

start with the first entry
while (! at the end of the file)
   if (whatTheUserwants.equals(entryInTheFile))
       return entryInTheFile;
   move on to the next entry

(now, Google has a better algorithm than this. This is a TERRIBLE search called a linear search, but it gives you an idea).

In fact, since you are now Boolean expression experts, you can make better Boolean expressions when you use Google and get better matches returned. You don’t always have to make boring searches based on equals! You can use and, or and not.

Questions

A. In the Advanced Search Window:

"With all of the words" is equivalent to AND (&&). All words must be found to be returned.
"At least one of the words" is equivalent to OR (||). One or more of the words must be found to be returned.
"Without the words" is equivalent to NOT (!). The reverse of your expression will be returned.
"With the exact phrase" is a fancy AND (&&). It is only true if the order is maintained.

1. Match the Google search to the Java-like expression to what would be returned by Google. Assume that you are matching a String s.

Google Search	Java-Like Expression	What Google Would return
1. "With all of the words" Java Gosling	A. s contains "Java" \|\| s contains "Gosling"	a. pages that had the exact phrase "Java Gosling" in them. I don't think any would exist, this is a stupid phrase to search.
2. "At least one of the words" Java Gosling	B. ! (s contains "Java" \|\| s contains "Gosling")	b. pages that had both Java and Gosling in them would be returned.
3. "Without the words" Java Gosling	C. s contains "Java" && s contains "Gosling"	c. pages that had Java or Gosling or both in them would be returned.
4. "With the exact phrase" Java Gosling	D. s contains ("Java Gosling")	d. pages that didn't have either Gosling or Java in them. If Gosling appeared, it would be returned, ditto Java.

2. De Morgan's law states that !(A&&B) = !A || !B. As well, !(A||B) = !A &&!B. That being stated, what is another way that you can write: ! (s contains "Java" || s contains "Gosling") ?

3. Match the Google search to the Boolean expression. Assume that you are matching a String s. (One has two matches)

Google Search	Java-like Boolean Expression
1. "With all of the words" fluffy cat	A. s contains "fluffy cat"
2. "At least one of the words" fluffy cat	B. (s contains "fluffy") && (s contains "cat")
3. "Without the words" fluffy cat	C. ! (s contains "fluffy" \|\| s contains "cat")
4. "With the exact phrase" fluffy cat	D. ! (s contains "fluffy") && ! (s contains "cat")
5. "Without the words" cat	E. (s contains "fluffy") \|\| (s contains "cat")
6. "With all of the words" fluffy cat, "Without the words" persian	F. ! s contains "cat"
	G.(s contains "fluffy") && (s contains "cat") && ! (s contains "persian")

4. Write your own Java-like expression for the following:

a. "With all of the words" Alan Turing
b. "At least one of the words" Alan Turing
c. "Without the words" Turing
d. "With the exact phrase" Alan Turing
e. "With all of the words" Alan Turning, "Without the words" Enigma
f. "At least one of the words" Alan Turing, "Without the words" Enigma

5. You can also restrict other things on the advanced search window. For example, you can restrict the language to English. (i) Write your own Java-like expression to express each search. (ii) Then, explain why each search is useful:

a. "With all of the words" Boole mathematician "In the language" German
b. "At least one of the words" Boole Algebra "Date - page updated" last 3 months.
c. "With all of the words" Boole Algebra "Occurrences Appear" in the title.

B. Searching in the Main Window:

Google automatically puts an and between words.
OR means look for one or the other or both. It works like ||.
-word means do not include pages that include that phrase.
Google automatically ignores common words. + means include the following common word in the search. If you typed "World War +I", then the I would be included in the search.
~word means look for synonyms of the word too.
1914..1918 searches for numbers in the range specified.
Google searches are not case sensitive

6. Match the following main page searches to the java phrases.

Main Search Page Phrase	Java-like Phrase
a. fluffy cat	1. s contains "fluffy" \|\| s contains "cat"
b. fluffy OR cat	2. s >=1914 && s<=1918
c. -fluffy cat	3. s contains "fluffy" \|\| s contains "cat" && !! s contains "hair"
d. fluffy -cat	4. s contains "fluffy" && s contains "cat"
e. fluffy OR cat -hair	5. no Java equivalent
f. 1914..1918	6. ! s contains "fluffy" && s contains "cat"
g. ~fluffy	7. s contains "fluffy" && ! s contains "cat"

7. Translate these Advanced Search page searches to the short cuts used on the main search page (-, OR, etc)

a. "With all of the words" Alan Turing
b. "At least one of the words" Alan Turing
c. "Without the words" Turing
d. "With the exact phrase" Alan Turing
e. "With all of the words" Alan Turning, "Without the words" Enigma
f. "At least one of the words" Alan Turing, "Without the words" Enigma

8. How would you write these ranges on the main search page? (use the .. notation)

a. s=>1914 && s<=1934
b. s>1914 && s<1934
c. s>1914 (be creative, more than one right answer)
d. s<1934 (be creative, more than one right answer)

9. Opinion Questions

a. Should Google searches be case sensitive? Java is. Provide an argument in favour of a case sensitive search and one against it before you make your decision.

b. Google searches do not appear to use brackets or a complex Order of Operations like Java does. Why would this be useful? Why do you think the makers of Google chose not to include it.

10. Compare and Contrast Java's Boolean Expressions with those used in Google. Provide at least 6 points of comparison