DQ #1

  • Be prepared to define the terms in the following list:
    • class
    • interface
    • constructor
    • method
    • method invocation
    • method signature
    • return type
    • parameter type
    • formal parameter
    • actual parameter
    • class variable
    • instance variable
    • local variable
    • scope
    • access modifier
  • Read through the class documentation for the String class.
  • Given the following block of code, answer the questions about it:
       String h = "Hello";
       String w = "world";
       String n = "My name is Pam.";
       Sting hw = h+w;
    • What does the output from the statement System.out.println(hw) look like?
    • What does the output from the statement System.out.println(n.substring(0,4)) look like?
    • What does the expression h.matches("hello") evaluate to?
    • How can the previous expression be modified so that it evaluates to true?
    • How can we use the string n to get another string containing just Pam's name?
  • Read through Project #1 Indexing Substrings and bring questions to class.
  • Compare and contrast arrays and ArrayLists.
  • Write out the code to print out all elements of an array and an ArrayList.
  • Write out the code to search for a particular element in an array and an ArrayList.
  • Come up with at least one situation where you would use each of these data structures.

DQ #2

  • Ex 2.1, 2.2, 2.4, 2.5
  • Try to finish stage one of the Indexing Substrings project. Come to class with questions.

DQ #3

  • Be prepared to define the terms in the following list:
    • inheritance
    • superclass
    • subclass
    • abstract class
    • data hiding
    • encapsulation
    • polymorphism
    • dynamic binding
  • SR 3.7, 3.8
  • EX 3.1
  • What are the "fundamental operations" on Linked Structures, according to section 4.2?

DQ #4

  • SR 5.1, 5.2, 5.4, 5.5, and 5.6
  • EX 5.1, 5.2, 5.7, and 5.8

DQ #5

  • Be prepared to discuss the Big-O analysis of the different List implementations.

DQ #6

  • According to Section 6.2, what methods do java.util.ArrayList and java.util.LinkedList have in common?
  • What methods would you specify in a common java.util.List interface?
  • Might any of these methods have the same implementation? If so, would it make sense to have a java.util.AbstractList class?
  • Think about an appropriate set of tests for the following two list methods:
    • addAtEnd(T element)
    • getElement(int index) //returns element without altering list.
  • SR 9.1 and 9.2

DQ #7

  • SR 8.1 to 8.6
  • EX 8.2 and 8.3

DQ #8

  • Re-read the books description of selection sort, insertion sort, Quicksort, and merge sort.
  • In class, we worked through an analysis of the number of comparisons performed by selection sort. Perform a similar analysis for insertion sort. Does the original ordering of the items impact the number of comparisons made by insertion sort? selection sort?
  • Each of the four sorting algorithms that we have discussed (selection, insertion, merge and quick) have their own strengths and weaknesses. Is any one of these algorithms the best choice under all circumstances? Can you think of a scenario for each sort in which it would be the best choice?
  • A stable sort is defined as a sorting algorithm that preserves the original order of duplicate objects. Which of the sorting algorithms that we studied are stable sorts?

DQ #9

  • For the depth-first tree traversals discussed in class (pre-order, in-order, and post-order), the order that the nodes are visited arises naturally from the sequence of recursive calls. This makes it challenging to provide corresponding iterators; hasNext and next will not be called recursively. How does the code in the textbook overcome this difficulty?

DQ #10

  • Test the following code segment to determine what gets printed:
       TreeMap<Integer, String> m = new TreeMap<Integer, String>();

       m.put(new Integer(12345),"John");
       m.put(new Integer(23456),"Sue");
       m.put(new Integer(12543),"Adam");
       m.put(new Integer(32145),"Nathan");
       m.put(new Integer(14352),"Kay");

       Set<Entry<Integer, String>> pairs = m.entrySet();
       Iterator<Entry<Integer, String>> itr = pairs.iterator();

       while (itr.hasNext())
  • Change the code above to use a HashMap instead of a TreeMap. What output do you get? How can you explain the difference between the output of the different Maps?
  • Think about the Data Structures we have studied so far. Since the HashMap allows us to add, remove and search for objects in constant time, why would or wouldn't this be our "ultimate" data structure? Would there be other times/reasons we would want to use other structures? Some examples?