1. Programming Practice - Markov Chain Algorithm in JavaJava classes of Markov chain algorithmPrefix ClassChain ClassMarkov ClassString Tokenizer Class1. 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 records4. 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
View Full Document
Unlocking...