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 wordFrequency; Note that you cannot use a Map because you cannot use primitive types as type parameters in Java. What is a Map>? 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 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 When do you use the throw statement? What is the catch clause used for? What are checked exceptions? When do you use the throws clause? How (and why) do you design your own Exception types? What does it mean: throw early, catch late? What are all permutations of the word beat? What is: backtracking? How many solutions are there altogether for the four queens problem? How can you accidentally replicate instance variables from the superclass? Where does the super/sub terminology come from? What is: accidental overloading? What is polymorphism? Define: dynamic method lookup. Is the method call Math.sqrt(2) resolved through dynamic method lookup? Define: abstract class(es). Define: final methods and classes. Define: protected access. Why don't we simply store all objects in variables of type Object? When (and why) do you use the reserved word super? When (and why) do you use super with parentheses? What is the purpose of the method toString in class java.lang.Object? (Answer). What is the purpose of the method equals in class java.lang.Object? (Answer). How do you check that two objects belong to the same class (even if you don't know the name of the class)? What is a simple rule of thumb for finding classes? What is a criterion of cohesion for a class's public interface? What is an immutable class? Why is it a good idea to minimize dependencies between classes? Is the substring method of the String class an accessor or a mutator? Is the Rectangle class immutable? If a refers to a bank account, then the call a.deposit(100) modifies the bank account object. Is that a side effect? Explain. What is the difference between a static variable and an instance variable? Name two static variables of the System class. Name a static constant of the Math class. Name a static method of the Math class. What could go wrong if you try to access instance variables in static methods directly? What is a package? What does import do? Which of the following are packages: (a) java, (b) java.lang, (c) java.util, (d) java.lang.Math? What is a unit test framework? What is the JUnit philosophy? Declare an array containing two strings, \"Yes\" and \"No\". Declare an array called words that can hold ten elements of type String. What is a standard rule of design for parallel arrays? In Java can you write methods that receive a variable number of arguments? Explain. What is a linear search? What does java.util.Arrays's copyOf method do? Write a loop that counts how many elements in an array are equal to zero. Can you use java.util.Array's sort method to sort a partially filled array? Why should one be familiar with fundamental algorithms (such as those tested in Exam Three)? What are multidimensional arrays? Suppose you want to store the names of the weekdays. Should you use an array list or an array of seven strings and why? What is regression testing? Suppose a customer of your program finds an error. What action should you take beyond fixing that error? When should you use a do loop instead a while or a for loop? Suppose Java didn't have a do loop. Could you rewrite any do loop as a while loop? What is a sentinel value? What do the break and continue statements do? When do you use them? Describe common loop algorithms: sum and average. Write code if necessary. Describe common loop algorithms: counting matches. Write code if necessary. Describe common loop algorithms: finding the first match. Write code if necessary. Describe common loop algorithms: prompting until a match is found. Write code if necessary. Describe common loop algorithms: maximum and minimum. Write code if necessary. Describe common loop algorithms: comparing adjacent values. Write code if necessary. How do you find the position of the last space in a string? Write code if necessary. How do you simulate a coin toss with the Random class (or the Math.random() method)? How do you simulate the picking of a random playing card? Instead of using a debugger, could you simply trace a program by hand?