CS

211 Review Guide

Prof. Snyder's Sections
Test #1 Review Guide - Snyder

The first test covers everything we have discussed about basic Java programming, through control
structures, arrays, and methods. We continued into classes and objects, and learned how to create and
use both, including making constructors and other methods. We further discussed visibility
(public/private), which is the last topic on our test.

In preparing for your test, you should be aware that anything in the required readings, anything
presented in lecture, and anything covered in the labs and assignments, is valid testing material. I will try
to create a laundry list of topics here, but it is not a guarantee that things won't show up on the exam.
Since I'm the one making the study guide and our test, it's a pretty good bet that it will indeed be the
same listing of things I feel is important; just be sure you study everything at your disposal, even if this
review guide serves to focus your time on specific topics.

This class, and especially this first test, has a significant focus on being able to write programs in the Java
language. This course also has a significant focus on being able to describe the object-oriented concepts
that we have learned, so as a transition from CS 112, there will likely be an increased (but not extreme)
focus on more theoretical questions, such as "why is X a good idea", or "how does Y make Z exhibit more
encapsulation?". We will still have questions that test your ability to program in Java, just as CS 112
would test your ability to write Python code. But now we will also have a slightly shifted focus towards
the concepts of OO. Sometimes the theoretical part doesn't occupy quite as much a portion of our
presentation time, because the details of writing Java code dwarf the theory; but that doesn't mean the
theory was less important.

This guide does not attempt to go into complete detail, especially when that detail is available already in
our slides and in the book.

Throughout the slides, there are many "Practice Problems" slides; they are an excellent starting point for
the sorts of sample problems you might expect to see on the exam. Other examples (not explicitly listed
as practice problems) in the slides are also quite instructive of what to expect on the test.

Java Basics

The Java compiler translates from source code to bytecode, which runs on the "Java Virtual
Machine". Many different systems have interpreters that translate bytecode to machine
instructions for their particular CPU's.
syntax: the way to write something in a language. semantics: the meaning of a language feature or
specific piece of code.
errors:
o compile-time errors. E.g., syntax errors (can't be interpreted as valid code in the language);
type errors (misuse of language features so that it is not valid code).
o run-time errors. Code compiled, but attempted something illegal/impossible (e.g., divide by
zero, out-of-bounds array index, using null like an actual object value).
o semantic errors. The code compiles and runs (doing what it implied), but we have written
code that doesn't do quite what we want to occur (such as dividing instead of multiplying,
or not-quite-finding the maximum in an array).
Edit-Compile-Run cycle: When writing code, we first edit a document; then we compile it (to
translate to Java bytecode, in this class), which generates the .class file; last, we run it. No matter
what development environment, or language, this three-phase cycle is occurring, even when the
steps are blurred by DrJava or Eclipse or some other IDE.
HelloWorld: be able to write out the "hello, world" program. Although we haven't learned what
quite all the parts of it mean, we are making great progress already. Also, running any program
amounts to this basic piece of code.
o on the test, you won't always have to write code to make a full program; read carefully if a
question just asks for a method, or lines of code that would do something when run. We're
usually just looking for the couple lines or so that relate to a specific task.
Whitespace: any whitespace allowed between any identifiers, operators, etc. (as long as they can
be distinguished, we don't even need whitespace: x+=1*foo(a,b); versus x += 1 * foo ( a , b ) ; ).
Only exception: can't have newlines within a string literal (between matching ""'s). Thus
whitespace doesn't have the indentation meaning that we saw in Python, even though we strongly
encourage indentations again.
Comments: /* multi line */ and //to-end-of-line styles.
identifiers: names for things in our code. Consist of letters, numbers, underscores, and $'s, but
don't start with numbers. (Please don't use $'s: they are for code that writes code).
keywords: identifiers that have built-in meaning in the language, such as: for while if case switch
public private
primitive types versus reference types:
o primitive types: 8 basic types where the values are atomic (no sub-portions) and of a
known, small, fixed size. They are: boolean, char, byte, short, int, long, float, double.
! literals: know how to create literals in all primitive types. Recall hexadecimal input,
F suffix for float, L suffix for longs.
o reference types: types created through a class definition or array definition (whether we
write the class or we get it from a library of code, such as java.util or java.lang).
casting: a conversion from a value of one type to a value of another type.
o implicit casting conversions: when no information is lost, Java will convert between types
for us. E.g., from int to double; from short to int; from anything to String (for printing
purposes, usually; uses the toString() method for objects).
o explicit casting conversions: programmer-specified conversions. Usually required when
the conversion loses precision or other information; tells Java that it is 'okay' to perform
the lossy action. E.g.: from double to int; from long to short.
o Be able to identify when Java performs implicit casts.
2

o Be able to use explicit casts to get data into the right format (type).
Creating Variables
o declaration: a type and an identifier. Tells Java that there should be a named storage
location that can contain one value of the given type, and will be accessed using the given
identifier. Only declared variables can be used, ever.
Expressions vs. Statements
o Expression: a representation of a calculation that can be evaluated to result in a single
value; no indication what to do with the value.
! Be comfortable identifying expressions.
! Understand the ternary ?: expression.
o Statement: a command/instruction for the computer to perform some action; often,
statements contain expressions.
! Be comfortable identifying statements versus expressions.
Strings
o concatenation: + operator.
o implicit conversion of everything to String values when added to a String, or when a String
value is needed.
o escape sequences: \t, \n, \", \\, etc.
o checking for string equality: can't just use ==. Use the equals method: e.g., s1.equals(s2).
o Strings are immutable (can't change).
printing: via System.out.println(), System.out.print(), System.out.printf().
Scanner: class providing convenient methods to read text input from a source (such as
keyboard/System.in).
o Be able to use basic scanner methods: nextInt(), nextDouble(), next(), nextLine(), etc.
Constant: a 'variable' whose value will never change from its initial value. Indicated with the final
keyword.
o naming convention: all caps. ex: MIN_HEIGHT, NUM_PONIES.
increment/decrement: e.g., x++, ++x, x--, --x. "syntactic sugar" for an increment on the previous or
following line. See our slide examples for their semantics. Be ready to examine code using them
and report what happens. We ought not have more than one of these per variable per statement

Control Flow

heavy use of boolean expressions. (expressions that result in a boolean value).

if/if-else. (No elif: since we use {}'s instead of indentation, we can get the same effect with chained
if-else's).
switch: old-fashioned, fast way to branch.
o can only switch based on primitive value (or enum, or String as of Java 1.7).
o cases must be values, not expressions.
o use break statements to manually leave after each case statement (or don't, with unusual
control flow behavior compared to if-elses).
o default case can catch all non-cased values.
while loop: keep executing body as long as guard (boolean expression) is true. Body might execute
zero times (if guard is false first time).
do-while loop: like while loop, but guaranteed to run at least once (guard checked after each loop
iteration, not before).
for loop: init, guard, update. See slides for detailed examples/while loop version.
for-each loop: requires an 'Iterator' (arrays are Iterators). Looks like value-based for loop from
Python; avoids index usage but still lets us access/modify each element in the Iterator (array, for
us for now).
3

break, continue: ways to modify loop/switch control flow. Try not to use them too often, but
sometimes they really do make a block of code simpler.

Arrays

arrays are fixed-length sequences of values, all of a single type. e.g., an array of integers (where
each slot holds one integer, like an integer variable).
representing an array type: place []'s after a type to indicate an array of that type. String
String[]. int int[]. Defines an array type.
o can add multiple dimensions: int[][], float[][][], etc.
Declaration: as always, give a type and an identifier; now the type is an array type. ex: int[ ] xs ;
Instantiation: must indicate exact length.
o {vals,like,this} //allowed at declaration time only.
o new int[]{vals,like,this} // allowed anywhere
o new int[10]. (Fills with default values: 0, false, null, as appropriate for the type).
accessing/update: using xs[index]. index must be an expression yielding an integer value.
o No slicing like Python allowed.
usage with loops. A lot of code examples used loops and arrays; be comfortable doing these sorts
of things.

Classes and Objects

Class: a class is a type. It is like a blueprint for making objects. It defines the state that each object
will have, and what behaviors (methods) are available for those objects.
Object: an object is a value. (A value of a particular class type). It is an instance of its class (one
distinct value of that type). It has its own copy of each instance variable and method.
Terminology: a type defined through a class is called a "reference type", because we don't have the
direct value as with ints; instead, we deal with references to the object value that resides in
memory.

Variable versus Reference versus Object:

A variable is a named container (on the stack). A reference is just a (type,address) pair of an
address of an object in memory that also knows what type it points to. Some variables only
contain primitive values (no reference), while other variables only contain references (the value
is elsewhere). An object is an instance of a class (it's a value), and it resides in the heap memory.
The object contains its own copy of each instance variable and method.
many references can have the address of the same object; they are called aliases. Since there's
only one object involved, updates via one reference are visible through the other references.
instance variable: a (non-static) variable declared inside a class, indicating that each object of the
class will have its own maintained copy of this variable. E.g., the Square class has a side instance
variable. A Coordinate class could have both x and y instance variables.
constructor: special method that is used when creating a new object.
o no return type listed (returns reference to object of the class's type)
o method name must be the class name exactly.
o parameters: entirely at programmer's discretion. (Often one per instance variable).
o default constructor: If a class definition does not explicitly list a constructor definition,
then a default implementation is available: no parameters, and all instance variables
receive default values: 0, false, and null (for reference types).

Methods

named block of code that can be called.

defined in a class thus has access to things defined in the class (no matter what visibility).
available modifiers: visibility (public/private/), static or not, final or not, others we haven't seen.
method signature: modifiers, return type, name, parameter list.
o example: public static void main (String[] args)
parameters: formal parameters defined in parameter list (declares them); when a method is
called, the actual parameters (arguments) are supplied to instantiate the formal parameters for
this particular invocation of the method. Parameters are local variables.
return type: Java enforces that the method will always return a value of the specified return type.
o void: indicates that control flow should return without a return-value. Java enforces this,
too. All possible paths must guarantee a return of the correct type of value.
method overloading: when two methods share the same name, but are still distinguished by their
parameter lists, Java allows them to coexist (never ambiguity which one is being called).
o only the name, number of params, and types of params can distinguish them.
o constructor methods can also be overloaded! This is a great thing.
Control Flow: understand how control flow passes through multiple methods as they call each
other. Our diagrams of the stack of method frames exhibited both this control flow as well as the
location of local data (in the frames, dying as methods were exited) and objects (in the heap
meaning space to the right in our diagrams, which could last arbitrarily long, as long as our
references meant Java wouldn't garbage collect them).

Static

modifier that indicates there should only be one definition for the entire class.
Note: static doesn't mean "unchanging"! That's what the final keyword is for.
static variable: a "class variable". One copy overall, regardless how many objects are made (zero
to many, it doesn't matter). Access as Classname.varname, or, as varname inside the class.
static method: like a regular method, but cannot use instance variables. Therefore, accessible
without an object, directly through class (since no object is used to call it). Access as
Classname.method(..), or inside the class definition as just method(..)
Usage example: main is static (because we don't make an object of the class to run main). If we
want 'helper' methods for main, they must also be static:
o static things can't use non-static things! (Local variables in a static method seem like an
exception, but it's still inside a static location).

References

the result of a constructor call is not the object itself it is a reference to that object.
A reference is simply an address of an object.

Method Calling Conventions (how are actual parameters actually transmitted?)

only values are ever sent across from actual parameters of a method call to formal parameters
during execution of method body.
primitive types: a copy of the primitive value is sent. No effect on the original primitive value is
possible (or wherever it may have been stored).
reference types: a copy of the reference value is sent (creating an alias). No effect on the original
reference is possible; however, these aliases both point to the same object in memory and thus can
witness each others' updates to that object.
6

We had examples of each of these, to understand what effect on memory was possible when
passing primitive/reference types for parameters.
Garbage Collection
When an object is no longer reachable by your program (no existing chain of references can reach
it), Java identifies it as 'garbage', and in the next 'garbage collection' sweep, Java will delete this
object (reclaim its memory for later use).
garbage collection is automatic in Java very convenient! (But there are programming tasks
where garbage collection may not be desirable/allowed/available).

Object class
ancestor of all classes. Provides the toString() and equals(Object o) methods, among others.
o we can redefine toString() to aid in printing (Java uses this toString method to String-ify
any object, quite often with printing in mind).

Packages

means of grouping Java classes for distribution/usage in multiple projects.

utilizes actual folder structure to make package structure. Files must include package statements.
aids code reuse, avoids name clashes, organizes code.
some class libraries (packages) are provided with Java: java.util, java.lang, etc.
a jar file is a "Java Archive": a single-file approach to providing entire libraries of Java classes (still
maintains package hierarchy). It is actually just a zip file!
Classpath
o specifies where Java (javac, java) should look for class definitions. By putting a package's
directory on the classpath (or a jar file directly on the classpath), Java can find all classes
defined in the package.
package usage:
o we could just fully qualify a class from a package at each and every usage:
! java.util.Scanner sc = new java.util.Scanner(System.in);
o But we tend to import it first:
! import java.util.*; // or java.util.Scanner

Scanner sc = new Scanner (System.in);
o Consider our package example

Random Class

pseudorandom number: one that seems random (despite being based quite exactly upon some
seed state and previous values).
Scale/offset the nextFoo values to get the range you want.

Wrapper Classes

class-versions of the primitive types.

o Sometimes only objects are allowed; these also can group more info, like methods and
static things, with the type.
Auto-boxing: casting between the primitive types and their wrapper-class equivalents occurs
implicitly (automatically). Java is able to meaningfully convert between them so it occurs.

Scope

scope of data is the area in a program where that data can be referenced (used).
7

data declared at the class level can be referenced by all methods in that class.
data declared within a method is called "local data", and can only be used in that method.

Terminology

variables defined in a class, whether static or non-static, are called fields.

fields and methods are called "members" of a class.

Visibility

class members (and classes) can be given a visibility. For now, just consider public and private.
public: anyone with access to this object is allowed to use this public portion of it (whether it's
reading/writing a public variable, or calling a public method).
private: access to this member is restricted to other members inside the class: meaning that an
object can use this private thing while performing its own calculations, but the outside world can't
use it.
o Good for enforcing encapsulation: presentation to outside world is the public stuff,
internal-only representations and methods are private stuff.
Based on current view of an object: internal vs. external. (internal: everything available; external:
only public stuff available).
public methods: "service methods". private methods: "support methods".
accessor/mutator methods (getters and setters): ways to individually restore read/write
privileges to users of private variables.
public stuff defines the "interface" (we called it the API/application programming interface in
Python) to the object.

CS 211
Test #2 Review Guide - Snyder

The second test broadly covers inheritance (including overriding, abstract classes and methods,
constructors, etc), interfaces, enumerations, exceptions, numeric systems (converting between bases),
and the concepts of unit testing / debugging / javadoc. It will not include searching/sorting (that is the
breaking point).

In preparing for your test, you should be aware that anything in the required readings, anything
presented in lecture, and anything covered in the labs and assignments, is valid testing material. I will try
to create a laundry list of topics here, but omission here is not a guarantee that things won't show up on
the exam. Since I'm the one making the study guide and the test, it's a pretty good bet that it will indeed
be the same listing of things I feel is important; just be sure you study everything at your disposal, even if
this review guide serves to focus your time on specific topics. This guide does not attempt to go into
great detail (such as exhaustive examples), especially when that detail is available already in our slides,
lab tutorials, and in the book.

As is often the case, if you are not running Java code while you study, you will likely not do well on the
test. Don't restrict yourself to just catching up on reading; be sure you actually practice writing code!
Throughout the slides, there are those "Practice Problems" slides; they are an excellent starting point for
the sorts of sample problems you might expect to see on the exam. The quizzes are another excellent
resource for sample question styles. Other examples (not explicitly listed as practice problems) in the
slides are also quite instructive of what to expect on the test. We've posted a lot of code samples from
class; review that code as a way to see the ways we introduced topics, and think back to how we
discussed why we would do things, followed by how we would do them. Lastly, if you haven't completed
the lab tutorials yet, that's a great source of practice! Don't just skim over examples because you don't
see any difficult situations arising; code it up, make sure it compiles, make sure it works. I have a hunch
people are omitting the lab chapter exercises, and that might be a telling factor in who does well on the
test or not.

Format will again likely be part multiple choice, part short answer, part longer responses.

Topics

Inheritance

Allows a new sort of code reuse: similar state (fields) and behavior (methods) can be "inherited"
from one class to another.
o Establishes a "parent-child" relationship. Also called "superclass/subclass", "base
class/derived class".
o indicated with extends keyword: class Car extends Vehicle
Perhaps most importantly, we now have a supertype/subtype relationship. All the child classes'
objects can be used where the parent class's objects were expected.
Inheriting things: any fields or methods of the parent class are automatically a part of the child
class. They can never be removed. Methods may be re-implemented (with the parent class's
9

approval non-final methods).

Visibility:
o public: anyone that can name it can access it.
o protected: anyone in the package, and child classes outside the package, can access it.
o default (package-private vis.): all in package can see it; nobody outside of the package, not
even children, can see it.
o private: only visible to this specific class (not to children or co-package members).
super : refers to the parent class.
o note: this referred to an instance; super refers to a class.
o uses: calling parent constructors: super(any,args)

finding shadowed (overridden) parent members: s uper.fieldName
constructors: only thing that isn't directly inherited (we must make our own constructors too).
o a child class constructor must call its parent constructor as its very first statement, using
super(any,args); and correctly matching the parameters list of an actual constructor
for the parent class.
! Java actually adds s uper(); to any child class constructor that doesn't explicitly
call its parent constructor. If no such zero-parameters constructor existed in the
parent class, it is a compilation error.
single inheritance: Java allows exactly one parent class, always.
o if no parent class is specified, the Object class is the parent class.
o we can simulate multiple inheritance with interfaces later on.
Overriding Methods:
o child class can provide a new implementation of a method inherited from parent class.
o the method signature must exactly match: name, parameters' types / ordering / number,
and also the return type.
o No matter at what type we're viewing the child object, if we call the overridden method, we
get the child's specialized implementation.
! we call methods on objects; whenever that particular object was instantiated it had
a specific type (the class containing that specific constructor used)
That type always dictates what versions are used, no matter where else (and at
what type) we eventually call methods on that object. e.g., we'd get the same
implementation of makeNoise():
Labrador spot = new Labrador(..);
spot.makeNoise(); // uses Labrador version.
((Dog)d).makeNoise();
// still uses Labrador version.

Overriding Fields (a bad, bad idea):

you can also override fields, but my opinion is that this will almost always be a programming
bug competing versions of the same-named variable (perhaps different types), where
inherited methods use the parent's version, and new/overridden methods use the child's
version. Ugly bugly!
Difference: Overloading vs. Overriding
o overloading: providing same-named methods that purposefully have different method
signatures (parameter list #/types), to provide multiple implementations based on
different inputs. Especially useful for constructors. Possible without any inheritance
involved. The different versions co-exist in peace.
o overriding: requires parent/child, inheritance. Child class inherits method, yet re-defines
what it will do when that method is called by purposefully having the same method
signature, but providing a new body. There can be only one!
10

Object class
o it is always an ancestor (parent, grandparent, ..) of every class.
o provides a few useful methods: equals(..), toString(), others.
o we prefer always overriding these methods.
Abstract class:
o a class that cannot (yet) be instantiated (we can't make objects of this exact type).
o The opposite of an "abstract" class is a "concrete" class.
! concrete classes may be instantiated
o abstract class: achieved by adding the abstract keyword to class declaration.
public abstract class Shape { .. }
o abstract classes also may optionally include abstract methods: methods that are declared
(with abstract modifier), but have no body (a ; instead of {..}).
! just like all other members, abstract methods will be inherited.
o abstract classes may still have child classes. If the child class overrides every abstract
method that was inherited, then the child may be concrete.
o Just like other classes, an abstract class is a type. The collection of fields and methods we
introduced are all guaranteed to exist (and be concrete) for all actual instances from child
classes. This is the whole point of introducing an abstract class into our class hierarchy: to
have a formal way to group related child classes and use them uniformly.
final classes, f inal methods:
o if a class is declared to be final, it may not be extended (no child classes are allowed).
o if a method is declared to be final, it may not be overridden (no child class may ever
change its implementation of this method).

Interfaces

Java's "controlled simulation of multiple inheritance".

An interface is a type.
defines a group of abstract methods that any class may implement.
o an interface never has any fields. Add getters/setters to pretend.
A class "signs the contract" of an interface by claiming it implements it:

public class Car implements Sellable { ..
A class "fulfills the contract" by actually implementing (overriding) every single method of the
interface. If even a single method from the interface is left out, the class must be abstract
(allowing for abstract methods to be passed on to child classes), or else it didn't actually
implement the interface, and a compiler error occurs.
Examples of interfaces in Java's standard libraries:
o Comparable: provides just the compareTo(..) method. Allows an understanding of
ordering. Useful for sorting and such.
o Iterator: provides hasNext(), next(),and remove().
o Serializable: no methods. But clues Java in to make the class representable for storing in
a file or transmitting over a network.
Advanced interfaces:
o interfaces may inherit from each other! We didn't try this, but it's interesting how rich and
related the types we can introduce in Java may be.
11

Enumerations

basically, a finite set of values that are grouped into a new type.
simple examples:
o enum TrafficLight {RED, AMBER, GREEN}
o enum Day {MON, TUES, WED, THURS, FRI, SAT, SUN}
internal implementation (good mental model): as a class, except that constructors must be private
(so no extra values are created anywhere else), and the finite list of values are included at the
beginning of the class definition once and for all (as static fields). Otherwise, we can still add
methods, fields, all the usual class stuff.
Simple Usage:
o in general, access with EnumName.EnumValue (e.g., Grade.A).
o in switch: access with EnumValue. (Java already knows EnumName b/c of the switch
expression)
o in foreach loop (utilizing the array returned by values()):


for (Grade g : Grade.values() ) { ... }
Advanced features:
o add three things at once:
! fields (any visibility)
! private/package-default constructors (not public: can't be accessed outside package
ever, and no protected: enums can't be extended)
! "constructor calls" to the enumerated values to give state to the values (see slides)
o add methods to the entire enumeration. (static or non-static; different visibilities ok except
protected)

Number Systems

Different bases of interest: 10, 2, 16

representations: just different symbols, with column values and symbol values combining to
represent the full value.
o representation choice (which base) doesn't change the value!
o be comfortable counting up in bases 2, 10, 16 (chart from slides/labs)
conversions between bases:
o towards base 10: 2 10, 16 10.
! Process: find column values; find symbol values ( their values in base 10, e.g. C is
worth 12); multiply each symbol by its column value, add these results together.
o from base 10:
10 2, 10 16
! Process, version 1: find enough columns/their values until you've got enough space.
Working from left to right, put as much as you can into each column. When you
reach the right (the 1's column), you should have zero left over.
! Process, version 2: keep dividing by the target base to get a quotient and remainder.
The remainder of each division is the next column symbol from right-to-left, the
quotient is what you divide by the base again. When quotient=0, you are done.
(Watch out: remainder can be zero throughout, but you're not done until the
quotient reaches 0.)

12

Exceptions

Idea: Java's representation of "something went wrong that can't be handled right here".
o when thrown, an exception causes normal control flow to be abandoned, like a rogue
return statement.
o There are many Exception classes, related in a class hierarchy (using inheritance). We can
extend these classes with our own child classes, letting us hook into Java's exception and
exception handling effort.
o Exception classes to know about (know of an example if starred):
!

Throwable
! Exception
RuntimeException
o NullPointerException
o ArrayIndexOutOfBoundsException
o ClassCastException
o ArithmeticException
IOException
o FileNotFoundException

Causing exceptions:
o call a method that throws an exception (e.g. , file not found)
o expression that's nonsensical (e.g., 5/0 or xs[-3])
o manually throw one (e.g., throw new MyException(""");)
Handling exceptions:
o wrap the suspicious code in a try block.
o immediately-following catch blocks specify how to handle exceptions of the particular type
listed in the catch block.
o we can have multiple catch blocks for one try block, where each catch block handles a
different exception.
! order catch blocks from most specific (most childly) to most general (most
ancestral, such as Exception itself).
o we also may have a finally block after all the catch blocks. This block always runs
whether no exceptions occur, or an exception occurs and is caught, or an exception occurs
and won't be caught (the finally block still gets to run before the propagation continues,
and if the finally block throws its own exception then the original one is lost).

Propagating exceptions:
o means we allow it to crash this part of the program, if the exception actually occurs.
o when a try block has no corresponding catch block (or we didn't even have a try).
o Checked vs. Unchecked exceptions:
! checked exceptions that are propagated must be admitted in the signature:
public int foo (int a) throws IOException {..}
! unchecked exceptions that are propagated don't have to be admitted, but may be.
! unchecked exceptions are the R untimeException class, E rror class, and their
children. They tend to represent program bugs and hardware failure respectively, so
should be solved/fixed (for bugs) or dealt with gracefully.
! checked exceptions represent things beyond programmer's control that still must be
dealt with. e.g.:
FileNotFoundException when trying to read a file
InputMismatchException when Scanner token is wrong
13

o side effects and control flow:

! any side effects (reassigning a variable, printing) that occurred before the exception
cannot be undone.
! the current statement isn't even finished (so maybe a method call wasn't attempted
if the argument's evaluation generated an exception; or, the assignment statement
didn't happen because we generated an exception trying to get a value for it).
! blocks of code are abruptly exited in search of an enclosing try-catch-block,
meaning some side-effectful lines that would normally have been executed next will
instead not be run.
Creating your own exception classes
o write a child class of any throwable class (includes all the Exception classes mentioned).
! Extending RuntimeException (or Error) makes yours unchecked; extending
Exception makes yours checked.
! Any (non-final) Exception class may be extended.
! Use of fields, methods, overriding toString() highly encouraged.
o Create objects of your exception class as normal (with constructor call):
!
o

MyExc me = new MyExc ("problem studying", 410);

throw your exception manually:

throw me; //following previous code snippet

Testing and Tools

javadoc: a tool for generating API documentation based on Java packages (and classes).
o generates a lot of HTML (good to put in separate directory. Then, open index.html)
o always "scrapes" source code for things like inheritance hierarchy, implemented interfaces,
listing out fields/methods.
o can write special /** javadoc */ comments that are also inspected by javadoc.
! use @tags to label more info: @param, @return, @exception, @author, etc.
o can limit what levels of visibility are included
o can generate API documentation for many packages/sub-packages all together.
o might add package-info.java files to document entire packages.
debugger: a tool for interactively inspecting values of a running program.
o breakpoints: when these statements are reached, execution pauses (allows user to take
control and inspect/change things).
o stepping: advancing one statement at a time.
! step into: allow steps to travel with method calls and step there too. (follow calls)
! step over: allow steps of method calls to call-return in one atomic step. (stay local)
! step out: keep stepping until a return statement is reached (let's leave now)
o watches / watch lists: a set of variable names that the debugger will show values for at each
pause (of course, can't display anything when nothing of that name is in scope). Just
variables/fields available. (DrJava now allows tracking of expressions, cool!)
o modifications:
! user can directly change a variable's memory to see effects (but doesn't change what
original program will do when run again)
! user can run expressions/statements interactively (to inspect more than just
variables).
! direct edits to source code generally will not affect debugger's behavior until next
compilation/debug-run.
14

Testing
o gaining assurance that code works as expected
o catching bugs in earlier phases saves orders of magnitude of effort!
o test case: specific inputs and expected outputs for some part of the program.
o regression testing: after making any changes, we re-run old tests that had passed, to double
check that nothing was broken.
o Testing styles:
! black box testing: test cases that focus on the meaning of the code: with no view
inside the "black box", what behavior is expected?
! white box testing: test cases that are aware of the particular implementation, and
attempt to get code coverage. Each part of the code (loop, if-else, etc) gets test cases
to try and use that piece of code. In general, test cases that focus on the
implementation more than the general meaning of the code could be considered
white box testing.
o passing all tests doesn't mean program is necessarily correct. (Can't usually test all cases
anyways). Defining correctness is very hard!
o unit testing: writing tests for the smallest parts of a program.
o test-driven development: writing tests before (or at least alongside) implementation

JUnit: a unit testing framework for Java.
o java package that can be imported (and used to run test cases/report on results)
o offers annotations: @Test methods are test cases. Also, @Before, @After.
o require behavior by using assertWhatever methods: assertEqual(..),
assertTrue(..), assertNull(..). Report failures with fail().

Command-Line Arguments
Since running a Java program means running the main method, we can pass in an array of String
arguments on the command-line when we execute our Java program:
demo$ java MyProgram args here 123 "spacey ones in quotes" too
Only strings available: main method signature has (String[] args) parameter list.
values are separated by spaces. matching single- or double-quotes may be used to create a single
String that contains a space (e.g., "spacey arg").
getting numbers: use Integer.parseInt(s) or Double.parseDouble(s), based on any
String s. (e.g., Integer.parseInt(args[0]) ).

15

CS 211

Final Review Guide


This review guide covers the last third of the course (everything after our second test's materials). The
final exam itself will be cumulative: you should anticipate roughly half the exam to cover the materials
listed here, and the other half should cover the materials of the first two tests. The labs go into far better
details than will be shown here; you should consider the lab readings, lab exercises, quizzes, and slides as
other good sources for ideas on what is important, as well as what sorts of questions might be asked.
Good luck!

Searching and Sorting

Searching: given some collection of data, and some key that will identify the piece of data we seek,
search through that collection and return the data.
o some possible returns: a reference to the object; the index within the collection that can be
used to quickly re-find the data.
Sorting: given some collection of data, and the notion of some sequential traversal, relocate values
within the collection so that the traversal will visit values in some ordered fashion.
o examples: sorting an array of Person objects by name, or alternatively sorting by age. Sorting
numbers ascending.
You should be capable of writing a search algorithm and of writing a sort algorithm of your choosing.

Searching

Basic Searching Example: Linear Search

o assuming no ordering of the data, must check every location for the desired value.
o Simply looping over each location and checking for a match is the simplest search.
o for a list of length n, might take n inspections before completing.
Faster Searching Example: Binary Search
o assumes/requires that the data are sorted in order.
o given a range that must contain the key (if it is present in the collection at all), check the
middle value. Either it's the match, or else we know that the key would have to be in just the
left half, or just the right half, of our range.
o repeatedly search on that side range, until either a match is found, or there is no place left to
look (the remaining range is of size zero).
o for a list of length n, only requires log2(n) recursive calls at worst to find the key.

16

Sorting

Basic Sorting Example: Bubble Sort

o idea: one traversal will step through the list from front to back, comparing each adjacent pair
of values, swapping if they're out of order.
! each traversal guarantees that at least one more item is sorted at the end larger values
'bubble' up to their correct location.
! after n traversals (for a list of length n), the entire list is definitely sorted.
o improvements to the basic double-for-loop algorithm.
! each successive iteration doesn't have to run all the way to the end of the list after k
traversals, the last k elements don't need to be compared.
! if no swaps occurred in a traversal, the entire list is sorted stop!
More-Advanced Sorting Example: Merge Sort
o idea: we realize that merging two already-sorted lists into a single sorted list isn't very hard. So
keep splitting the list in half, until we have lists of length 1 (or 0), which are already sorted.
Then re-merge them together preserving the orderedness. Easily defined via recursion, though
not necessary for an implementation.
o merging two lists together: keep inspecting the front item of our two lists; the lower value is
removed from that list and added to our result.
o the simple approach of creating two sub-lists: copies all the values, resulting in a lot of space
usage.

Search and Sort Summary
There are many other ways to search or sort data, we simply looked at a simplistic and then more
involved version of each.

Different issues of efficiency, both in time taken and space needed during the calculation, arise.

Regular Expressions

a way to describe a pattern within Strings that we are interested in finding.

can be used to check if a given String matches, or contains, the pattern.
we can also then extract different parts of the match for further calculations.
Basics:
o any character without special meaning matches itself. (This includes the space character!)
o the period (.) matches any single character
o repetition:
! *
: match zero or more of the previous thing.
! +
: match one or more of the previous thing.
! ?
: match zero or one of the previous thing.
! {n}
: match exactly n of the previous thing.
! {n,m}
: match between n and m inclusive of the previous thing.
! {n,}
: match n or more of the previous thing.
o (parentheses) : groups things together. (e.g., for use with the repetition meta-characters)
17

o |
: the vertical bar indicates "or", allowing the pattern on its left or right to be chosen. Can be
used (with|many|choices|still|choosing|one|of|many).
o character classes:
! used to define how to match a single acceptable character. Just list them inside [ ]'s: [aeiou]
! [a-z]
: the dash(-) indicates a range on the ASCII chart; must be ascending.
! [^abcde] : the caret (^), only when it is the first symbol in a character class, indicates

"not the characters in this character class".
! [nested[classes]] : union. (any single character from either can be selected).
! [nested&&[classes]]
: intersection. Only a character from both classes may be matched.
o pre-defined groups: many common character classes have shortcut names.
! \d : [0-9]
(digits)
! \s : [\t\n \f\r] (whitespace)
! \w : [a-zA-Z0-9_] (identifier characters)
! \D, \S, \W :
[^0-9], [^\t\n \f\r], [^a-zA-Z0-9_] (non-whatever versions)
! other special pre-defined groups also exist. (see Java Pattern class API if you're interested).
o anchors: represent some property other than a specific character.
! ^ : the beginning of line.
! $ : the end of line.
! \b : a word-boundary, the point between a word-character \w and a non-word character \W.
! \B : a non-word-boundary. (the point between 2 word-characters or 2 non-word characters).
o embedded flags: ways to affect the overall meaning of a regular expression.
! (?i)
: case insensitive.
! (?d)
: unix newlines (only \n means newline)
! (?m)
: let ^, $ match on each line in the string, not just actual begin/end of entire string.
! there are more of these we just want to be comfortable with the basic idea.

Representing Regular Expressions in Java.

o We represent a regex inside of a Java String. This means that escaping characters becomes
complicated.
! any quote characters must be escaped (because it's in a String).
! any occurrence of a backslash that was escaping something in the regular expression becomes
a double backslash (so that the String contains the backslash character itself, and doesn't try to
escape something).
! regex's might already have a double backslash to represent a backslash character itself; it'll be
a quadruple backslash in the String!
! good approach: write the regex normally first (perhaps in a comment in your source code),
then represent each individual symbol in a Java String as necessary to obey Java String syntax.
examples of methods we might use with regular expressions
o String class
!
!

boolean matches(String regex)

String replace (String target, String replacement)

String replaceAll (String regex, String replacement)

replaces ALL matches of the target string (which isn't a regex)

replaces ALL matches of the target regex

! String[] split (string regexDelimiter)

Scanner class
! String findInLine (String regex)

18

!
!

String findWithinHorizon (String regex, int horizon)

String next() // relies upon the regex delimiter, settable with useDelimiter() method.

19

Capture Groups
o each parenthesized portion of a regular expression is a capture group. They are numbered 1 and
up, found by scanning through the regex from left to right and numbering each opening
parenthesis found. (The entire regex is considered group 0).
Pattern and Matcher classes
o In order to speed up loop bodies or use further functionality, we can use the Pattern and Matcher
classes.
o Pattern: allows us to represent a "compiled" regular expression as an object with useful methods,
rather than just hiding it in a String.
!
!

public static Pattern compile (String regex)

public Matcher matcher(String candidate)

o Matcher: Provides functionality related to checking for matches or finding the next match within a
Pattern. Also provides the group method for extracting capture groups' values.
!

public boolean matches()

public boolean find()

checks for a complete match between the Pattern used to create this Matcher, and the
candidate String supplied when the Matcher was created. If successful, calls to group with
existing group #'s will succeed, returning the last match of that capture group.
checks for the first match within the candidate String. If successful, calls to group with
existing group #'s will succeed, returning the last match of that capture group.

public String group(int g)

if a successful match or find has been completed, and the regular expression that matched
had a capture group of the given number input, then the String that corresponded to this
group is returned.

Generics

generics allow us to add type parameters to classes or methods (or interfaces).

o This gives us parametric polymorphism entire class / method / interface definitions
parameterized over any type.
o type parameters on a class let us effectively create a whole batch of class definitions:
public class ArrayList<E> { .. } gives us ArrayList<String>, ArrayList<Integer>,
ArrayList<Person>, and ArrayLists of any other type. Even more exotic ones, like
ArrayList<ArrayList<Integer>>.
Problem that is solved: Java sometimes "loses" a type. The original ArrayList only stored Object
values. Even if we only put Integer values in it, Java could only remember that it was an Object
value, requiring lots of casting. (For instance, inside foreach loops). The programmer is now
responsible for this "type checking", and can easily mess up.
o Generics allow use to introduce a type parameter that, once instantiated, gives Java a reminder of
the only acceptable type of inputs that are allowed for this particular ArrayList value.
Class-definition generics
o we may introduce a list of type parameters in a class declaration.
! example: public class Pair <R,S> { R first; S second; }
o those types are now usable anywhere inside the class definition (e.g., for field types, return types,
parameter types, and local definition types). Note: no extra < >'s here after the type parameter list
20

o the type parameters must be instantiated at each constructor call, locking in the correct type

21

Method-definition generics
o we may introduce a list of type parameters in a method declaration.
! example:
public <U> U choose (U left, U right, boolean selector) {

return b ? first : second;
}
! Not connected to class type parameters: these are only instantiated/used inside the method,
and possibly at different types for each call of the method.
! Offers a sort of "infinite overloading", but lets us constrain different types via equality of the
same type parameter, though it will become some specific type whenever the method is called.
Our Examples:
o we looked at a simplistic view of the ArrayList class as an example of generics. We also had
extensive examples of Pairs and Boxes in the lab.
Going further:
o There are more advanced notions of generics, involving notions of subtyping, extending multiple
types (both from class inheritance and interfaces, despite frugal re-usage of the extends keyword),
and even wildcards. Just be aware that we can get more than this basic parametric polymorphism.
Example usage: ArrayList.
o Supply a type in <>'s to create the actual type, which then is used to declare variables or call
constructors: (all in one line here:)

ArrayList<Integer> intlist = new ArrayList<Integer>();

intlist.add(5); intlist.add(7); intlist.add(12);
int sum = 0;
for ( Integer i : intlist) {




sum += i;
}

// decl/constr: give type params.

// usage (no explicit types are given)
// Java knows only Integers are present.

Java Collections

Java standard library versions of common patterns of data.

Implemented through a series of inheritance-linked interfaces, with many generics-enhanced classes
implementing these interfaces through different means (e.g., ArrayList<E> class and LinkedList<E>
class both implement the List<E> interface with different underlying data representations and
correspondingly different behaviors).
Shining examples of data structures! (A taste of things to come in CS 310).

ArrayList<E>

part of the Java Collections Framework, ArrayList<E> represents a List<E> structure (and has an
underlying array implementation, hence the name "ArrayList").
As a class, all list operations are through methods: e.g., xs.get(i), xs.set(i,val) instead of xs[i].
as a list, it has more functionality than just an array: we can add/remove elements (changing the
length of the structure), and we can do so at any index (not just the end). Feels like Python lists
(because it is a list, not an array!). All these behaviors come from implementing List<E>.
extra methods available due to the array implementation: ensureCapacity, trimToSize, more constrs.
Uses generics to allow it to contain any specific type of element. (see generics for more info).

22

Recursion

Recursion generally means that something is defined in terms of itself.

o code can be recursive a method may call itself.
o data can be recursive a class may contain a field whose type is the class type itself.
Code Recursion
o Split the possible actions into base cases and recursive cases.
! Base Case: for specific inputs, we memorize/know the answer, and report it directly without
having to call ourselves.
! Recursive Case: for a given input, we know how to rephrase the solution in terms of a call to
the same method on "smaller" inputs (closer to a base case).
o Recursion(through recursive cases) must be terminated (by reaching a base case), or else it's just
like an infinite loop: never ending. (Actual result would be a StackOverflowError).
! The recursive calls of a method must be on a "smaller" version of the problem. This could mean
subtracting one from some counter, calling on a list whose length is shorter than the current
call's arguments, or anything that represents progress towards a base case.
o Each recursive call is distinct: it has its own frame on the stack, meaning it has its own copy of
local data (parameters, local declarations), and after the recursive call it made is complete, it will
continue its own execution until returning.
o Base cases must be tested before recursive cases, to ensure the recursion can stop.
! error conditions (e.g., negative numbers for factorial) can be handled like base cases.
o Recursion can be used to solve the same problems that iteration can just as we can choose
between a for-loop and a while-loop, we can choose between recursion and iteration. Each one is
better-suited to certain problems.
! Often, definitions themselves are recursive, so it's convenient (translation: low cognitive
effort) to write the definitions the same way.
! Iterative definitions are often faster by a negligible to noticeable amount, so it might be worth
the effort to craft an iterative implementation.
o Recursion is sometimes far less efficient than an iterative approach. For example, Fibonacci can
lead to a drastic amount of duplicated calculations. This is certainly not always the case, but it
means we must be conscious of the decision to write a recursive or iterative solution. To spot
these cases, consider the size of your input (e.g. length of array, value of some number) and think
about if the number of recursive calls could be as large as the input size (recursion might be okay),
could be far larger (recursion is probably a bad choice), or could never be more than a fraction of
the size (like gcd, where recursion is probably a very nice option). If the number of recursive calls
is based on one variable's value like in Fibonacci, then that is a horrendous time to use recursion.
Data Recursion
o Data can be recursive: the definition of the data's structure may include a field of the type being
defined.
o The base case is null.
o The recursive case is the field of the same type.
o Data Structures are often written with recursive definitions. Now the notion of some value may be
represented by many objects of the recursive type, instead of one. This is really the same as an
object having fields, except that the fields happen to be of the same type in this recursive example.
o Example: Linked Lists can be represented as two fields: a value and another LinkedList. (see the
lab for more details)
23

24