# teaching machines

## CS 245 Lecture 9 – Complexity

October 1, 2013 by . Filed under cs245, fall 2013, lectures.

### Agenda

• what ?s
• Hunting Dragons with Binary Search
• finish binary search
• What If?
• comparing algorithms
• the tradeoff: ease of development or performance
• I’m More Difficult Than You
• terrain generation

### What If?

Suppose you’ve got the following list of numbers in an array:

1 17 9 3 48 55 53 0 2

You try to find each number’s index using binary search on the unsorted array. Which numbers will you find? Which won’t you find?

### I’m More Difficult Than You

Sort the following problems in terms of their general difficulty:

• cracking a fixed-length password comprised of lowercase letters
• sorting a list of dictionary terms
• finding the maximum in a list
• prepending an element onto the beginning of an array
• finding the average of a list

### Code

#### Spellchecker.java

package lecture0926;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class Spellchecker {
private ArrayList<String> words;

public Spellchecker() {
words = new ArrayList<String>();

try {
Scanner in = new Scanner(new File("/usr/share/dict/words"));
while (in.hasNextLine()) {
String word = in.nextLine();
words.add(word);
}
} catch (FileNotFoundException e) {
}
}

public boolean isLegitimate(String wordInQuestion) {
return smarterIndexOf(wordInQuestion) != -1;
}

private int indexOf(String wordInQuestion) {
for (int i = 0; i < words.size(); ++i) {
if (words.get(i).equals(wordInQuestion)) {
return i;
}
}

return -1;
}

private int smarterIndexOf(String wordInQuestion) {
return smarterIndexOf(wordInQuestion, 0, words.size() - 1);
}

private int smarterIndexOf(String wordInQuestion, int lo, int hi) {

// Have we reached the impossible bounds? If so, no hay palabra.
if (lo > hi) {
return -1;
}

int middle = (lo + hi) / 2;
int order = wordInQuestion.compareTo(words.get(middle).toLowerCase());

System.out.println(words.get(middle));

// order < 0 means wordInQuestion < middle word
// order == 0 means wordInQuestion is middle word
// order > 0 means wordInQuestion > middle word

if (order == 0) {
return middle;
} else if (order < 0) {
// m - 1 is the new h
return smarterIndexOf(wordInQuestion, lo, middle - 1);
} else {
// m + 1 is the new l
return smarterIndexOf(wordInQuestion, middle + 1, hi);
}

}

public static void main(String[] args) {
Spellchecker checker = new Spellchecker();
System.out.println(checker.isLegitimate("foobag"));
}
}

### Haiku

I lost my car keys
Found them while sorting my stuff
No searching needed