Algorithms

Reading is posted on Canvas.

An algorithm is recipe for performing a procedure. Algorithms, to be practical, must exhibit these characteristics.

• unambiguous: The instructions for an algorithm must be precise and must be comprehensible to its audience.
• finite lifetime: An algorithm must halt with a result after a finite number of steps.
• finite memory: An algorithm can only use a finite amount of memory.

Searching A List You can search a list for an item by iterating through the list, and reporting you found it if you find it, and by reporting it's not there if you get to the end of the list without finding it. The time it takes to do this is at worst proportional to the length of the list. We say this algorithm is \(O(n)\).

Binary Search This is a means of searching for an item in a sorted list. I am going to describe this algorithm and you are going to use it to write a program that searches a scrabble dictionary for a word that is specified as argv[1]. You may hard-code the filename scrabble.txt in your prgram. Here is the idea.

• Go to the midpoint of the list
• Check if the word you seek precedes the word at the midpoint alphabetically. If it does, you can eliminate the second half of the list as a search space.
• Otherwise, the word, if it is in the list is in the second half of the list.
• Repeat this procedure. Either you will find the word, or your search space will be empty, in which case, the word is not present in the list.

Each iteration cuts the size of the search field in half. It is not hard to see that, given a number \(n\), if divide it by 2 \(\lceil \log_2(n)\rceil\) times, that it will be reduced to 1 or 0. This algorithm terminates after that many iterations. Hence, this is a \(O(\log(n))\) time algorithm. Doubling the size of the list only increases the work by one iteration.

Pairings These were assigned randomly by the program mateFools.py.