Assignment 3: Designing methods for Complex Data, Practice with Lists and Accumulators
Goals: Practice working with lists. Learn to design methods and practice designing with accumulators.
3.1 Instructions
the names of classes,
the names and types of the fields within classes,
the names, types and order of the arguments to the constructor,
the names, types and order of arguments to methods, or
filenames,
Make sure you follow the style guidelines that handin enforces. For now the most important ones are: using spaces instead of tabs, indenting by 2 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 handin submission system. You may submit as many times as you wish. Be aware of the fact that close to the deadline the system may have a long queue of submissions which means it takes longer for your code to be submitted - so try to finish early.
As always, you may only use techniques that have been covered in lectures so far in your solutions.
You will submit this assignment in two parts:
Part 1: Submit your data definitions, examples and tests for the methods. You should include stubs for the methods themselves (remember not to have your stubs return nulls). Although we would not expect the tests to pass yet, your code should compile. This will be partly graded on the completeness of your test cases. You should add examples for the cases you want to test. Please add a comment for each test case describing what you are testing.
After part 1 of Assignment 3, there is a self-eval assignment. This will give you a chance to review your own work. This will also help the TAs with grading because it will ask you to tag lines of code that we will be looking for (in this case, tests).
The self-eval will show up in handins after the deadline for part 1 has passed: at 10pm Monday night. Then you will have 24 hours to complete it.
Important: you will no longer be able to submit part 1 after clicking on the self-eval. Make sure you have submitted your final version of the assignment before doing the self-eval!
Part 2: Submit everything from Part 1 but this time include complete implementations for the methods (including any helpers needed).
Part 1: Monday, September 23rd, 9:00 pm (with self-eval due Tues by 10pm)
Part 2: Thursday, September 26th, 9: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.
Problems 18.1 - 18.4 on page 225
Problem 18.5 on page 229
Problem 18.6 on page 234
Problem 19.4 on page 263
Problem 1: Understanding the String class
Give sufficient examples of data, and sufficient tests, to test your methods thoroughly.
If you find yourself wanting to use a field-of-field or getters, stop. Fill out the template for each method, and figure out another design.
Think carefully about how to use dynamic dispatch, and where to define methods, to keep your code as simple and clean as possible.
Note: The following method defined for the class String may be useful:
// does this String come before the given String lexicographically? // produce value < 0 --- if this String comes before that String // produce value zero --- if this String is the same as that String // produce value > 0 --- if this String comes after that String int compareTo(String that)
When referring to strings, this is known as a “case-insensitive” sort, since when it examines two strings, it converts everything to lowercase (or uppercase —
would it make any difference?) before comparing them, so the comparison can’t use— or be sensitive to— differences in casing. Design the method sort that produces a new list, sorted in alphabetical order, treating all Strings as if they were given in all lowercase.Note: The String class defines the method toLowerCase that produces a String just like the one that invoked the method, but with all uppercase letters converted to lowercase.
Design the method isSorted that determines whether this list is sorted in alphabetical order, in a case-insensitive way.
Hint: You will likely need a helper method. You may want to review the accumulator style functions we have seen in DrRacket.
Design the method:
ILoString subList(int start,int end) ILoString sublist(int start,int end)
for ILoString. When invoked, it returns a list of Strings from this list in the same order, starting from the given start position and ending at the given end position (including the two positions). Positions in the list start at 0 (i.e. the first String in the list is at index 0). For example, when called as list.sublist(1,3) it will return a list containing the second, third and fourth strings in that order. If the range goes partly beyond the list in either direction, it should choose the appropriate indices that lie within that range (e.g. a range of -2 to 4 should return Strings in indices 0 to 4, and so on).
Design the method interleave that takes this list of Strings and a given list of Strings, and produces a list where the first, third, fifth... elements are from this list, and the second, fourth, sixth... elements are from the given list. Any “leftover” elements (when one list is longer than the other) should just be left at the end.
Design the method merge that takes this sorted list of Strings and a given sorted list of Strings, and produces a sorted list of Strings that contains all items in both original lists, including duplicates, treating all Strings as if they were given in all lowercase. You should not use sort for this. (This is not the same computation as for interleave, but the two methods are similar. Can you construct an example of two lists such that interleaving them and merging them produce different results? Can you construct another example where the two results are the same?)
Design the method reverse that produces a new list of Strings containing the same elements as this list of Strings, but in reverse order.
Hint: The cleanest solution to this problem uses a helper method, in a style seen already in this problem.
Design the method isDoubledList that determines if this list contains pairs of identical strings, that is, the first and second strings are the same, the third and fourth are the same, the fifth and sixth are the same, etc.
Hint: Think carefully about how to test this method.
This isn’t the same as the typical definition of palindromes, which asks whether a single string contains the same letters when read in either order.
Design the method isPalindromeList that determines whether this list contains the same words reading the list in either order.Hint: Several of the methods defined above will be helpful in your solution.
Submit your work in the completed Strings.java file.
WARNING: Be extra careful not to name your file "String.java" – or else Java will think that you’re trying to redefine the built-in String class, and everything will break in creatively bizarre ways.