teaching machines

CS 245 Lecture 9 – Complexity

October 1, 2013 by Chris Johnson. 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?

1 17 9 3 48 55 53 0 2

I’m More Difficult Than You

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