Exam Information — CSE 331 17au

Exam	Date	Topics Covered
Midterm	Monday, November 6th	reasoning about code, specifications, ADTs, testing & debugging, module design, equality & hashing
Final	Monday, December 11th	all of the above plus... exceptions, subtyping, generics, defensive programming, event-driven programming, GUIs, design patterns

Midterm

For the midterm, make sure that all of the following topics are well understood. Click on each topic to see a list of the related ideas that I consider most important to know.

• Quality & Complexity
  • The goal of the course is to learn to write code of higher quality and increased complexity.
  • Increased complexity makes quality even more difficult to achieve.
  • The goals can be accomplished by writing code that is (1) correct, (2) easy to change, (3) easy to understand, and (4) modular.
  • Achieving correctness with high probability requires (1) tools, (2) inspection, and (3) testing. None of these can be left out.
• Reasoning about code ("inspection")
  • A Hoare triple {{P}} S {{Q}} is valid if Q always holds after executing S assuming that P holds before.
  • How to perform forward and backward reasoning for sequences of assignments and if statements.
  • A loop invariant is an invariant that holds each time we reach the top of the loop.
  • A loop is valid iff (1) the invariant holds initially, (2) the invariant holds each time after the loop body is executed, and (3) the postcondition holds when the loop condition is false.

  Problems: 16sp questions 1, 2, 3; 15au questions 1, 2, 3

• Specifications
  • Specifications are necessary for writing high quality programs:
    • They are necessary for determining whether the code is correct.
    • They are necessary for knowing what changes can be made to the code while maintaining correctness.
    • They make the code more understable: they allow the client to understand what the code does without having to read the full details of the code.
    • They are necessary for writing modular programs. They allow the client and implementor to work in parallel.
  • A specification can be made stronger by weakening the precondition or strengthening the postcondition (or both).
  • In general, weaker specifications are easier to implement (they give more freedom to implementors) and stronger specifications are easier to use (they give more guarantees to clients).
  • The postcondition part of a specification includes not only the return value but also any exceptions thrown and any parameters (or other state) modified.
  • In practice, specifications of widely-used methods cannot have preconditions: clients will become dependent on the actual behavior even if the specification says not to.

  Problems: 16sp question 9; 15sp question 2

• ADTs
  • The purpose of an ADT is to hide the details of the data representation in order to make the code easier to change, easier to understand, and more modular.
  • The key idea of an ADT is to define the data type by the set of specifications for its operations rather than the concrete representation of the data in memory.
  • Specifications for ADT methods must make reference to the state of the object without talking about the concrete representation. They do this by describing states using math, which we refer to as the "abstract state" of the object or the "abstract value".
  • We document the implementation of an ADT with two additional concepts:
    • The representation invariant gives assertions about the state of the concrete representation that should hold at all times except when the state is (briefly) being modified.
    • The abstraction function describes how concrete representations satisfying the representation invariant map to abstract values. This documents what the concrete representation means in the term used by the specification.
  • Representation exposure allows clients to see the details of the concrete representation, allowing their code to become dependent on it or even to break the representation invariant.

  Problems: 16sp questions 4, 5, 6; 15au questions 4, 5, 7; 15sp questions 3, 4, 5

• Defensive Programming

  Some techniques for trying to prevent scary bugs:

  • Writing code to check that our assumptions actually hold. This is most commonly used for preconditions of methods and representation invariants of ADT implementations, but can also be used for loop invariants, postconditions, or any other assertions from our reasoning.
  • Making copies of input parameters in case the clients later mutate them.
  • Using immutable classes wherever possible.
  • Not having multiple methods with the same name and number of parameters, which could be accidentally confused.
  • Using @Override to have the compiler double check that we are actually overriding a superclass method.
• Object Equality
  • The specification for equals(Object) requires that (1) it is an equivalence relation, (2) it is consistent (always returning the same value unless the object is mutated), and (3) that equals(null) returns false.
  • The specification for hashCode() requires that it be consistent and that it returns the same value for two objects that are equal. For good performance, we would like unequal objects to have different hash values as often as possible.
  • Mutating objects that are being used as keys in Set or Map data structures will lead to bugs that are often very difficult to track down.

  Problems: 16sp question 8; 15au question 8; 15sp question 6

• Testing
  • In industry, you will most likely be expected to write unit tests for your own code.
  • You can fight confirmation bias by writing your tests before your code. (By definition, these are black-box tests.)
  • Also write clear-box tests after you have written the code. These can test boundary cases that you see from looking at the code rather than the specification.
  • For most methods, it is not possible to test every input. Instead, we break the inputs into subsets on which we believe the outputs of the method will either be all correct or all incorrect ("revealing subdomains") and include a test from each. It is also useful to specifically test inputs on the "boundary" between our subdomains as it is easy to be mistaken about where the boundaries actually are.
  • It is always preferable to have too many tests rather than too few. Too many tests is just exra work. Too few tests means a bug may sneak by us and attack our clients.
  • Correctness is far more important in the code of our tests than changability or modularity. Test code should be as simple as possible. If any code in the test is not obviously correct, then it should be tested too!

  Problems: 16sp question 7; 15au question 6; 15sp question 7

For most of the topics above, I have also given a list of related problems from past midterms. These midterms and their solutions are given below. I do not think it is necessary to study these past midterms in order to be well prepared for our midterm exam. It is most important simply that you understand all the points above. However, if you need some reassurance that you understand these topics well, then looking at these problems may help.

• 16sp: exam solution
• 15au: exam solution
• 15sp: exam solution

The most useful midterms to look at, though, are probably the ones from previous classes taught by your instructor, which are these:

• 16su: exam solution
• 17su: exam solution

Here is our midterm exam:

• 17au: exam solution

Final

For the final exam, in addition to the topics listed above, make sure that all of the following topics are also well understood. Click on each topic to see a list of the related ideas that I consider most important to know.

• Debugging
  • It is easier to find the defect that caused a failure when the failure shows up closer to that defect. Hence, as a general rule, it is a good idea to have your code fail immediately when an error is detected.
  • If the cause of a failure is not immediately clear, it is usually worthwhile to start by finding the smallest or simplest test case that demonstrates the failure.
  • For bugs that are especially hard to track down, use the scientific method to locate the cause: think of a hypothesis that would help you narrow down the cause, design an experiment to test that hypothesis, and repeat.
  • After finding the bug, it's a good idea to add it as a test case in order to make sure the bug doesn't come back after you've fixed it.

  Problems: 15sp question 7

• Assertions
  • Java assertions are like assertions we use in reasoning except that they are checked at run time.
  • Java assertions are useful to detect bugs in your reasoning as well as misuse of your code by others.
  • Java assertions make errors visible at a location closer to the true cause, which makes debugging easier.
• Exceptions
  • Checked exceptions that could occur in a method must be caught or declared using the throws clause.
  • Exceptions that are subclasses of RuntimeException or Error are unchecked.
  • When choosing between checked and unchecked exceptions, decide whether it would be worthwhile to force all clients to think about how to handle that error. In particular, if there is probably no way to recover from the error, then it probably should be unchecked.

  Problems: 15au questions 1.i, 2.j

• Subtyping
  • A (true) subtype is one that could be substituted for instances of the supertype without causing any errors in correct client code. (This is Liskov's "substitution principle".) In other words, a subtype is one that has a stronger specification.
  • Java subtypes are not necessarily true subtypes because the Java compiler only checks at the level of type signatures, not the full specification (including the effects, throws, return, etc.).
  • Java subclasses are often tightly coupled to the superclass. For example, subclasses can be dependent on the pattern of self-calls within the superclass, and there may be instances where overriden methods are called while the representation invariant does not hold. As a result, we recommend:
    • Either explicitly design the class to support subclassing or disallow it (by making the class final).
    • Prefer composition to subclassing.

  Problems: 16sp questions 1.c, 5 (though 5.a and 5.d are debatable); 15au question 1.n; 15sp questions 2, 3

• Generics
  • Generic types usually only make sense for classes that are containers.
  • Generic methods are often useful for any methods that take containers as arguments.
  • Subtyping relationships between parameters are not translated by Java into subtyping relationships between generic types. E.g., if A is a subclass of B, it is not the case that List<A> is a subtype of List<B> or vice versa.
  • Surprisingly, subtyping relationships between types are translated into subtyping relationships between arrays of those types. E.g., if A is a subclass of B, then A[] is a subtype of B[]. However, attempts to write an instance of A into the latter array will throw an exception at runtime.
  • If T is a type parameter, Java does not allow creating an array of type T[]. Just use ArrayList<T> instead.
  • If A is a generic type, Java does not allow checking whether an object is an instance of A<T> for any T. It only allows checking if an object is an instance of A<?>. In particular, the latter must be used when implementing equals.

  Problems: 16sp question 10; 15au questions 1.e, 1.g, 1.h, 7; 15sp questions 4, 5, 6

• Module Design
  • A key goal in deciding how to separate code into modules is to reduce the dependencies (coupling) between modules, where possible. More coupling will make the code harder to understand (because you must think about more of it simultaneously to understand each module) and, hence, make the code less likely to be correct.

  Problems: 15au question 2.h; 15sp question 11.a

• Method & Constructor Design
  • Try to avoid having many parameters of the same type on one method as clients can easily forget the correct order and, when they do, the compiler may not notice their mistake.
  • The job of a constructor should be to create a valid instance of that type (i.e., one whose representation invariant holds) and nothing more. Code that is not working toward that end should be removed.
  • The Builder design pattern allows clients to construct an object describing the instance they want created (and then call a method to have it created).

  Problems: 16sp question 1.h; 15au question 8.b

• Readability
  • Write code that is intended to be read by another human being, not just by a compiler.
  • Your code will be easier to read if you break it into small-ish paragraphs and give each a comment that explains what it does (unless the code itself is just as clear).
• Event-Driven Programming
  • An event-driven program is one whose main thread sits in an event loop, which repeatedly waits for an event and then process it.
  • GUIs and servers are important examples of event-driven programs.
  • In most OSes, it is not possible to wait for all types of events in a single event loop. For example, it is common to need separate event loops for UI and networking. This is unfortunate:
    • Having multiple event loops makes debugging even more difficult.
    • Having multiple event loops introduces the possibility of cross-thread synchronization errors.
• GUIs
  • GUIs are typically constructed by putting together a hierarchy of components of different types (e.g., buttons, panels, and text fields).
  • Components that contain other components (a.k.a. containers) usually allow you to control how the contained components are arranged. In Java AWT/Swing, this is done with a layout manager.
  • Components allow you to add listeners that will be called upon important events (e.g., button clicks).
  • The Java AWT/Swing event loop is performed on a separate UI thread that is created automatically when the UI is first displayed.

  Problems: 15sp questions 11.d.i, 11.d.ii

• Design Patterns
  • Design patterns are solutions to problems that come up repeated in object-oriented programming.
  • Static factory methods are often more readable than calling constructors directly.
  • Factory objects allow clients to provide a callback that will decide what type of class is created.
  • Both static factory methods and factory objects, unlike constructors, allow the code to return a subtype and/or to return an existing object rather than creating a new one.
  • Adapters are necessary to bridge differences between interfaces that should be the same but aren't (for whatever reason).
  • Composites allow collections to be treated in the same manner as individual objects. This pattern is used extensively in JavaScript programming (using jQuery).

  Problems: 16sp questions 1.f, 1.g, 1.i; 15au question 8; 15sp questions 9.a, 9.b

For most of the topics above, I have given a list of related problems from past finals. These finals and their solutions are given below.

• 16sp: exam solution
• 15au: exam solution
• 15sp: exam solution

As with the midterm, the finals from the previous courses taught by your instructor will be most similar to our final. They are the following finals:

• 16su: exam solution
• 17su: exam solution

Once again, I do not think it is necessary to study these past finals in order to be well prepared for our final exam. It is most important simply that you understand all the points above. However, if you need some reassurance that you understand these topics well, then looking at these problems may help.