CSSE 220 – Object-Oriented Software Development

Homework 30

More optional practice problems to do before the exam  (there were others in HW 25 and HW 29)

• One way to compute the nth power of x is to multiply x by itself n times.  This is clearly O(n).  We can improve on this by writing a recursive method based on the fact that xn = (x^n/2)². Write and test this method and give its big-oh running time. Note that the cases for even and odd values of n are slightly different.
• Suppose we know that when the following code is called, we know that c is not null, none of the collections in c is null, and str is not null.
  public static int count(Collection<Collection<String>> c, String str)
  Write the code for this method, which should return the number of times that str occurs in c. Here is some code that can be used to test your method.

  public static void main(String[] args) {
        Collection> a = new ArrayList>();
        
        String[][] arrays = {{"abc", "def", "ghi"}, 
                             {"xyz", "uvw", "abc", "abc"}, 
                             {"a", "ab", "abc", "xyz", "abc"}};
        
        for (String[] sArray : arrays){
           Collection a1 = new ArrayList();
           for (String s: sArray)
              a1.add(s);
           a.add(a1);
        }
        System.out.println(count(a, "abc"));
     }
  }
  			

• Write a Comparator class that compares two Strings in the following way:  Shorter strings are less than longer strings.  If two strings have the same length, the normal ASCII ordering determines which is less.  Use this comparator in a call to Arrays.sort to sort an array of strings based on this method of comparison.
• Write a method that removes every other element from a java.util.List.  Write the method in such a way that if the List is a LinkedList, the method will use a constant amount of extra space (independent of the length of the list) and will run in O(N) time.
• Add a reverse() method to your LinkedList class.  It reverses the order of the elements in the LinkedList class.  Challenge:  Write this method so that it does not refer to any element fields and does not create any new ListNodes.  This is problem P15.3 in Big Java.
• R14.12 (not for the faihnt of heart!)
• R14.13
• R14.14
• P14.8
• R15.12
• P15.7
• P15.13
• R16.6
• P16.1
• P16.2

Turn-in Instructions

There is nothing to turn in.  You should look at these problems, and try to do the things that you are unsure about.