Define: collection, list, set, map.

A collection groups together elements and allows them to be retrieved later. A list is a collection that remembers the order of elements. 
A set is an unordered collection of uique elements. A maps keeps associations between key and value objects. 

    Define: linked list. 

Data structure used for collecting a sequence of objects that allows efficient addition and removal of elements in the middle of the sequence.

    Define: list iterator. 

An iterator encapsulates a position anywhere inside the linked list. 

    Do linked lists take more storage space than arrays of the same size? Explain. 

Yes, for two reasons. A linked list needs to store the neighboring node references, which are not needed in an array. Moreover, there is some
overhead for storing an object. In a linked list, each node is a separate object that incurs this overhead, whereas an array is a single object. 

    Why don't we need iterators with arrays? 

We can simply access each array element with an integer index.

    Consider the types HashSet and TreeSet. Do they have anything in common? 

They both implement the Set interface. Set implementations arrange the elements so that they can locate them quickly. 

    Can you add an element to a set at an iterator position? Explain why or why not. 

It makes no sense to add an element at a particular position in a set, because the set can order the elements any way it likes. 

    Arrays and lists remember the order in which you added elements, sets do not. Why would you want to use a set instead of an array or list? 

Adding and removing elements as well as testing for membership is more efficient with sets. 

    Why are set iterators different from list iterators? 

You do not know, nor can you control, in which order the set keeps the elements. 

    How do you find all keys and values in a map? 

To find all keys and values in a map iterate through the key set and find the values that correspond to the keys:

http://www.cs.indiana.edu/classes/c212-dgerman/fall2015/backmatter.jpg

    Consider the types HashMap and TreeMap. What do they have in common?

The HashMap and TreeMap both implement the Map interface. A map allows you to associate elelemnts from a key set with elements from a value collection. 
You use a map when you want to look up objects by using a key. 

    What is the difference between a set and a map? 

A set stores elements. A map stores associations between keys and values. 

    Why is the collection of the keys of a map a set and not a list? 

The ordering does not matter and you cannot have duplicates. 

    Why is the collection of the values of a map not a set? 

Because it might have duplicates. 

    Suppose you want to track how many times each word occurs in a document. Declare a suitable map variable.

Map<String, Integer> wordFrequency; 

Note that you cannot use a Map<String, int> because you cannot use primitive types as type parameters in Java. 

    What is a Map<String, HashSet<String>>? Give a possible use for such a structure. 

It associates strings with sets of strings. One application would be a thesaurus that lists synonyms for a given word. For example, the key
"improve" might have as its value the set ["ameliorate", "better", "enhance", "enrich", "perfect", "refine"] 

    What is a hash function? What is a good hash function?

A hash function computes an integer value from an object. A good hash function minimizes collisions -- identical hash codes for different objects. 

    Define: stack, queue, priority queue. 

A stack is a collection of elements with LIFO ("last-in, first-out") retrieval. A queue is a collection of elements with FIFO ("first-in, first-out")
retrieval. A priority queue collects elements, each of which has a priority (e.g., collection of work requests, some of which may be more urgent than
others). In a priority queue elements can be added in any order, but when an item is retrieved it is the one with the most urgent priority. 

    Why would you want to declare a variable as Queue<String> q = new LinkedList<>() instead of simply declaring it as a linked list? 

This way, we can ensure that only queue operations can be invoked on the q object. 

    Why wouldn't you want to use an array list for implementing a queue? 

Depending on whether you consider the 0 position the head or tail of the queue, you would either add or remove elements at that position. Both are 
inefficient operations because all other elements need to be moved. 

    Why wouldn't you want to use a stack to manage print jobs? 

Stacks use a LIFO discipline. If you are the first one to submit a print job and lots of people add print jobs before the printer has a chance to deal
with your job, they get their printouts first, and you have to wait until all other jobs are completed. 

    What is the value of the reverse Polish notation expression 2 3 4 + 5 * *? 

(2, 3, 4, +) -> (2, 7, 5 *) -> (2 35 *) -> (70)

    Define: big-Oh notation. 

Computer scientists use the big-Oh notation to describe the growth rate of a function. 

    Define: binary search.

A binary search locates a value in a sorted array by determining whether the value occurs in the first or second half, then repeating the search 
in that half, until we either find the value or we determine it's not there at all. 

    Why can't the Arrays.sort method sort an array of Rectangle objects? 

The Rectangle class does not implement the Comparable interface. 

    When designing a program how do you decide what classes you will need in your program? 

To discover classes, look for nouns in the problem description. Concepts from the problem domain are good candidates for classes. 

    Define: inheritance, aggregation (also called composition). 

Inheritance (is-a) is a relationship between a more general class (the superclass) and a more specialized class (the subclass). Inheritance 
is sometimes abused. Aggregation (the has-a relationship) often can be used with better results. It denotes that objects of one class contain 
references to objects of another class. 

    Why should coupling be minimized between classes? 

It is a good practice to minimize the coupling (i.e., dependency) between classes. If the change to a class is drastic, all the classes that
depend on it (the coupled classes) must be updated. Furthermore if we want to use a class in another program all the classes on which it depends
need to be taken as well. Therefore we always want to remove unnecessary coupling between classes. 

    What is UML? 

To visualize relationships between classes, such as dependence, programmers draw class diagrams. In the textbook we use the UML ("Unified Modeling
Language") notation for objects and classes. UML is a notation for object-oriented analysis and design invented by Grady Booch, Ivar Jacobson, and 
James Rumbaugh (see p. 378, section 8.2 and appendix H for details). 

    Define: CRC cards. 

CRC stands for "classes", "responsibilities" and "collaborators". Use an index card for each class. As you think about about verbs in the task
description that indicate methods, you pick the card of the class that you think should be responsible, and write that responsibility on the card.
For each responsibility, you record which other classes are needed to fulfill it. Those classes are the collaborators. 

    Why do the format methods return String objects instead of directly printing to System.out? 

This design decision reduces coupling. 

    Define: interface type. 

A Java interface type declares the methods that can be applied to a variable of that type. 

    Can you convert from an interface type to a class type? 

You need a cast to convert from an interface type to a class type. 

    What is the design purpose of the Comparable interface? 

Implement the Comparable interface so that objects of your class can be compared, for example, in a sort method. 

    Define: callback(s). 

A callback is a mechanism for specifying code that is executed at a later (though clearly specified) time. 

    Define generic interface types. 

Let's use as an example the interface Comparable. Comparable, like ArrayList, is a parameterized type. The type parameter specifies 
the type of the objects that this class is willing to accept for comparison. See Chapter 18 in the textbook for an in-depth discussion
of implementing and using generic classes. 

    Define: inner class(es). Why would you use an inner class instead of a regular one? 

A class that is declared inside another class is called an inner class. Inner classes are commonly used for utility classes that should
not be visible elsewhere in the program. 

    Define: anonymous class(es). Why would you use an anonymous class instead of a regular one? 

An entity is anonymous if it doesn't have a name. In Java, it is possible to declare an anonymous class if all you ever need is a single 
object of that class. 

    Define: event listeners. 

Event sources report on events. When an event occurs, the event source notifies all event listeners. An event listener belongs 
to a class that is provided by the application programmer. Its methods describe the actions to be taken when an event occurs. 

    Describe a common, basic use for JPanel objects. 

Use a JPanel container to group multiple user-interface components together. 

    Describe a common, basic use of the ActionListener interface. 

Specify button click actions (or timer event actions) through classes that implement the ActionListener interface. 

    Describe the meaning and use of a JComponent's repaint method.

The repaint method causes a component to repaint itself. Call repaint whenever you modify the shapes that the paintComponent method draws. 

    Why does a timer require a listener object? 

The timer needs to call some method whenever the time interval expires. It calls the actionPerformed method of the listener object. 

    Explain: the Character class has methods for classifying characters. 

The Character class declares several useful methods such as: isDigit, isLetter, isUpperCase, isLowerCase, isWhiteSpace. 

    How do you convert Strings to numbers in Java? 

If a string contains the digits of a number, you use Integer.parseInt(...) or Double.parseDouble(...) method to obtain the number value. 

    Define: command line arguments. 

Programs that start from the command line receive the command line arguments in the main method's String[] args. 

    Encrypt CAESAR using the Caesar cipher. 
            DBFTBS
            ECGUCT  
            FDHVDU

The answer is: FDHVDU and the sequence above shows how we get there. 

    When do you use the throw statement? 

To signal an exceptional condition use the throw statement to throw an exception object. When you throw an 
exception, processing continue in an exception handler. 

    What is the catch clause used for? 

When you throw an exception, processing continue in an exception handler. Place the statements that can cause 
an exception inside a try block and the handler inside a catch clause. 

    What are checked exceptions? 

Checked exceptions are due to external circumstances that the programmer cannot prevent. The compiler checks that 
your program handles these exceptions. A checked exception describes a problem that can occur, no matter how careful 
you are (e.g., an IOException can be caused by a disk error or a broken network connection). The unchecked exceptions 
on the other hand are your fault. The compiler does not check whether you handle an unchecked exception (such as an 
IndexOutOfBoundsException) since you should in fact check your index values rather than install a handler for that 
exception. 

    When do you use the throws clause? 

Add a throws clause to a method that can throw a checked exception. 

    How (and why) do you design your own exception types? 

Sometimes none of the standard exception types describe your particular error condition well enough. In that case, you
can design your own exception class. To describe an error condition, provide a subclass of an existing exception class. 

    What does it mean: throw early, catch late? 

Throw an exception as soon as a problem is detected. Catch it only when the problem can be handled. 

    What are all permutations of the word beat? 

There are 4! = 1 * 2 * 3 * 4 = 24 permutations in all: b followed by six permutations of eat, 
e followed by six permutations of bat, a followed by six permutations of bet, and t followed by
the six permutations of bea. So that means

b e a t 
    t a
  a e t 
    t e
  t e a
    a e
e b a t
    t a
  a b t
    t b
  t b a
    a b 
a b e t
    t e
  e b t
    t b 
  t b e
    e b
t b e a
    a e 
  e b a
    a b
  a b e
    e b

    What is: backtracking? 

Backtracking examines partial solutions, abandoning unsuitable ones and returning to consider other candidates. Backtracking
is the exhaustive (sometimes guided by heuristics) search for a path in a space of solutions that has been represented as a graph
with the nodes representing states of the problem as it is being solved and the arcs representing actions taken to that end. 

    How many solutions are there altogether for the four queens problem? 

Two solutions: +---+---+---+---+
               |   |   | Q |   |
               +---+---+---+---+
               | Q |   |   |   |
               +---+---+---+---+
               |   |   |   | Q |
               +---+---+---+---+
               |   | Q |   |   |
               +---+---+---+---+ and its mirror image. 

    How can you accidentally replicate instance variables from the superclass? 

class A           { int x; A(int x) { this.x = x; } } 
class B extends A { int x; B(int x) { this.x = x; } } // bad, now two x instance variables 
                                                      // ^ (the one in B shadows the one in superclass)
class B extends A {        B(int x) { super(x);   } } // good, uses constructor chaining 

    Where does the super/sub terminology come from? 

The super/sub terminology comes from set theory. When class A extends B all objects of type A are also of
type B. Therefore the set of A objects is a subset of the set of all B objects. The more specialized objects
in the subset have a richer state and more capabilities. Likewise the set of all B objects is a superset for
the set of objects of type A. 

    What is: accidental overloading? 

In Java two methods can have the same name, provided they differ in their parameter types. We say that their
name is overloaded. The Java compiler considers them completely unrelated. This is different from overriding,
where a subclass method provides an implementation of a method whose parameter variables have the same types. 

    What is polymorphism? 

A subclass reference can be used when a superclass reference is expected. Polymorphism ("having multiple forms") 
allows us to manipulate objects that share a set of tasks, even though the tasks are executed in different ways. 

    Define: dynamic method lookup. 

When the virtual machine calls an instance method, it locates the method of the implicit parameter's class. The
reference to the object might be of one of the superclasses (e.g., Horse), but the method run will be from the actual 
class of the object the reference points to (e.g., Unicorn). This is called dynamic method lookup. 

    Is the method call Math.sqrt(2) resolved through dynamic method lookup? 

No, this is a static method of class Math. 

    Define: abstract class(es). 

An abstract method has no implementation. A class that has abstract methods is abstract. A class can also 
be abstract because we declare it that way (and we don't want it to be instantiated ever). An abstract class
has constructors and constructor chaining rules are still in place. 

    Define: final methods and classes.

You can force other programmers to create subclasses of abstract classes and override abstract method. 
Occasionally, you may want to do the opposite, that is: prevent other programmers from creating subclasses 
(of a certain class) or from overriding certain methods. In these situations you use the final keyword. 

    Define: protected access. 

Protected data in an object can be accessed by the methods of the object's class and all its subclasses. Some
programmers like the protected access feature because it seems to strike a balance between absolute protection
(making instance variables private) and no protection at all (making instance variables public). 

    Why don't we simply store all objects in variables of type Object? 

There are only a few methods that can be invoked on variables of type Object.

    When (and why) do you use the reserved word super? 

Use the reserved word super to call a superclass method. 

    When (and why) do you use super with parentheses?

You can also use the reserved word super to invoke a constructor of the superclass (as part of the constructor chaining rules). 
Constructor chaining: unless specified otherwise, the subclass constructor calls the superclass constructor with no arguments. To
call a superclass constructor, use the super reserved word in the first statement of the subclass constructor. The constructor of
a subclass can pass arguments to a superclass constructor, using the reserved word super. 

    What is the purpose of the method toString in class java.lang.Object? 

Override the toString method (and suppply your own version) to yield a string that describes the object's state. 

    What is the purpose of the method equals in class java.lang.Object? 

The equals method checks whether two objects have the same contents. 

    How do you check that two objects belong to the same class (even if you don't know the name of the class)?

Use getClass().

    What is a simple rule of thumb for finding classes? 

Look for nouns in the problem description. 

    What is a criterion of cohesion for a class's public interface? 

The public interface of a class is cohesive if all of its features are related to the concept
that the class represents. 

    What is an immutable class? 

An immutable class has no mutator methods. 

    Why is it a good idea to minimize dependencies between classes? 

If a class does not depend on another it is not affected by interface changes in the other class. 

    Is the substring method of the String class an accessor or a mutator? 

It's an accessor -- calling substring doesn't modify the string on which the method is invoked. In fact all
instance methods of the String class are accessors. 

    Is the Rectangle class immutable? 

No -- translate is a mutator method. 

    If a refers to a bank account, then the call a.deposit(100) modifies the bank account object. Is that a side effect? Explain. 

It is a side effect. This kind of side effects is common in OOP (Object-Oriented Programming). 

    What is the difference between a static variable and an instance variable?

A static variable belongs to the class, not to any object of the class. Likewise a static method is not
invoked on an object. 

    Name two static variables of the System class.

System.out and System.in are the most popular. 

    Name a static constant of the Math class.

Math.PI and Math.E are my favorite. 

    Name a static method of the Math class. 

We have used Math.pow and Math.sqrt a lot.

    What could go wrong if you try to access instance variables in static methods directly? 

To access an instance variable you need to have a reference to the instance. This is fine always
unless you want to use the this keyword -- implicitly or not -- which you can't do inside a static 
method since a static method does not belong to any particular object, instead it is located at the
class level.

    What is a package? 

A package is a set of related classes. (In some sense it's like a directory of compiled classes.)

    What does import do? 

The import directive lets you refer to a class of a package by its class name, without the package prefix. 

    Which of the following are packages: (a) java, (b) java.lang, (c) java.util, (d) java.lang.Math? 

(b) and (c) are packages. (d) is a class and (a) is an interpreter for a language. 

    What is a unit test framework? 

Unit test frameworks simplify the task of writing classes that contain many test cases. 

    What is the JUnit philosophy? 

The JUnit philosophy is to run all tests whenever you change your code. 

    Declare an array containing two strings, "Yes" and "No". 

String[] words = {"Yes", "No"}; 

    Declare an array called words that can hold ten elements of type String.

String[] words = new String[10]; 

    What is a standard rule of design for parallel arrays? 

Turn them into one array of objects. 

    In Java can you write methods that receive a variable number of arguments? Explain. 

Yes. The syntax is like void fun(int ... values) and in effect values is an int[] variable.

    What is a linear search? 

A linear search expects elements in sequence until a match is found. 

    What does java.util.Arrays's copyOf method do? 

Use the Array's copyOf method to copy elements from one array into another. 

    Write a loop that counts how many elements in an array are equal to zero. 

int count = 0; 
for (double x : values) 
  count += (x == 0) ? 1 : 0; 

    Can you use java.util.Array's sort method to sort a partially filled array? 

Yes. 

    Why should one be familiar with fundamental algorithms (such as those tested in Exam Three)? 

You should be familiar with the implementation of fundamental algorithms so you can adapt them. 

    What are multidimensional arrays? 

You can declare arrays with more than two dimensions. 

For example int[][][] a = new int[3][4][5]; is an array with three dimensions. There is room for 60 elements in it. Each element
can be accessed via a triplet of indices, such as: a[1][0][2]. There is no limit to the number of dimensions an array can have. 

    Suppose you want to store the names of the weekdays. Should you use an array list or an array of seven strings and why?

There are seven days not more or less so we should use an array. An ArrayList is convenient when you don't know in advance how many
elements you will need to store. Absent the need for flexible storage management an array is the ideal choice. 

    What is regression testing? 

Regression testing involves repeating previously run tests to ensure that known failures of prior versions do not appear in new versions of the software. 

    Suppose a customer of your program finds an error. What action should you take beyond fixing that error? 

Add a test case to the test suite that verifies that the error has been fixed. 

    When should you use a do loop instead a while or a for loop? 

The do loop is appropriate when the loop body must be executed at least once. 

    Suppose Java didn't have a do loop. Could you rewrite any do loop as a while loop? 

Yes, the do loop 

  do { body; ] while (condition); 

is equivalent with the following while loop: 

  body; while(condition) { body }; 

Or, as the book has it: 

  boolean first = true; 

  while (first || condition) {
    body; 
    first = false; 
  } 

    What is a sentinel value? 

A sentinel value denotes the end of a data set but it is not part of the data. 

    What do the break and continue statements do? When do you use them? 

A break statement can be used to exit a switch, while, for, do. 

    Describe common loop algorithms: sum and average. Write code if necessary. 

// to compute an average keep a total (sum) and a count of values (count)
int sum = 0, count = 0; 
for ( int a : values ) {
  sum += a;
  count += a; 
}
// average is sum /count 

    Describe common loop algorithms: counting matches. Write code if necessary. 

// to count values that fulfill a condition, check all values and 
int count = 0; 
for ( int a : values ) {
  if (a == b) count += 1; // increment a counter for each match
}
// count how many elements in values match b


    Describe common loop algorithms: finding the first match. Write code if necessary. 

// if your goal is to find the first/last match look for it starting at the right end
boolean found = false; int i; 
for (i = 0; i < values.length; i++) {
  if (b.equals(values[i])) {
    found = true;
    break; // then exit the loop when you find it    
  } 
}
// if found i has the index of the first match 

    Describe common loop algorithms: prompting until a match is found. Write code if necessary. 

while (true) {
  System.out.print(" prompt: "); 
  String line = a.nextLine(); 
  if (a.equals("bye"))
    break; 
}


    Describe common loop algorithms: maximum and minimum. Write code if necessary. 

// to find the largest value update the largest value seen so far whenever you see a larger one
double largest = in.nextDouble(); 
while (in.hasNextDouble()) {
  double input = in.nextDouble(); 
  if (largest < input) 
    largest = input;
}

    Describe common loop algorithms: comparing adjacent values. Write code if necessary. 

// to compare adjacent inputs store the preceding input in a variable 

Compare  http://www.cs.indiana.edu/classes/c212/fall2010/1026002.jpg

to this http://www.cs.indiana.edu/classes/c212/fall2010/notes/1026001.jpg


    How do you find the position of the last space in a string? Write code if necessary. 

Start the loop at the end of the string. Assume String word = ...; 

int i = word.length() - 1; 
while (i >= 0 && word.chartAt(i) != ' ') i--; 
System.out.println( i < 0 ? "No space." : "The index is: " + i ); 

    How do you simulate a coin toss with the Random class (or the Math.random() method)? 

Compute/evaluate Math.random() > 0.5 ? "head" : "tails"; by itself or as part of a return statement in a method. 

    How do you simulate the picking of a random playing card? 

Compute (int)(Math.random() * 4) and associate the result with one of the four suits. 

Compute (int)(Math.random() * 13) and associate with Jack, Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Queen, King. 

    Instead of using a debugger, could you simply trace a program by hand? 

For short programs you certainly could. But when programs get longer it would be very time-consuming to trace them manually.