Loading...

​​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);

​​            }

​​        }

​​    }