Lab 5: Word Games
Bard College – Computer Science – Data Structures

In this lab we will write programs to play word games with the help of a file of words and our new dear friend, binary search. 

Warm Up 

Compare the time it takes to sort words using insertion, selection and merge sort. The file typically lives in /usr/share/dict/words on Unix, but it is also posted to Google classroom. 

I’d suggest using bash’s time to see how long each sort takes (IntelliJ fans can use StopWatch from algs4):

$ time java -cp algs4.jar edu.princeton.cs.algs4.Selection < /usr/share/dict/words > /dev/null 

Report how long each sorting algorithm takes to sort the words file on your computer.

Spell Checker: Two Ways

Our first program will act as a spell checker: it checks to see if a word exists in the dictionary.

import edu.princeton.cs.algs4.*;

public class SpellChecker{
    private String[] words;

    public SpellChecker(String dictFile) {
        words = In.readStrings(dictFile);
    }

    public SpellChecker() {
        this("words");
    }

    public boolean check(String word){
        return scheck(word); // or bcheck(word, 0, words.length-1);
     }
         
    private boolean scheck(String word){
        return false;
     }
    
    private boolean bcheck(String word, int low, int high){
        return false;
    }

    public static void main(String[] args){
        String[] testWords = {"bear", "jackalope", "liger", "zebra"};
        SpellChecker sp = new SpellChecker();
        if (args.length > 0) testWords = args;
        for (String word: testWords){
            if (!sp.check(word)){
                StdOut.println(word);
            }
        }
    }