Write out the code to print out all elements of an array and
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.
Ex 2.1, 2.2, 2.4, 2.5
Try to finish stage one of the Indexing Substrings project.
Come to class with questions.
Be prepared to define the terms in the following list:
SR 3.7, 3.8
What are the "fundamental operations" on Linked Structures,
according to section 4.2?
SR 5.1, 5.2, 5.4, 5.5, and 5.6
EX 5.1, 5.2, 5.7, and 5.8
Be prepared to discuss the Big-O analysis of the different List implementations.
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:
getElement(int index) //returns element without altering list.
SR 9.1 and 9.2
SR 8.1 to 8.6
EX 8.2 and 8.3
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?
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?
Test the following code segment to determine what gets printed:
TreeMap<Integer, String> m = new TreeMap<Integer, String>();
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?