DISCUSSION QUESTIONS

IMPORTANT NOTE: Discussion questions are a learning or study aide to help you reflect on the concepts and activities in the course. Answer the questions in your notebook or electronically, and be prepared to discuss them in class. You do not need to submit your answers.


DQ: Review

Be prepared to define the terms in the following list:

  • class
  • constructor
  • method
  • method invocation
  • method signature
  • return type
  • parameter type
  • formal parameter
  • actual parameter
  • class variable
  • instance variable
  • local variable
  • scope
  • access modifier


DQ: More Review

Be prepared to define the terms in the following list:

  • inheritance
  • superclass
  • subclass
  • abstract class
  • data hiding
  • encapsulation
  • polymorphism
  • dynamic binding


DQ: Percolation

Here are some questions we will talk about in class:

  • In the Percolation project we have square N x N grids. Do they have to be square?
  • Consider the initial display of the grid and its contents. Does the time it takes to "paint" the background (not including the grid contents) depend on the size of the grid? Does it depend on the number of grid elements? What about displaying the elements in the grid?
  • How does SlowPercolationController drive the Step process?
  • Assuming there are N rows in a grid, how many steps does it take a VerticalPercolator to reach the bottom (or get stuck and it can no longer percolate), in the worst case? What is the worst case?
  • What about GravitationalPercolator? What about AllDirectionPercolator? (Be creative when thinking about the worst case.)
  • How does ListPercolationController drive the Step process?
  • What is the impact of that on the time it takes to execute a single step? How about on the time it takes to run until the material is as saturated as it can be, given the presence and location of obstacles?


DQ: ArrayList Performance

  • What is the time complexity for each CRUD* operation in an array (fixed size)? Assume you have a companion variable storing the current number of items in the array. How do you think this might be different for ArrayList? Then read the class documentation for ArrayList. Were there any surprises?

    *CRUD stands for Create, Read, Update, Delete. It's a common acronym when referring to database operations, but we can use it for common data structures as well.


DQ: Queue as ArrayList

  • What would be the issues if you implement a Queue ADT using an ArrayList?


DQ: LinkedList Performance

  • What is the time complexity for each CRUD operation in an linked list?
  • How might you implement a Queue as a linked list?


DQ: Big-O Analysis of Lists

  • Be prepared to discuss the Big-O analysis of java.util.ArrayList and java.util.LinkedList.


DQ: K_SimpleLL Performance

  • What is the time complexity for each CRUD operation in your K_SimpleLL class?


DQ: Stack Implementation Choices

  • What are the advantages or disadvantages of implementing a Stack ADT as an ArrayList or a LinkedList?


DQ: List Comparisons

  • 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.


DQ: Sorting Algorithms

  • Why does the inner loop (the "insertion loop") in Mystery Function #1 go backwards from j = i - 1 down to 0?
  • What is the Big-Oh notation for each of the mystery functions from last week?


DQ: More About Sorting Algorithms

  • 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: OrderedList Follow-Up

  • Comparing OrderedList and LinkedList, note that OrderedList does not have addFirst, addLast, or set methods. Nor does it have add(int index, T element) nor addAfter(int index, T element). Why do these methods not make sense for this version of a list?

    On the other hand, there is no problem with having get(int index), remove(int index), or remove(T element). What makes these methods different from the ones above?


DQ: Recursive Lists

  • How is an empty list represented in K_SimpleLL? How is an empty list represented in K_RecLL?


DQ: Maps

  • 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())
          System.out.println(itr.next());
  • 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?