Test 2 study guide

The test covers lectures 6-9 and their associated readings; discussion sections 3; and assignment A2. That is approximately all the material covered on the week of Monday July 1st, and all the activities related to that material.

The exam will ask you to write correct and stylish Java code. Your code should not be redundant, needlessly inefficient or complicated, or indicate a lack of understanding of Java features. Your code should follow our coding guidelines, with one exception: unless comments are specifically requested, you may omit them on the exam. Your code should contain at most minor syntactic errors: syntax errors that can be corrected by (i) a local insertion or deletion of punctuation and/or whitespace, (ii) corrected spelling of identifiers, or (iii) transposition of adjacent tokens. In other words, a malformed program that an experienced programmer can nonetheless understand unambiguously with a second or two of thought.

The exam will not allow access to reference materials. You will not have access to notes, a “cheat sheet”, or IntelliJ, or the Java API documentation. Except: if there is a Java API method you must use to solve a problem not listed among the topics below, we will provide a brief specification for it.

List of topics

Variables and types

  • Wrapper classes and autoboxing

Java syntax and structures

  • Exceptions: try/catch statements, checked vs. unchecked exceptions (throws)

Classes

  • Generics and Type parameters

Data Structures

  • Abstract Data Types
  • Bag (resizable array implementation, linked implementation)
  • Linked lists
  • Stacks and queues

Skills

To do well on the exam, you should be able to do the following:

  • Given the signature for constructor of a subclass of Exception, write a throw statement that will throw that exception.
  • Given a method that is written to return -1 or some other such value to indicate an error, revise the method to instead throw a specified exception.
  • Given a method signature and specification that states the possibility of an exception being thrown, write a try statement that attempts to invoke the method, catches the exception if it is thrown, and prints a friendly error message. Example: given the method signature and specification for a method that opens a file, print an apology if it couldn’t be opened because an exception was thrown.
  • You are given a try statement containing several catch blocks; there might be nested try statements, too. There are several print statements throughout. Write the output of the code. Example: iClicker question in lecture.

  • Parameterize a class on generic type(s), and use those types in the class’s fields, methods, and constructors. Example: define a class to represent a pair of values who have the same type, with fields for each value, a constructor to initialize the fields, two methods to get the values of the fields, and a toString() method to print the pair.
  • Given access to an example (i.e., a reminder) of how to initialize an array of a generic type, write a new array initialization that works for a different generic type.
  • Classify a concrete type as usable or not usable for instantiating a generic type parameter. Example: given a class C<T> { … }, classify each of these as legal or illegal: C<int>, C<Integer>, C<int[]>, C<Integer[]>.
  • As a client of class with a generic type parameter, instantiate the parameter on a wrapper class and use it with primitive types. Example: given a class C<T>, create an object of type C<Integer>, and use values of type int as arguments to methods of C, and/or return values from methods of C.

  • Given a written description that includes text, diagram(s), and/or code, classify the entity being described as either an ADT or a data structure.
  • Name at least three kinds of data collections that are common examples of ADTs.
  • Given a real-world example of some data collection, either in written form or as a picture, choose one of the following ADTs as the most appropriate representation: Bag, List, Stack, Queue. Examples: a coin purse, the line to order at the Mattin’s sandwich counter.
  • You are given a real-world example of some data collection, either in written form or as a picture. You are also given one of the following ADTs: Bag, List, Stack, Queue. Identify one characteristic of the collection that makes the ADT unsuitable for representing it. Example: a coin purse and a List.
  • Describe at least four operations that are part of a Bag ADT. The descriptions must include a Java method signature for the operation, and a single sentence describing the main task performed by the operation. Precise preconditions/postconditions are not required for the descriptions.
  • Given a Java interface for a Bag, write a Java method that uses a Bag to perform a stated task. The method should contain no algorithmic errors. Example task: add the individual digits from a phone number to a Bag, then print the frequency of each digit in the number.
  • State one advantage and one disadvantage for each of these approaches to implementing a Bag: an array, a dynamic array, a linked chain of nodes.
  • Given the field declarations for a Bag implementation based on an array, write a class invariant that correctly constrains the relationships between the fields. Example: given fields for size, capacity, and an array, write an invariant that describes which indices of the array are non-null, and how those relate to the size field, and how the capacity field relates to the length of the array field.
  • Given a Java class for a Node, write Java code to construct a chain of linked nodes that contain three different data values. Also write Java code to construct a chain of two other linked nodes that both point to a single, shared data value.
  • Draw a node diagram representing a chain of linked nodes containing N different data values, where N is between 0 and 5 inclusive.
  • You are given a node diagram of a chain of linked nodes. You are also given a new data value. Draw the new node diagram that results from adding a new node to the beginning of the chain. The new node should contain the new data value.
  • Given the fields and class invariant for a Bag implementation (array or linked), and a specification for a Bag operation, implement that operation in Java in less than 5 minutes. The operation might be one we studied in class/readings, or it might be a new one. Example operations: add, contains, frequencyOf, remove a specified value, remove an unspecified value, etc.
  • Given the fields and class invariant for a Bag implementation (array or linked), and a specification for a Bag operation, identify whether the running time required by the implementation would be dependent or independent of the number of items in the bag. Examples: for the array implementation of a Bag with a field that tracks the number of items in the bag, the “size” operation is independent of the number of items, and the “remove specific item” operation is dependent.
  • You are given a series of operations performed on a List, and the specifications for those operations. The specifications identify whether the list uses 0-based or 1-based positioning. Draw the node diagram for the list at the end of that series. Example: addFront(0), addEnd(5), addAt(2, 3), remove(1).
  • Given the fields and class invariant for a LinkedList implementation, and a specification for a List operation, implement that operation in Java in less than 10 minutes. The operation might be one we studied in class/readings, or it might be a new one. Example operations: addAt, addFront, addBack, get, remove at a specific position, remove an unspecified value, etc.
  • Given the fields and class invariant for a LinkedList implementation, and a specification for a List operation, identify whether the running time required by the implementation would be dependent or independent of the number of items in the bag. Examples: for the linked list implementation that has head and tail pointers, the “add at end” operation is independent; but if we had only a head pointer, that operation would be dependent.
  • You are given a series of push and pop operations performed on a Stack, followed by a peek operation. State the value returned by the peek.
  • You are given a series of enqueue and dequeue operations performed on a Queue, followed by a peek operation. State the value returned by the peek.
  • You are given the fields and class invariant for a Stack or a Queue. One of the fields is a Node or a List. Implement in Java a stated operation according to its specification. Example: the Stack is represented by a List field that keeps the most recent item at the beginning, and you have to implement the push operation by adding to the front of the Stack.

Study tips

To prepare for the exam, we recommend the following study habits: