CSC 171
Homework 6
Recursion without polymorphism: lists, Strings, whole numbers, input streams

Assigned Apr 19, due May 1

For each method, be sure to follow the design recipe for methods.

For each animation, be sure to follow the design recipe for animations.

Be sure to choose meaningful names for methods and parameters, and watch for opportunities to re-use methods you, I, or Dr. Stemkoski have already written.

Also turn in a log of how many errors of different kinds you encountered in the assignment, with brief comments describing each one ("mismatched parentheses" is self-explanatory, but more complex errors might need more description). You may do this using the PSP forms, or simply by keeping track in a text file or on paper and turning it in.

How to turn this in

You are encouraged to do this in teams of two students; turn in one copy of the project with both names on it (in the README file or in comments in the Java source files). Even if you do the assignment without a partner, make sure your name is on it.

    Lists

    I encourage you to copy the type-parameterized List, AbstractList, Empty, and NEL classes from the lecture code posted on Moodle (e.g. April 15 version 2), and use these classes without alteration.

  1. Choose one of the IntList methods from homework 5, and re-implement it in a separate class as a static method that takes in an explicit parameter of type List<Integer>. (You can recycle the test cases, except that instead of calling something like oneTwoThree.convertReversed() you'll call HW6_1.convertReversed(oneTwoThree).)

  2. Re-implement the sort method from lecture (and its helper, insertInOrder) in a separate class as a static method with an explicit List<Integer> parameter. (Again, you can recycle the test cases.)

  3. Extra credit: write a static method subsets that takes in a List<Integer> and returns a List<List<Integer>>, representing all possible subsets of the numbers in the original list, once each. For example, if oneTwoThree represented the list [1, 2, 3], then subsets(oneTwoThree) might produce

    [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
    (Your method may produce results in a different order, as long as it produces the right subsets. This is the order that my definition produced, so you might want to try this approach: all the lists that don't contain 1, followed by all the lists that do contain 1.) You may assume that all the numbers in the input list are distinct.

  4. Extra credit: write a static method scramble that takes in a List<Integer> and returns a List<List<Integer>> representing all possible orderings of the elements in the original list, once each, for example, scramble(oneTwoThree) might produce

    [[1, 2, 3], [2, 1, 3], [1, 3, 2], [3, 1, 2], [2, 3, 1], [3, 2, 1]]
    Again, you may assume that all the numbers in the input list are distinct.

    Hint: This one is harder than subsets, probably requiring several helper methods.

  5. Strings

  6. Write a static method countVowels that takes in a String and counts the vowels (any of the letters "a", "e", "i", "o", or "u") it contains, by looking at each character in turn. You may assume there are no capital letters (or, if you prefer, you may treat upper- and lower-case letters the same).

  7. Write a static method replaceChar that takes in a one-character String and two (possibly longer) Strings: it replaces the first character with the second string wherever it appears in the third string. For example,

    t.checkExpect(replaceChar("r", "fnord", "reference librarian"),
                  "fnordefefnordence libfnordafnordian");

    Hint: Use the usual String-processing template on the third String; don't take apart the other two.

  8. Whole numbers

  9. Write a static method countDown that takes in an int and produces a list of the integers from it down to 0. For example, countDown(4) would produce [4, 3, 2, 1, 0]. What would be an appropriate right answer if the input is negative?

  10. Input streams

  11. Write a static method addUntilNeg that reads in a sequence of integers from an input stream and adds them all together. The input is terminated by a negative number, which should not be included in the sum.

  12. Putting it all together

  13. Write a static method countLongLines that takes in an int and an input source (represented as a Scanner), then reads a sequence of lines from the input stream and counts how many of the lines have more than the specified number of words on them. (A "word" can be defined as anything between blocks of white space.) For example, countLongLines(3,new Scanner(System.in)) would count how many of the lines in the input have 4 or more words on them.

    Hint: It may help to first write a static words method that takes in a String and returns a list of words in it.

  14. Extra credit: write a static method pigLatin that takes in a String and converts it to "Pig Latin": for each word, if it starts with a vowel, add "way" to the end of the word, and if it starts with a consonant, move that consonant to the end of the word and add "ay". You may assume for simplicity that there are no upper-case letters, numbers, or punctuation. For example,

    t.checkExpect(pigLatin("hi boys and girls"), "ihay oysbay andway irlsgay");

Grading standards

Error log:       /50
(I'm not grading on how many or how few errors you encountered, only on whether you recorded them adequately.)

Programming: To save time and get you feedback more quickly, we won't grade all of the problems, but a selection of them. Each animation requires writing a class with two or more methods; in some cases you'll also need to write a new class to be the model.

General skills:

Following directions /10
Writing contracts from word problems /10
Choosing test cases /10
Choosing names; readability /10
Coding /10
Code re-use and function composition /10

Last modified:
Stephen Bloch / sbloch@adelphi.edu