CS 245 Lecture 9 – Complexity
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
Found them while sorting my stuff
No searching needed