Assignment 9

Goals: Practice designing loops, using and mutating the ArrayList

Instructions

The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit.

Make sure you follow the style guidelines for code indentation.

You will submit this assignment by the deadline using the Web-CAT submission system.

With each homework you will also submit your log file named pairxxx.txt where you replace xxx with your pair number.

On top of every file you submit you will have the names of both partners, and the pair number.

The .txt file will be the log of your work on this assignment. Each log entry will have data and time, who was present (one or both of the partners) and a short comment decribing what you were working on.

Submission Details:

• Make sure the the names of all classes and interfaces in all three problems are different.

• Make sure every file with name Xyyy.java contains as the first class or interface the definition of class Xyyy or interface Xyyy.

• Make sure that the three classes with tests for the three problems are named ExamplesCode, ExamplesInsertSort, and ExamplesEliza (and, optionally ExamplesInsertionSort.

Due Date: Friday, March 22th, 6:00 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 ArrArrayListayList. 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 ExamplesInsertSort 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 a new 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 ExamplesIsertSort class on lists of Integerss and Strings.

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 with the user’s question as its argument.

  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:

/** A random number generator */

Random rand = new Random();

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.