1 Programming Practice Markov Chain Algorithm in Java Java classes of Markov chain algorithm Class Prefix Class Chain Class Markov Prefix Class class Prefix public Vector pref NPREF adjacent words from input static final int MULTIPLIER 31 for hashCode Prefix constructor duplicate existing prefix Prefix Prefix p pref Vector p pref clone Prefix constructor n copies of str Prefix int n String str pref new Vector for int i 0 i n i pref addElement str Prefix hashCode generate hash from all prefix words public int hashCode int h 0 for int i 0 i pref size i h MULTIPLIER h pref elementAt i hashCode return h Prefix equals compare two prefixes for equal words public boolean equals Object o Prefix p Prefix o for int i 0 i pref size i if pref elementAt i equals p pref elementAt i return false return true Chain Class class Chain static final int NPREF 2 size of prefix static final String NONWORD n word that can t appear Hashtable statetab new Hashtable key Prefix value suffix Vector Prefix prefix new Prefix NPREF NONWORD initial prefix Random rand new Random Chain build build State table from input stream void build InputStream in throws IOException StreamTokenizer st new StreamTokenizer in st resetSyntax remove default rules st wordChars 0 Character MAX VALUE turn on all chars st whitespaceChars 0 except up to blank while st nextToken st TT EOF add st sval add NONWORD Chain add add word to suffix list update prefix void add String word Vector suf Vector statetab get prefix if suf null suf new Vector statetab put new Prefix prefix suf suf addElement word prefix pref removeElementAt 0 prefix pref addElement word Chain generate generate output words void generate int nwords prefix new Prefix NPREF NONWORD for int i 0 i nwords i Vector s Vector statetab get prefix if s null System err println Markov internal error no state System exit 1 int r Math abs rand nextInt s size String suf String s elementAt r if suf equals NONWORD break System out println suf prefix pref removeElementAt 0 prefix pref addElement suf Markov Class class Markov static final int MAXGEN 10000 maximum words generated public static void main String args throws IOException Chain chain new Chain int nwords MAXGEN chain build System in chain generate nwords 2 Reading Writing in Java Reading and Writing Examples i The following code illustrates the use of classes Input Stream Reader Buffered Reader and the method readLine public static void main String args throws IOException We construct an input stream is It allows us to read input text line by line InputStreamReader converter new InputStreamReader System in BufferedReader is new BufferedReader converter We prompt the user for N strings We store input strings inside a String array B String B new String N System out println Enter input strings one string per line for int i 0 i N i B i is readLine System out println ii This is a modification of Markov chain algorithm The program takes input from the file alice30 txt and it sends the output to the file output txt class MarkovModifiedInOut static final int MAXGEN 10000 maximum words generated public static void main String args throws IOException BufferedReader in new BufferedReader new FileReader alice30 txt PrintWriter out new PrintWriter new FileWriter output txt Chain chain new Chain int nwords MAXGEN chain build in in close chain generate nwords out out close Modifications inside Chain class void build BufferedReader in throws IOException void generate int nwords PrintWriter out prefix new Prefix NPREF NONWORD for int i 0 i nwords i out println suf String Tokenizer Class iii This is yet another modification of Markov chain algorithm We keep the changes done in example ii and now we substitute the Stream Tokenizer object of the method build by an object of the String Tokenizer class Modifications inside build method of Chain class void build BufferedReader in throws IOException String s StringTokenizer st while s in readLine null st new StringTokenizer s while st hasMoreTokens add st nextToken add NONWORD 3 Programming Practice Debugging programs Debugging an overview To reduce debugging time stick to the following principles i Good design ii Good style iii Boundary conditions tests iv Assertions v Sanity checks vi Defensive programming vii Well designed interfaces viii Limited global data ix Checking tools When a hard bug occurs i Make the bug reproducible ii Divide and conquer iii Study the numerology of failures iv Display output to localize your search v Write self checking code vi Write a log file vii Draw a picture viii Use tools ix Keep records 4 Programming Practice Examples of tests based on proofs Loop Invariants and Loop Testing Loop Syntax while condition B do P end while Loop Invariant Q is a condition which we design in order to prove loop correctness Once the invariant Q is ready we need to verify the following statements Invariant Q holds after initializing loop variables If Q holds before execution of P then it holds after execution of P Execution of the loop terminates It is possible to deduce post condition from the fact that invariant Q holds and that the loop terminated its execution With the help of the following two examples we will discuss how one may use loop invariants to design tests of loops Example 1 Product int x int y pre condition x y 0 post condition j x y int i j i 0 j 0 while i x do j j y i i 1 end while return j end function Product Loop invariant Q j i y Example 2 Euclid s Algorithm GCD int a int b precondition a b 0 a b postcondition i gcd a b int i j i a j b while j 0 do compute i q j r 0 r j i j j r end while return i end function GCD Loop invariant Q gcd i j gcd a b Problem 1 Prepare C code for the following test of Example 1 Design an integer valued function with two integer arguments which implements the loop of Example 1 Design a Boolean valued function Q which checks whether the invariant holds In the implementation of Q perform direct calculation of the product Prepare C code for testing your implementation of the loop Your code should verify whether the invariant holds after the initialization of variables and after every execution of the update It should prompt the user for two input integers and report the result of the test Problem 2 Prepare C code for the following test of Euclid s algorithm Design an integer valued function with two integer arguments implementing the loop of Example 2 Design a Boolean valued function Q which checks whether the invariant holds In the