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 sorts. The file typically lives in /usr/share/dict/words on Unix, but it is also posted on repl.it.
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.Merge < words > /dev/null
Report how long each sorting algorithm takes to sort the words file.
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.*;
publicclassSpellChecker{
private String[] words;
publicSpellChecker(String dictFile){
words = (new In(dictFile)).readAllStrings();
}
publicSpellChecker(){
this("words");
}
publicbooleancheck(String word){
return scheck(word); // or bcheck(word, 0, words.length-1);
}
privatebooleanscheck(String word){
returnfalse;
}
privatebooleanbcheck(String word, int low, int high){
Warm Up
⪢ time java -cp algs4.jar edu.princeton.cs.algs4.Merge < words > /dev/nullSpell Checker: Two Ways
import edu.princeton.cs.algs4.*;
public class SpellChecker{ private String[] words;
public SpellChecker(String dictFile) { words = (new In(dictFile)).readAllStrings(); }
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); } } }