Assignment 9

Goals: Practice designing loops, using and mutating the ArrayList

Instructions

The names of the classes must be exactly the same as specified. The same is the case for the names and types of the fields within the class, as well as the order in which they are defined and listed as the constructor arguments. This allows us to design our own Examples class that tests your program.

Make sure you follow the style guidelines that WebCAT enforces. For now the most important ones are: using spaces instead of tabs, indenting by 4 characters, following the naming conventions (data type names start with a capital letter, names of fields and methods start with a lower case letter), and having spaces before curly braces.

You will submit this assignment by the deadline using the Web-CAT submission system. You may submit as many times as you wish. Be aware of the fact that close to the deadline the WebCAT system may slow down to handle many submissions - so try to finish early.

With each homework you will also submit your log file named pair-user1-user2.txt where you replace user1 and user2 with the usernames of the two partners.

On top of both files you will have five lines of comments as follows:

(In the text file you do not need the two slashes)

There will be a separate submission for each problem - it makes it easier to grade each problem, and to provide you with the feedback for each problem wou work on.

The two submissions will be organized as follows:

• Submission HW9P1: The log file and the solution to the Secret Code problem in one .zip file

• Submission HW9P2: The file ExamplesInsertionSort.java that contains the implementation of the insertion sort and the necessary tests in one file

• Submission HW9P3: The files Interactions.java and all other files that contain the solution to the Eliza problem in one .zip file

Due Date: Wednesday, March 19th, 11:59 pm.

Practice Problems

Work out these problems on your own. Save them in an electronic portfolio, so you can show them to your instructor, review them before the exam, use them as a reference when working on the homework assignments.

• Review the loop problems from the lecture on loops (posted in te Lecture Notes).

• Design the method that reverses the items in the given ArrayList.

• Design the method that swaps the each consecutive pair of items in an ArrayList, i.e., swaps the first and second, swaps the third and fourth, and if these is an odd number of items, leaves that last one as is.

• Design the method that removes the smallest item from the given ArrayList. The method also consumes a Comparator that is used to compare the items and determine which one is the smallest.

Problem 1: Secret Code

Create a project for your Problem 1.

You goal is to write a program that will encode and decode secret messages using a simple mapping of letters to a permutation of all letters. So if our alphabet had only five letters (a, b, c, d, and e) we could choose to encode them as (b, e, a, c, and d). Then the received message abe edc would be decoded as cab bed and the message bad ace would be sent encoded as ebc bad.

Download the file PermutationCode.java. It is a skeleton for your program. Your job is to design the three methods for which the purpose statements and the headers are already provided. Of course, you may need additional helper methods, and, of course, you will still follow the design recipe.

The class PermutationCode contains the key for the encoding and decoding of the messages, as well as the methods that perform these tasks. There are two constructors. One allows you to specify explicitly what will be your encoding permutation. This allows you to test your methods that encode and decode the messages. The second constructor generates a new encoding permutation that may be given to the parties that wish to communicate in secret.

• Design the method decode that will consume the encoded message and use the ArrayList code to decipher the message, one character at a time. Look up methods you may use with the data of the type String in the Java documentation.

• Design the method encode that will consume the message we wish to encode and use the ArrayList code to produce the encoded message, — again — one character at a time.

• Design the method initEncoder that produces a random permutation of the 26 letters of the alphabet and returns it as an ArrayList of Characters.

  Hint: Make a copy of the alphabet list, then remove one character at random and add it to the encoder list, until all letters have been consumed.

Black Box Tests

The WebCAT may invoke these three methods in the PermutationCode class to test your work. It will make its own examples of data that will be used in the tests.

Problem 2 Insertion Sort

Create a project for your Problem 2.

We have seen the recursively defined insertion sort algorithm both in the first semester and also recently, using the recursively defined lists in Java. The main idea behind the insertion sort was that each new item has been inserted into the already sorted list.

We can modify this as follows:

• Design the method sortedInsert that consumes an item of the type T, a sorted ArrayList, and a Comparator that has been used to define the sorted order for the given list. (Make sure the arguments are given in the order described here.)

  It modifies the given ArrayList by adding the given item to the ArrayList, preserving the ordering.

  Define this method directly in the ExamplesInsertionSort class, where you will include the tests for this method as well.

  Note: Be careful to make sure it works correctly when the given ArrayList is empty, and when the item is inserted at the and of the ArrayList.

• Design the method insertSort that consumes an arbitrary (unsorted) ArrayList and a Comparator (in the given order) and produces a new sorted ArrayList as follows:

  It starts with an empty sorted list and inserts into it one by one all the elements of the given ArrayList.

  Note: It is a bit more difficult to define the insertion sort algorithm so that it mutates the existing ArrayList in place.

• Design an in-place insertionSort method. Name it insertionSort and define it in the ExamplesInsertionSort class. You will get the credit only if the design is neat and clearly organized.

  Note: In-place sort mutates the given ArrayList. So, the method does not return any vlue (i.e. return type is void), but when the method finishes execution the original ArrayList has been mutated, so it is in sorted order.

Test your code on ArrayLists with elements of the type String (sorted lexicographically) and with elements of the type Integer sorted by their magnitude. You already have the necessary variants of Comparators from the binary search problem on the previous assignment.

Black Box Tests

The WebCAT will test your methods sortedInsert and insertSort defined in your ExamplesInsertionSort class on lists of Integerss and Strings.

Additional help: The Lab 9: Fall 2013 has a detailed explanation of the insertion sort with illustrations.

Problem 3 Eliza

Create a project with for your Problem 3.

Our goal is to train our computer to be a mock psychiatrist, carrying on a conversation with a patient. The patient (the user) asks a series of questions. The computer-psychiatrist replies to each question as follows. If the question starts with one of the following (key)words: Why, Who, How, Where, When, and What, the computer selects one of the three (or more) possible answers appropriate for that question.

If the first word is none of these words the computer replies I do not know or Why do you want to know? – a generic answer that does not depend on what was the question.

The file Interactions.java contains the code that will run your game, once you design it.

• Start by designing the class Reply that holds a keyword for a question, and an ArrayList of answers to a the question that starts with this keyword. The class diagram is:

  +---------------------------+

  | Reply                     |

  +---------------------------+

  | String keyword            |

  | ArrayList<String> answers |

  +---------------------------+

• Design the method randomAnswer for the class Reply that produces one of the possible answers each time it is invoked.

  Make sure it works fine even if you add new answers to your database later. In your examples, make at least three answers for each keyword.

• Design the class Eliza that contains an ArrayList of Replys. You should include a method that will initialize all answers, and invoke this method in the constructor, so that an instance of Eliza will be able to provide answers to the Interactions class.

• In the class Eliza design the helper method
  firstWord
  that consumes a String and produces the first word in the String. This should help you to find the keyword for the question the user has asked.

• The following code in the Interactions class reads the next input line from the user.

  System.out.println("Type in a question: ");

  s = input.nextLine();

  You will need to find out what was the first word in the patient’s question and convert it to a keyword that will match the keywords in the Reply objects. Look up the documentation for the String class (and we gently hint that the methods trim, toLowerCase, and startsWith may be relevant).

  Make sure your program works if the user uses all uppercase letters, all lower case letter, mixes them up, etc.

• Finish the work by designing any other methods you may need so that the program generates a random answer to every legitimate question.

  Hint: The code for the class Interactions include the following segment:

  // mock code: echo every line

  System.out.println(s);   // REPLACE THIS WITH YOUR CODE !!!

  // that finds out the reply to the question s

  // and prints the reply

  So replace the s in the argument to println with the call to a method that consumes s and produces the desired answer.

Black Box Tests

There will be no black box tests for this problem.

Instead, include in your submission the output of running the program with at least ten questions asked by the user. Save it as Transcript.txt.

Random Numbers - A Brief Note

For two of the problems you will need to generate random integers. You may have done so in your game earlier in the semester.

The code:

produces an instance of a new Random a random number generator defined in Java libaries. The class defines a method rand.nextInt(int n) that returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), provided that n >= 0.

Use this method to produce any desired random values.

Use the checkOneOf and checkRange methods to test your outcomes.