Some Extra Review Problems for Prelim II

CS211 - Fall 2000

Several students have requested additional problems to review before the exam. These are problems that have been used in some of the recitation sections.

1. Problem 5.3 in the text. This problem asks what you can conclude if you know that two functions are both = O(F(n)). Here are my answers:

 a) True (easy proof using def of big-O)
 b) True (another easy proof)
 c) False (big-O gives an upper bound; T2(n) could be equal to 1)
 d) False (big-O gives only an upper bound)

2. Problem 5.5 in the text. Comparing algorithms with runtimes 150 n log n and n^2. My answers: 

 a) First one is better for large n.
 b) Second is better for small n.
 c) We have no information on average running time.
 d) For n sufficiently large, the first algorithm has to be faster.

3. Problem 5.6 in the text. Big-O bounds for typical arithmetic problems (add, divide, multiply). This is a good problem to think about.

4. Problems 5.10 and 5.11 ask you to determine the relation between problem size and runtime for various big-O bounds.

5. Problem 5.13 is an order-by-growth-rate problem. This type of problem often appears on exams.

6. Implement a double-ended queue. Operations are addFront, addBack, getFront, getBack, removeFront, removeBack, and isEmpty. The get- versions get the item without removing it. The remove- versions remove the item without retrieving it. This matches the text's definition of a double-ended queue. What is the runtime for each operation?

This is easy to implement using the LinkedList class.

7. One nice question for discussion is the problem of finding the smallest k items in an array of n integers. To simplify the definition of "k smallest items", we assume that there are no duplicates. Here are several possible strategies: 

  1. find the smallest item and remove it; do this k times 
  2. sort the list; report the first k items 
  3. build a min heap out of all the items; use deleteMin k times 
  4. build a max heap of size k; check each item, changing the heap only if the new item is smaller than the largest item in the heap 
  5. use linear time selection to find the k-th item (call it x); run through the array once, printing all items less or equal to x

We haven't talked about selection yet, so you won't know how to do the last one using linear-time selection, but it's possible (using QuickSort partitioning).

The running times for these strategies are:

 a) O(kn)
 b) O(k + n log n) or O(n log n)
 c) O(n + k log n)
 d) O(k + n log k) or O(n log k)
 e) O(n)

8. A number of students appear to be confused about the use of Comparable and Comparator. Here are some simple example problems that use these concepts. You are given an array word[] of Strings.

a) Sort the array alphabetically. 

java.util.Arrays.sort(word);

This code works because String is of type Comparable (i.e., it implements Comparable and has a compareTo() method). The order defined by compareTo is regarded as the "natural ordering" for that class. For Strings, the natural ordering is case-sensitive.

b) Sort the array alphabetically, ignoring case. 

java.util.Arrays.sort(word,String.CASE_INSENSITIVE_ORDER);

This uses a predefined Comparator that ignores case in Strings.

c) Sort the array in reverse alphabetical order. 

java.util.Arrays.sort(word,Collections.reverseOrder());

This uses a predefined Comparator that reverses the natural order. I have no idea why it uses a method rather than a constant (it seems to me that Collections.REVERSE_ORDER should exist). Note that, since we are reversing the natural order, the ordering is case-sensitive.

d) Sort the array in reverse alphabetical order, ignoring case.

Here's a program that does this by building its own Comparator: 

import java.util.*;

class Temp {

public static void main (String[] args) {
    String [] word = {"One","Two","three","Four","five","Six","seven"};
    Arrays.sort(word,new myComparator());
    System.out.println(Arrays.asList(word));
    }
    
static class myComparator implements Comparator {
    public int compare (Object x, Object y) {
        return -String.CASE_INSENSITIVE_ORDER.compare(x,y);
        }
    }
}

Note that it uses the predefined case-insensitive comparator for Strings, reversing its meaning by simply negating the value it returns.

You can decrease the amount of code needed, by using Temp as the Comparator class. Here's the code that does this: 

import java.util.*;

class Temp implements Comparator {

public static void main (String[] args) {
    String [] word = {"One","Two","three","Four","five","Six","seven"};
    Arrays.sort(word,new Temp());
    System.out.println(Arrays.asList(word));
    }
    
public int compare (Object x, Object y) {
    return -String.CASE_INSENSITIVE_ORDER.compare(x,y);
    }    
}

It's probably worthwhile to examine the preceding solutions as examples of building Comparators, even though there is a simpler solution. Here's a simpler solution that doesn't require any new Comparators: 

     java.util.Arrays.sort(word,String.CASE_INSENSITIVE_ORDER);
     java.util.Collections.reverse(java.util.Arrays.asList(word));

The reverse method can only reverse a list and not an array, so you have to convert the array to a List. Note though that the resulting List is "backed by" the array, so any list changes are actually made directly to the array. In particular, changing the order of the list, changes the order of the array.