copyright 2012 Felleisen, Proulx, et. al.

CS 2510 Spring 2012:Assignment 10 - Loops

Practice Problems

Work out the following exercises. Do not add it to your assignment submission, though you should keep it in your electronic portfolio in your own svn repository.

Problem: Using ArrayList

1. Finish the SelectionSort problem from Lab 10.

2. In the Algorithms class design the method evenItems that consumes an ArrayList and produces a new one that contains only the items that were at the even-numbered locations.

3. In the Algorithms class design the method lower that consumes an ArrayList, a Comparator, and an object of the type T and produces a new one ArrayList that contains only those items from the original one that come before the given one according to the ordering defined by the given Comparator.

4. In the Algorithms class design the method upper that consumes an ArrayList, a Comparator, and an object of the type T and produces a new one ArrayList that contains only those items from the original one that come after the given one according to the ordering defined by the given Comparator.

Pair Programming Assignment

These problems should be checked into your pair's SVN repository by the due date.

Project naming requirements

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.

Every file you submit must have a header that identifies you and the problem it solves. So, for the first problem the header should look like this:

// Assignment 10 Problem 1
// Partner Name1
// partner1username
// Partner Name2
// partner2username
// 27 March 2012

Problem 1 Secret Code

Create a project with the name HW09Problem1.

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 fill 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.

1. Design the method encode 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.

2. Design the method decode 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.

3. 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.

Problem 2 Insertion Sort

Create a project with the name HW09Problem2.

1. Design the method sortedInsert that consumes a sorted ArrayList a Comparator that has been used to define the sorted order for the given list, and an item of the type T. It modifies the given ArrayList by adding the given item to the ArrayList, preserving the ordering.

   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.

2. Design the method insertionSort that consumes an arbitrary (unsorted) ArrayList and a Comparator 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.

3. Design an in-place insertionSort method. You will get the credit only if the design is neat and clearly organized.

4. Test your code on ArrayLists with elements of the type String and with elements of the type Integer.

Problem 3 Eliza

Create a project with the name HW09Problem3.

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? or something like that.

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

1. 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.

2. 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. Make at least three answers to each question

3. Design the class Eliza that contains an ArrayList of Replys.

4. In the class Eliza design the helper method firstWord that consumes a String and produces the first word in the String. The following code reads the next input line from the user. You will need to find out what was the first word in the patient's question. Look up the documentation for the String class (and we gently hint that the methods trim, toLowerCase, and startsWith may be relevant).

   System.out.println("Type in a question: ");
   s = input.nextLine();
   

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