Week 8, Friday: Searching

analysis of algorithms

How many steps for each of the following? And what happens to the number of steps when n doubles to 2n? Try to classify each of the following as one of these: O(logN), O(N), O(NlogN), O(N*N).

#############################################
# 1
n = int(raw_input("n: "))
for i in range(n):
  print i
#############################################
# 2
n = int(raw_input("n: "))
for i in range(100):
  print i*n
#############################################
# 3
n = int(raw_input("n: "))
for i in range(n):
  print i
for j in range(n):
  print j
#############################################
# 4
n = int(raw_input("n: "))
for i in range(n):
  for j in range(n):
    print i, j
#############################################
# 5
n = int(raw_input("n: "))
for i in range(n):
  for j in range(i,n):
    print i, j
#############################################
# 6
n = int(raw_input("n: "))
for i in range(n):
  for j in range(10):
    print i, j
#############################################
# 7
n = int(raw_input("n: "))
while n > 1:
  print n
  n = n/2
#############################################
# 8
L = [1,2,5,7,13,21,24,25,26,33,34,38,50,57,58,63]
n = len(L)
mid = n/2
print L[mid]
#############################################
# 9
n = int(raw_input("n: "))
for i in range(n):
  k = n
  while k > 1:
    print i, k
    k = k/2
#############################################

using our searches.py file

Write a program called lookup.py that simply asks for a word, and then tries to find the word in the system word list (/usr/share/dict/words). Here is an example:

$ python lookup.py 
word: hello
Found
word: pickles
Found
word: sdkjflkdjf
NOT Found
word:

In your program, include from searches import * to import our two search functions. If we are searching through the system word list, which is in alphabetical order, which search function should we use?

code timing

Another way to compare algorithms is by simply timing two algorithms on the same computer with the same data. For a spell-checking program, searching about 3000 times, through the system word list (99171 words), my linear search program took about 13 seconds to run, while the same program using binary search took only 4 seconds. What would happen to each if we doubled the size of the list we are searching through?

Here is an example of using the python time() function to see how long a block of code takes to run:

>>> from time import time
>>> t1 = time()
>>> x = 0
>>> for i in range(1000000):
...    if i%2 == 0:
...      x += 1
...    else:
...      x += 2
... 
>>> t2 = time()
>>> total = t2 - t1
>>> print(total)
9.0005819798

Ben's musicAlgo.com site

One of our students, Ben Schreiber, made a website to help students understand and learn various searching and sorting algorithms. His website includes a summary of binary search, an analysis of binary search, and a coding example with a song to help you remember the algorithm. If you are struggling to understand how binary search works (or the sorting algorithms we learn next week), check out Ben's musicAlgo.com site