Prelim 1 study guide

The exam covers lectures 1–11 and their associated readings; discussion sections 1–5; quizzes 1–5; and assignments A1–A3.

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: we may overlook missing semicolons or unambiguous spelling/capitalization mistakes, but ambiguous or structurally invalid code will be penalized.

The exam will not allow access to reference materials. You will not have access to notes, a “cheat sheet”, 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

  • Static vs. dynamically typed languages
  • Variable declaration and assignment; final
  • Primitive types: boolean, int, double, char
  • Logical, relational, and arithmetic operators
  • Reference types and null
  • Strings: immutability, length(), charAt()
  • Arrays: Type notation, creation, length, indexing
  • Object diagrams
  • Wrapper classes and autoboxing

Java syntax and structures

  • if-statements, while-loops, for-loops (standard and enhanced form)
  • Blocks, scope, and shadowing
  • Method declarations and signatures; static methods
  • Exceptions: try/catch statements, checked vs. unchecked exceptions (throws)

Classes

  • Instance variables (“fields”)
  • this reference
  • Constructors and new-expressions
  • Class invariants, preconditions and postconditions, method specifications
  • Inheritance: overriding methods, use of super
  • Class Object: toString(), == vs. equals()
  • Generics and type parameters

Object-oriented programming

  • Abstraction; client vs. implementer roles
  • Encapsulation and access modifiers (public, private, protected)
  • Subtyping
  • Java interfaces, implements
  • Type hierarchies and subtype notation (<:)
  • Variables’ static types vs. objects’ dynamic types
  • Dynamic dispatch
  • Casting and the instanceof operator
  • Inheritance, extends

Software engineering

  • Defensive programming: assert statements and invariant checks
  • Testing: black box vs. glass box testing

Data Structures

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

Efficiency

  • Big-O notation
  • Time and space complexity
  • Best case vs. worst case
  • Analyzing complexity of nested loops
  • Application to searching algorithms (linear and binary search)

Skills

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

  • Translate a short, 1-line mathematical formula into a Java expression that computes the formula. The formula could involve integers, floating-point numbers, and booleans, as well as arithmetic, logical, and relational operators.
  • Given the name of a type, classify it as either a primitive type or a reference type.
  • Given a type boolean, int, double, or char, and a value of that type, write a variable initialization statement that causes the variable to be assigned that value.
  • Given a few lines of code, predict the result of adding or removing keyword final.
  • Given a short expression that contains a mixture of types int and double, correctly predict the effect of any widening or casting operations. Examples: 1.8 * 10; (double) 1 / 4.
  • Given the name of a variable and a one-sentence specification of the new value it should contain, write an assignment statement that satisfies the specification. Examples: “increment x by 1”; “assign foo the result of calling function bar on arguments baz and quux”; “initialize next to null”.
  • Implement a short static method that satisfies a given specification. The specification is stated in a mixture of math and English. Implementing the method requires the use of if statements, ternary operators, for loops (standard or enhanced), and/or while loops. Examples: the methods on A1.
  • Write a short method that manipulates a string using the length() and charAt() methods and the + operator. Examples: return the next-to-last character (if any) of a string, return the concatenation of the first and last characters (if any) of the string. Or, given such a method without its name or specification, predict the result of running the method on a given input.
  • Write a short method that uses arrays to accomplish a specified task. The task might require declaring an array, initializing an array, getting the array’s length, indexing into the array, and/or looping over the array. Example: create an array named smallInts of length 10 that contains the integers 0 through 9 in increasing order. Or, given such a method without its name or specification, predict the result of running the method on a given input.

  • Classify a short program as containing a compile-time error, a run-time error, or no errors. The program could contain any of the Java features mentioned elsewhere in this study guide.
  • State the static type of an expression, given information about the types of variables occurring in it. The expression could contain any of the Java features mentioned elsewhere in this study guide.
  • State the dynamic type of an expression, given information about the values of variables occurring in it. The expression could contain any of the Java features mentioned elsewhere in this study guide.
  • Draw the object diagram that results at run-time from executing a short program. The object diagram must correctly use square versus rounded boxes, and the arrows in it must start and end at the correct places. Names and types must be labeled in the correct locations. Fields of objects must be correctly enclosed in the object. Null references must be correctly depicted, as must strings and arrays. The program could use a mixture of primitive types and reference types, with the corresponding value and reference semantics. Example: the Counter code and diagram from lecture.

  • Given the code for a method, circle and label these parts: return type, parameters, specification, keywords, types, literals.
  • Given the code for a short class, circle and label these parts: fields, methods, constructors, supertype (class or interface).
  • Given a class diagram, circle and label these parts: name, state, behavior.
  • Given the code for a short class, create the class diagram for it.
  • Given the method specifications for a class, write the field declarations and class invariants that will suffice to implement the methods. Example: Counter and Fraction from lecture.
  • State the default value to which a field will be initialized, given the type of the field.
  • Given a constructor signature, write a new expression to instantiate an object with that constructor.
  • Given fields and a class invariant, write a constructor that initializes an object by truthifying the class invariant. The parameters of the constructor might be given, or you might need to invent them yourself to satisfy a given specification. Examples: the constructors in A2.
  • Given a method signature, write an expression that invokes that method. The arguments to the method might be given, or you might need to invent them yourself to satisfy a given specification.
  • Given a method specification, fields, and the class invariant, write the (short) body of the method. Examples: the methods in A2.
  • Given a piece of code, circle the parts of it where a given name is in scope.
  • Predict the result of executing a piece of code that involves names that shadow each other. The shadowing could involve local variables, method parameters, fields, and expressions such as this.field.
  • Given code involving a class, label the parts that are written by the client of the class vs. the implementer of the class.
  • Circle and label the following parts of a given method specification: preconditions, postconditions, effects.
  • Given a method specification containing a precondition and postcondition, and an invocation of that method with some arguments, but not given the method body, predict the result of the invocation. If the behavior would be undefined, suggest at least three possibilities of what might happen.
  • Annotate a method body with an asterisk at each point where the class invariant is required to hold.
  • Write defensive code to assert the preconditions of a method, given the method signature and specification.

  • 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. Another example: the same as before, but the two values may have different types. (Update 3/8/23: we haven’t yet covered the latter.)
  • 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 method specification, invent at least three black box tests for it. The tests must not violate the method precondition. The tests must state the input and expected output. The tests do not have to be expressed in JUnit syntax.
  • Given a method specification and implementation, invent at least three glass box tests for it. The tests must not violate the method precondition. The tests must state the input, expected output, and actual output. The latter two might differ if the method implementation is incorrect. The tests do not have to be expressed in JUnit syntax.
  • Given a method specification and implementation, invent a set of glass box tests that achieve full line coverage. The set should include as few tests as possible. Example: Counter from lecture.

  • Given a class whose members are marked as either public or private (but not protected nor “default”), predict the result of compiling client code that attempts to access those members.
  • Given a class with some fields and class invariants, where some field(s) are marked as public, write client code that invalidates the class invariant by exploiting that visibility.
  • Given a class diagram and a skeleton implementation of that class (i.e., pieces such as method bodies or constructors or specifications may be missing), add public or private to each class member to encapsulate the state.
  • Given an interface and a class that claims to implement the interface, predict whether the code compiles — that is, whether the class really does implement the interface.
  • Given an interface containing at most about three methods (including signatures and specifications), write a class that implements the interface. The fields and class invariant might or might not be given. Example: the interface is for complex numbers and contains observers for the real and imaginary parts, and a method to add complex numbers. You invent two fields and implement the methods with them.
  • Given two or three classes each containing one to four methods, write an interface that abstracts the common behavior they contain. Only the method signatures need to be written in the interface, not the specifications.
  • State all the subtype (<:) relationships that exist in a provided class hierarchy. The hierarchy could be given in the form of a class diagram or code. Example: state all the subtype relationships between Piece, Rook, King, and Fraction as given in lecture.
  • Apply the compile-time reference rule to answer whether a piece of code involving two or more class types will compile. Example: Piece p = new King(); p.castle().
  • You are given a piece of code that violates the compile-time reference rule. Insert a cast to make the code compile. Your cast must not cause a runtime exception.
  • Given a variable of static type S, perform a runtime check to determine whether it is of dynamic type D. If so, cast the object to type D and invoke a method that exists in D but not in S. Example: cast an Object to a String and invoke length().
  • Given a statement that uses a cast, classify the cast as one of the following: (i) allowed at compile-time but could fail at run-time, (ii) allowed at compile-time and will always succeed at run-time hence unnecessary, (iii) allowed at compile-time but will always fail at run-time, (iv) not allowed at compile-time.
  • You are given a class D that extends another class C, where D overrides some of C’s methods but not others. Some of the methods contain print statements and/or super method invocations. You are also given some client code that creates objects of the two classes. Use the bottom-up rule to predict the result of the dynamic dispatch that results from invoking methods on the created objects. Specifically, state what is or is not printed as a result of the invocation. Example: Parent/Derived/Child iClicker question in lecture.
  • Given a class C, write a class D that overrides a method in C to customize its behavior to a refined specification. Example: override Object.toString() to provide a meaningful string representation for a Fraction class.
  • Write a short constructor that delegates some initialization to a superclass using super(), then finishes construction of its own class’s fields. Example: given classes for 2D and 3D points, write the 3D point constructor such that it delegates initialization of the x and y coordinates to the parent class, then initializes the z field itself.
  • Write a short method that delegates some work to a superclass using super, and also performs some work of its own. Example: given classes for 2D and 3D points, and a 2D-point method that negates both coordinates, override that method in the 3D-point class, such that it negates its own z coordinate, and uses the superclass’s method to negate the other coordinates.
  • Given a class hierarchy that contains some classes that are abstract, classify a new expression as allowed at compile time or not.
  • You are given the code for a class. There is a method in the class that it is impossible to implement; it can only be meaningfully implemented in a subclass. The method currently raises an exception. Revise the class and method to be abstract. Strike through the code to be eliminated, and write the keywords or other code that must be added. Example: making Piece abstract in lecture.
  • Given a class diagram, add class Object to it. Draw the arrows indicating what classes extend it. Write toString() and equals() in the box for Object with their types.
  • You are given the code for a few classes. Some of them implement equals() and others do not. You are also given code that instantiates some objects of those classes and compares them with == and/or equals(). Predict the boolean return value of those comparisons.
  • Given the implementation of a equals() method for a class, circle which of the following properties it satisfies, and cross out the properties it does not satisfy: reflexive, symmetric, transitive.

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

  • 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/A3, 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.

  • Match each of these complexity classes to its common name: \(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n^2)\), \(O(2^n)\). (Common names: constant, logarithmic, linear, quadratic, exponential.)
  • Given the common names of several complexity classes, order them from smallest to biggest. Example (not in order): exponential, constant, linear.
  • Given a growth-rate function, indicate which of several Big Oh sets it is in, and further indicate which of those is the tightest bound. Example: function is \(42 n^2 + 3 n + 7\), sets are \(O(1)\), \(O(n)\), \(O(n^2)\), \(O(2^n)\).
  • Use the definition of Big Oh to show that a growth-rate function is in \(O(n)\) or \(O(n^2)\) by stating suitable constants \(c\) and \(N\). Example: show that \(42 n^2 + 3 n + 7\) is in \(O(n^2)\). Out of scope: a proof involving logarithms.
  • Given an English description of an algorithm, state what quantity describes the problem size, and state the algorithm’s worst-case time complexity using Big Oh notation. Example: compute the sum of the integers stored in an array.
  • Variants of the above skill: Java code instead of an English description; best-case instead of worst-case; space instead of time.
  • Out of scope: Big Omega and Big Theta notation. The exam will use only Big Oh, but we do expect you to be able to give the tightest Big Oh bound for both best and worst cases.

Study tips

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

Sample exams

Here are some examples of exams from past courses covering similar material. Please note: these examples cover topics that are not in scope for our exam this semester, and they do not cover all topics that are in scope for our exam. The organization and style of questions on these exams is not necessarily indicative of what you will see this semester. Some notational conventions differ between other courses and ours.

Merely reading solutions is ineffective for knowledge retention. Pro-tip: do not look at the solutions until you have already solved the problems and checked your answers using your notes, IntelliJ, and/or a study partner.