AP Computer Science A

Essential knowledge

Data types

• A type is a set of values (a domain) and a set of operations on them.

• Data types in Java are either primitive or reference types.

• The primitive data types used in this course, which represent numbers and logical values, are int, double, and boolean.

• The main reference types we use are String, arrays, ArrayList and other classes that we write ourselves all of which extend Object.

• The primitive data types and Strings each have a syntax for writing literal values in Java programs, e.g. 1234, 9.876, true, and "foobar".

• Integer values in Java are represented by the data type int. ints are stored using four bytes (32 bits) of memory. Therefore, an int value must be in the range from Integer.MIN_VALUE to Integer.MAX_ VALUE inclusive.

• If an int expression would evaluate to a numeric value outside of the possible range for int, an overflow occur resulting in a mathematically incorrect int value. (For instance Integer.MAX_VALUE + 1 evaluates to Integer.MIN_VALUE.)

• Numbers with fractional parts are represented by the data type double. A double is stored in a 64-bit representation that encodes a significand, and exponent, and a sign, similar to the way scientific notation works.

• Logical values (true and false) are represented by the boolean data type. There are only two boolean values: written as true and false.

• All the other data types we will use are reference data types which means the values that are store in variables and passed to and returned from methods are references to where the real value lives in memory.

• null is a special reference value that represents “no object”. It can be written as a literal value as null. It is the default value for uninitialized member variables and array elements with a reference type.

• Using the dot operator to call a method or access an instance variable on a null value causes a NullPointerException to be thrown.

Variables

• Each variable has associated memory that is used to hold its value.

• The memory associated with a variable of a primitive type holds the actual representation of the primitive value while the memory associated with a variable holding a reference type holds a reference to the actual data which exists somewhere else in the computer’s memory.

• A minimal variable declaration contains a type and a name.

• The type of a variable determines what kind of values we can assign to the variable and what kind of value it produces when used as an expression.

• The name of a variable allows us to refer to it in assignment expression and as a value.

• Two variables can hold references to the same object which allows changes made to the object via one variable to be visible via the other variable.

• When a variable is declared final, its value cannot be changed once it is initialized.

• There are two kinds of variables in Java: local and member. Member variables, are further divided into instance and static variables.

• Local variables are declared in the body of methods and constructors. These variables may only be used within the method or constructor where they are declared. They are not marked as either public or private because they are not accessible at all outside the method or constructor.

• Parameters declared in a method or constructor are also local variables.

• When there is a local variable with the same name as a member variable, the name will refer to the local variable instead of the member variable.

• Member variable are declared at the top-level of a class and can be marked as public or private. Usually variables will be marked private though sometimes classes define important constants as public static final variables, for instance Math.PI.

Expressions

• An expression is any part of a program that can be evaluated to produce a value:

• Literal values, e.g. 10 or "foo", evaluate to the value they denote.

• Variables, e.g. x or Math.PI, evaluate to the current value of of the variable.

• Method calls to non-void methods, e.g. s.substring(1) or Math.sqrt(2), evaluate to the value returned by the method when called with the given arguments.

• Object instantiations via the new keyword, e.g. new ArrayList<>(), evaluate to a reference to a newly created object that has been initialized by running the appropriate constructor.

• Array access expressions, e.g xs[0], evaluate to the value stored at the given position in the array.

• Compound expressions made up of expressions and operators, e.g. x + 2, evaluate to a value determined by the operator and its operands.

• Each expression has a type which is determined by the types of its sub-expressions and the operators involved. The type describes the kind of values it can produce.

• Anywhere a value of a given type is needed we can use any expression that produces values of that type.

Arithmetic expressions

• Arithmetic expressions are expressions that produce an or int and double value.

• The arithmetic operators consist of +, −, *, /, and %.

• An arithmetic operation on two ints will evaluate to an int.

• An arithmetic operation with at least one double value will evaluate to a double.

• Operators can be used to construct compound expressions.

• During evaluation, operands are associated with operators according to operator precedence to determine how they are grouped.

• An attempt to divide an integer by zero will result in an ArithmeticException to occur.

• The casting operators (int) and (double) produce numeric values of the specified type.

• Casting a double to an int produces an int with any fractional part (the digits to the right of the decimal point) truncated.1

• Casting an int to double produces a double with the same mathematical value since all int values are exactly representable as a double.

• Using an int where a double is expected, without a cast, causes the int value to be automatically cast to a double value.

• Values of type double can be rounded to the nearest int by (int)(x + 0.5) or (int)(x – 0.5) for negative numbers.

Boolean expressions

• A boolean expression is any expression that results in a boolean value. The values used in the expression may be booleans or other kinds of values. For instance, x > 10 is a boolean expression even though x must be a number and a == b always evaluates to a boolean even though a and b could be any type of values.

• Boolean expressions are made from boolean literals, boolean variables, methods that return boolean, and expressions involving logical operators, equality operators, relational operators.

Logical operators

• Logical operators operate on boolean values and produce a boolean value.

• The logical operators in Java are ! (not), && (and), and || (or).

• ! is the highest precedence, followed by &&, followed by ||.2

• When the result of a logical expression using && or || can be determined by evaluating only the first operand, the second is not evaluated. This is known as short-circuited evaluation.3

• De Morgan’s Laws allows us to transform some boolean expressions into equivalent expressions.

  • !a && !b = !(a || b)

  • !a || !b = !(a && b)

• Truth tables can be used to prove boolean identities, i.e. different expressions that are equivalent in the sense that for all possible combinations of values for the variables in the expressions they evaluate to the same value. A trivial example of a pair of equivalent expressions is: a && true and a. More complex identities include things like De Morgan’s Laws. For more details see Boolean algebra summary

Equality operators

• Both primitive and reference values can be compared for equality using the equality operators == and !=.

• However two object references are only == when they both reference the same object or when they are both null. This may not, however, be the notion of “the same” that you care about when you are comparing two objects.

• All classes have an equals method inherited from Object and often overridden by classes to provide a way to determine if two instances of the class are equivalent. For example, two String objects with the same character content are equals even when they are not ==.4

• The == operator is sometimes pronounced “equals equals” to distinguish it from the equals method.

Relational operators

• Relational operators operate on numeric values and produce a boolean value.

• Numeric values can be compared using the relational operators <, >, <=, and >= which evaluate to true if their left hand operand is less than, greater than, less than or equal to, or greater than or equal to the right hand operand. E.g. 10 < 20 evaluates to true.

• You can’t chain relational operators in Java the way you can in math. So rather than writing 0 <= x < 10 you have to combine two relational expressions with the logical operator &&, writing instead 0 <= x && x < 10.

Assignment operators

• Assignments in Java are technically expressions that produce a value but normally we care more about their side effect, namely changing the value the variable or array element being assigned to.

• The only assignable places in Java are variables (local or member) and array access expressions, e.g. x, obj.someField, and nums[0].

• The assignment operator = allows a program to initialize or change the value stored in a variable or an array element. The value of the expression on the right of the = is stored in the variable or array element referenced on the left. The value of of an assignment expression is the value that was assigned.

• Compound assignment operators (+=, −=, *=, /=, %=) can be used to assign a new value to a variable or array element computed from the old value. For instance x += 2 is equivalent to x = x + 2. The value of a compound assignment expression is the new value of the variable or array element.

• The increment operator (++) and decrement operator (−−) are used to add 1 or subtract 1 from the value of a variable or an array element. For instance x++ equivalent to x += 1 or x = x + 1. The value of a ++ or -- is the value of the variable or array element before it was incremented or decremented.5

• Note that = (one equals sign) is the assignment operator and == (two equals signs) is the equality comparison operator. If you mix them up, you’ll get either compiler errors or incorrect and confusing behavior from your program.

Methods

• Procedural abstraction means hiding how a value is computed or how an effect is achieved allowing a programmer to use a method without needing to know exactly how the method is written.

• In Java the unit of procedural abstraction is the method.

• Methods allow us to “decompose” or break down a large problem into smaller sub-problems by writing methods that call other methods that each solve various sub-problems.

• We can use methods provided to us by Java (as in the Math methods such as Math.sqrt) and also methods that we write ourselves.

• We can use methods without knowing exactly how they are implemented but it is also useful to write our own method to hide details in one part of our code even though we have to deal with those details elsewhere.

• The code in one method can call other methods, allowing us to build layers of abstractions.

Method structure

• Method signatures must specify three things: the return type, the name of the method, and the method’s parameters.

• The return type specifies the kind of value the method returns. The special return type void indicates that a method does not return any value. All non-void methods must return a value of the specified type.

• Methods with void as their return type are called “void methods” and are called only for the effects they have, such as printing to the screen or changing the state of an object.

• Method parameters are variables and thus must be specified with a type and a name.

• Methods that take no arguments are written with an empty parameter list consisting of just a pair of parentheses.

• The body of the method follows the signature and is enclosed in a pair of {}s.

• Code within the body of a method can refer to the parameters declared in the method signature as well as any local variables declared in the method and any static variables declared in the class. Code in instance methods can also refer to any instance variables defined in the class and the special variable this which refers to the object on which the method was invoked.

Method calls

• Method calls consist of a reference to the method and a possibly empty argument list consisting of a comma-separated list of expressions, e.g. foo(10, "some string").

• The expressions in the argument list are evaluated to get the values that are passed as the arguments to the method. When the method runs the parameters declared in the method signature are initialized to the values of the corresponding arguments, with the first parameter getting the value of the first argument, and so on.

• The arguments passed to a constructor or method call must be compatible with the types identified in the parameter list.

• Arguments are passed to methods by copying values. This means that there is no way for code in a method to change the value of local variable in the method that called it.

• Recall, however, that the value of a reference type is the reference itself; this means code in a method or constructor that is passed a reference to a mutable object can use the reference to alter the state of the object and those changes will be visible to other code that also has a reference to that object. As a matter of good coding practice, methods should not modify mutable objects passed as arguments unless doing so is an inherent part of the method’s purpose.

• Calling a method causes the flow of control to jump to the start of the method after initializing the parameters. When the method returns, the flow of control returns to the point where the method was called. No code executes in a method after a return statement.6

• Values are returned from a method using a return statement consisting of the keyword return followed by an expression that evaluates to a value of the correct type which is then returned from the method. (In a void method return is only used with no following expression to return early from a method.7)

• The value returned by a method is copied, just like method arguments. Again, this means a reference returned by a method can be used to modify object it references.

• A method call to a non-void method is a kind of expression whose value is the value returned by the method.

• A call to a void method can only be for effect and not part of an expression since the method doesn’t return any value. They typically do not need a return statement and simply return when execution reaches the end of the method.

Naming methods in method calls

• Within a class, code can reference other methods in the same class simply by their name with the exception that static methods cannot call instance methods without an explicit object to invoke the method on. But in non-static methods, invoking a method by its simple name is the same as invoking it on this, i.e. on the same object the current method was invoked on.

• Outside a class, static methods are typically referenced using the class name, the dot operator, and the name of the method, e.g. Math.sqrt(2) to invoke the static sqrt method in the class Math.

• Instance methods in other classes are invoked on a particular object using an expression that evaluates to a reference to the object, the dot operator, and the name of the method, e.g. s.substring(1) to invoke the substring method on an instance of String referenced by the variable s.

Control constructs

• Control constructs allow us to control the flow of execution other than by calling and returning from methods. They fall into to two kinds: conditional control constructs and and looping control constructs.

Conditional control constructs

• Conditional statements interrupt the normal sequential flow of control from one statement to the next by allowing some code to execute or not depending on the values of a boolean condition.

• A simple if statement affect the flow of control by executing the statements in the if’s body only if the if’s boolean condition evaluates to true. This provides a one-way selection where a set of statements either is or is not executed, depending on the condition.

• A two-way selection, written with an if/else, causes either one set of statements or another to be executed, one when the boolean condition is true and the other when it is false.

• A multi-way selection, written with an if, one ore more else ifs, and optionally a final else, chooses one of several sets of statements to execute based on a number of different boolean conditions. The code that executes is the body of the first if whose condition is true or the body of the else if all the conditions are false.

• Any code can go in the body of an if or else including other if, if/else, and if/else if/else statements, producing nested conditional statements.

• Technically if/else if/else statements are just regular if/else statements with a nested if/else statement but we write them chained together when we want to express a multi-way selection.

Looping control constructs

• Looping control constructs, also called iteration constructs, change the normal flow of control by repeating a sequence of statements zero or more times.

• In both while and for loops, a boolean expression is evaluated before each iteration of the loop’s body, including the first. When the expression evaluates to true, the loop body is executed. Then the loop repeats this process until the boolean expression evaluates to false..

• If the boolean expression evaluates to false the first time it is evaluated, the loop body is not executed at all. Conversely, if the boolean expression always evaluates to true, the loop is an infinite loop.

• A while loop consists of just two parts: the condition and the body.

• A while loop executes by evaluating the condition. If the condition is true it then executes the body and repeats, back at the condition. Otherwise the loop ends.

• Both the condition and the body will usually refer to variables defined before the loop. If the condition depends on the values of one or more variables and the body contains code that changes those variables, the condition can eventually become false and the loop will stop.

• while loops are most useful when you do not know, before the loop starts, exactly how many times it needs to run.

• A for loop consists of a header and a body.

• The header of a for loop consists of three parts, enclosed in parentheses and separated by semicolons:

  • the initialization clause

  • the condition

  • the update clause

• The initialization clause is run once, before anything else in the loop. Typically the initialization clause declares and initializes a variable called the loop variable.

• The condition is evaluated before each iteration of the loop and the loop only continues if it evaluates to true. Usually the condition is some expression involving the loop variable.

• The update clause runs after the body of the loop and just before the next evaluation of the condition. The update clause usually updates the loop variable, typically by incrementing or decrementing it.

• The body of the for loop is executed after the condition is evaluated and before the update clause. Code within the body can refer to the loop variable declared in the loop header.

• for loops are typically used when we know, before the loop starts, how many times we want to iterate, e.g. once for every character in a string or element of an array.

• A for loop can be rewritten into an equivalent while loop and vice versa, though the while loop will need some code before the loop proper to perform the role of the for loop’s initialization clause and the update clause will need to appear in the body of the while loop.

• The enhanced for loop provides a concise way to traverse an array or an ArrayList in the common case when we only need to deal with one element at a time and don’t care about the index.

• The enhanced for loop consists of a simplified header consisting of just a variable declaration, a colon, and an expression that evaluates to an array or an ArrayList, and a body.

• The body of an enhanced for loop is executed once for each element of the array or ArrayList with the variable assigned the value of each element in turn.

• The loop variable in an enhanced for loop is just a regular variable. Assigning a new value to it has no effect on the array itself.

• The body of a loop can contain any statements including other loops.

• Nested loops are just loops that appear in the body of another loop.

• When a loop is nested inside another loop, the inner loop must complete before the outer loop can continue.

• Since executing a return statement always immediately returns from the current method, it can be used to break out of a loop.8

• “Off by one” errors occur when the iteration statement loops one time too many or one time too few, for instance for (int i = 0; i <= s.length(); i++) rather than for (int i = 0; i < s.length(); i++) when iterating over the characters of a string.

• Unintended infinite loops occur when the condition never becomes false, often due to a bug in the update code.

• See counting loops for another summary of different kinds of loops.

Arrays

• Arrays are a reference type that collects multiple values of a given type into a single value.

• The values in an array are called the elements of the array or sometimes the components.

• Array elements can be either primitive or reference values.

• The size of an array is established at the time of its creation and cannot be changed.

• When an array is created using the keyword new and a size (e.g. new int[10]) all of its elements are initialized with the standard zero value for the element type: 0 for ints, 0.0 for doubles, false for booleans, and null for all reference types.

• Initializer lists can be used to create arrays containing specific values, e.g. new int[] { 42, 52, 103 }. Arrays created this way have their length set to the number of elements provided.

• Arrays have a read-only instance variable length which gives the number of elements in the array.

• The elements of an array are accessed using square brackets ([]) and an index, e.g. xs[0] accesses the 0th element of the array xs.

• The valid indices for an array are 0 through length - 1, inclusive.

• Using an invalid index (less than 0 or greater than length - 1) will cause an ArrayIndexOutOfBoundsException.

• An array access expression is like a variable in that it can be used to obtain a value or as a place that can be assigned a value with = or any applicable compound assignment operator (e.g. += or ++ on on an array of numbers).

• Looping over the individual elements of an array is also called traversing the array.

• Traversing an array with a standard for or while loop requires using an index to access each element of the array.

2d arrays

• 2d arrays are stored as arrays of arrays. Therefore, the way 2d arrays are created and indexed is similar to 1d array objects.

• It is equally correct to think of a 2d array as a 1d array whose elements happen to be arrays.

• The square brackets [row][col] are used to access and modify an element in a 2d array.

• 2d arrays can be initialized with specific values by writing a nested initialization expression like { { 1, 2, 3 }, { 4, 5, 6 } }

• 2d arrays are typically traversed using nested loops.

• Since 2d arrays are stored as arrays of arrays, the outer loop iterates over the array whose elements are 1d arrays and the inner loop iterates over the elements of the 1d array.

• In the outer loop of nested enhanced for loops used to traverse a 2d array, the type of the loop variable must be the type of each row, i.e. a 1d array. In the inner loop, the type of the loop variable is the actual element type.

• Typically, and always on the AP exam, 2d arrays are arranged with the outer array holding 1d array representing the rows of the 2d array. Thus to access the element at row r and column c, we use arr[r][c]. This form is called “row-major order”.

• It is, however, possible to think of a 2d array as representing an array of columns in which case to get the element at row r and column c you would write arr[c][r]. This is called “column-major order”.

• All algorithms that work with 1d arrays will work with 2d arrays, as long as they apply to arrays whose elements are arrays.

Classes

• A class defines a common structure for many objects. The structure is made up of variables, constructors, and methods which, collectively, are called the “members” of a class.

• Defining a class also defines a new type that can be used anywhere a type is needed: in variable declarations, as the return type of a method, or as the type of element on an array or ArrayList.

• An object is a single instance of a class whose data lives somewhere in memory distinct from all other objects.

static members

• Variables and methods can be either static, marked with the static keyword, or non-static, also known as “instance” variables and methods.

• Static variables and methods can be marked as either public or private and then marked with the static keyword before the variable type or the return type of a method, e.g. public static int.

• Each static variable represents a single value stored in the class itself and shared by all instances of the class.

• Static methods can only access static variables and call other static methods.9

• Static members are typically accessed with the class name and the dot operator, e.g. Math.PI and Math.abs().

Instance variables

• An object’s state is stored in its instance variables and each object has its own values its instance variable.

• Instance variables create a “has-a” relationship between the object and the values stored in its instance variables, as in a Point has an x and y value. (This is often contrasted to the “is-a” relationship created when one class extends another.)

• Instance variables can be marked as either public or private before the variable type, e.g private int n. Typically they are made private.

Constructors

• Constructors are invoked to create objects. A constructor’s signature consists of the constructor name, which always matches the class name, and a parameter list.

• Every object is created by calling a constructor using the keyword new followed by the class name and an argument list that corresponds to one of the class’s constructors.10

• The job of a constructor is to initialize the state of an object and leave it in a usable state. Often constructors assign the values passed as arguments to the constructor to the object’s instance variables.

• Constructors have parameter lists that work just like method parameter lists, defining local variables that are initialized with the values of the arguments passed to a call to the constructor. The arguments should provide the data needed to initialize the object’s state.

• When no constructor is written, Java provides a no-argument constructor and all instance variables are set to the default value for their type. (0 for int, 0.0 for double, false for boolean, and null for all reference types.)

• When a mutable object is passed as an argument to a constructor and stored in an instance variable, any mutations made to that object by code in the class will change the state for all code that has a reference to that object. Sometimes it’s necessary to instead store a copy of the argument to avoid changing the original object out from under other code. Other times that’s the whole point of being passed the object.

Methods in classes

• An object’s behavior—what we can do with the object—is defined by the methods in its class.

• Instance methods are called on objects of the class while static methods are called on the class itself.

• Instance methods have access to all an object’s instance variables.

• Methods that take no arguments and simply return the value of an instance variable are called “getters” or, more formally, “accessors”. They are used to give code outside the class access to the object’s state without making instance variables public.

• Methods that return void, take a single argument, and assign it to the value of an instance variable are called “setters”. More generally, methods that change any part of an object’s state are called “mutators”.

Access modifiers

• The keywords public and private control what code can access class members.

• The keyword private restricts access to only code within the declaring class, while the keyword public allows access from any code.

• Classes cannot be marked private and are typically marked public.11

• Access to variables should usually be kept internal to the class. Therefore, instance variables are usually made private.

• Constructors are typically made public but sometimes classes will have private constructors that are only used within the class, either from other constructors or from methods that construct new instances of the class.

• Methods are equally likely to be public or private. The public methods define what we can do with instances of a class but private methods are useful for breaking up big methods into sub-methods that are only useful within a class.

• Code within a class can access the private variables and methods of any instance of the class.

Encapsulation

• Encapsulation is a technique in which implementation details of a class are kept hidden from code outside the class.

• When designing a class, programmers make decisions about what parts of its state to make accessible and modifiable from an external class. Data can be either accessible, modifiable, both, or neither.

• State can be encapsulated by storing it in private instance variables and access controlled by what getter, setter, and other mutator methods are provided.

toString

• The toString method is inherited from java.lang.Object and is frequently overridden to provide a concise, human-readable representation of an object.

• If System.out.print or System.out.println is passed an object, that object’s toString method is called, and the returned String is printed.

• toString is also used when a reference type is include in a String concatenation expression.

this

• Within a non-static method or a constructor, the keyword this is a name for the reference to the current object—the object on which the method was called or the object being constructed.

• The keyword this can be used to pass a reference to the current object as an argument to a method or constructor or as a value to be assigned anywhere a value of the type of the current class is needed.

Comments

• Comments are ignored by the compiler and are not executed when the program is run.

• Three types of comments in Java include /* */, which generates a block of comments, //, which generates a comment on one line, and /** */, which are Javadoc comments and are used to create API documentation.

Invariants

• Invariants are things that must be true if the program is working correctly. They help us think about how different parts of a program work together.

• A precondition is a kind of invariant that defines a condition that must be true before a method is called.

• A postcondition is kind of invariant that defines a condition that must always be true after a method returns successfully. Postconditions describe the outcome of the execution in terms of the value returned and/or any changes to the state of the world.

• The job of a method is to satisfy its postconditions assuming its preconditions have been met. If the preconditions are not met, it is a bug in the code that called the method. If the preconditions were met and the postconditions are not satisfied it is a bug in the method. Methods may or may not actually check that their preconditions have been met.

Overloading

• Constructors are said to be overloaded when there are multiple constructors in the same class with different numbers or types of parameters.

• Methods are said to be overloaded when there are multiple methods in the same class (or inheritance hierarchy) with the same name but different numbers or types of parameters.

• When an overloaded constructor or method is called, which one is invoked is determined by finding the constructor or method whose parameter types match the types of the arguments in the call.

• Overloading of methods doesn’t allow you to do anything you couldn’t do by just giving the different methods different names.

Inheritance

• A class hierarchy can be developed by putting common attributes and behaviors of related classes into a single class called a superclass.

• The keyword extends is used to establish an inheritance relationship between a subclass and a superclass. A class can extend only one superclass.

• Classes that extend a superclass, called subclasses, can draw upon the existing variables and behaviors of the superclass without repeating these in the code.

• Class S should only extend T if there is an “is-a” relationship between S and T. (If an S isn’t a T but they’re related it may be that there should be a “has-a” relationship expressed by one class having an instance variable that holds a reference to an instance of the other class.)

• The Object class in the java.lang package is the direct or indirect superclass of all other classes in Java.

• Classes that do not explicitly extend another class, implicitly extend Object.

• All classes inherit from Object the methods boolean equals(Object other) and String toString() which are described in the AP Java Quick Reference.

• Subclasses of Object often override the equals and toString methods with class-specific implementations.12

Constructors in inheritance hierarchies

• Constructors are not inherited.

• Every constructor must call a superclass constructor as the first thing it does. This can either be explicit, using the keyword super and passing appropriate arguments, or implicit by letting the compiler insert a call to the superclass’s no-argument constructor, if there is one.

• Regardless of whether the superclass constructor is called implicitly or explicitly, the process of calling superclass constructors continues until java.lang.Object’s no-arg constructor is called. At this point, all of the constructors within the hierarchy execute, beginning with the Object constructor. This ensures that before any code runs in a class all of it’s inherited instance variables have been properly initialized.

• The actual parameters passed in the call to the superclass constructor provide values that the constructor can use to initialize the instance variables defined in the superclass.

Inherited methods

• A subclass inherits all the public methods of its superclass as public methods in the subclass.

• A public method written in a subclass with the same method signature as a public method in the superclass overrides the parent class method.

• Subclasses can extend the behavior of their superclass by overriding existing methods or by adding additional methods or instance variables that are not present in the superclass.

• In a subclass, the superclass version of an overridden method, say foo can be called as super.foo() passing appropriate parameters as in any method call.

• The compiler will only allow method calls to non-static methods that exist in the compile-time type of object on which the method is being called, either because the method is defined in that class or inherited from a superclass.

• At run-time, the actual type of the object on which a non-static method is invoked determines exactly what method is run.

Types and inheritance

• Anywhere an instance of type T is required (assigning to a variable declared to be of type T, as a method argument that requires a T, as an element of a T[] array or an ArrayList<T>, etc.) we can also use an instance of S if S is a direct or indirect subclass of T.

• Using an instance of a subclass in the place of the superclass is what allows for the possibility of polymorphism, where the actual class of an object determines what version of an overridden method is invoked.

Built in classes

• Classes in Java are grouped into packages. The classes String, Math, System, Integer, Double, Boolean, and Object are all from the java.lang package which is always available in all Java programs.

• The only class we use from another package is ArrayList which needs to be imported from java.util.

• Application program interfaces (APIs) and libraries provide classes we can use in our programs.

• A class’s documentation describes the attributes, constructors and methods defined in the class.

Strings

• String objects are typically created with String literals but can be constructed via constructors defined in the String class.

• String objects are immutable; many methods on Strings produce new Strings that are related to the original (such as the original converted to all upper case) but the original String cannot be changed.

• String objects can be concatenated using the + or += operator, resulting in a new String object.

• Non-String values can also be concatenated with a String object. This causes an implicit conversion of the values to String objects. Primitive values and null are converted to their standard literal form and reference types are converted using their toString method.

• Escape sequences in Strings start with a \ and have a special meaning in Java. Escape sequences used in this course include \”, \\, and \n.

• A String object has index values from 0 to length – 1. Attempting to access indices outside this range (i.e. less than 0 or greater than or equal to the length of the String) will result in an StringIndexOutOfBoundsException.

• You can think of the index as the number that tells you how far from the front of the string a given character is. Thus the second character in a String has index 1 because there is one character ahead of it. And the first character has index 0 because there are zero characters ahead of it. The length of the string is not a valid index because there is no character in an n-character string that has n characters in front of it.

• The following String methods and constructors—including what they do and when they are used—are part of the AP Java Quick Reference:

  • String(String str) — Constructs a new String object that represents the same sequence of characters as str. There is almost no reason to ever use this constructor.

  • int length() — Returns the number of characters in a String object

  • String substring(int from, int to) — Returns the substring beginning at index from and ending at index to − 1

  • String substring(int from) — Equivalent to substring(from, length())

  • int indexOf(String str) — Returns the index of the first occurrence of str; returns -1 if not found

  • boolean equals(Object other) — Returns true if other is a String and its text is the same as the text of the String equals was called on. Otherwise returns false.13

  • int compareTo(String other) — Returns a value < 0 if the String is alphabetically less than other; returns zero if it is equals to other; and returns a value > 0 if it is greater than other.

• A one-character String at index i in the String s can be obtained by calling s.substring(i, i + 1).

The System class

• System.out.print and System.out.println display information on the computer monitor.

• System.out.println moves the cursor to a new line after the information has been displayed, while System.out.print does not.

The Math class

• The Math class is part of Java and is available in all Java programs.

• The Math class contains only static methods.

• You should know how to use the methods Math.abs, Math.pow, Math.sqrt, and Math.random. (You should also know about the variable—not a method—Math.PI whose value is the double value that best approximates the value of π.)

• The following static Math methods—including what they do and when they are used—are part of the AP Java Quick Reference:

  • int abs(int x) — Returns the absolute value of an int value

  • double abs(double x) — Returns the absolute value of a double value

  • double pow(double base, double exponent) — Returns the value of the first parameter raised to the power of the second parameter

  • double sqrt(double x) — Returns the positive square root of a double value

  • double random() — Returns a double value greater than or equal to 0.0 and less than 1.0.

• Values returned from Math.random are in the range 0.0 to 1.0 but can be manipulated to produce a random int or double in any desired range by scaling (multiplying) and shifting (adding).

ArrayLists

• The ArrayList class is part of the java.util package and needs to be imported to be used in a class.

• An ArrayList object is mutable and contains object references.

• The no-argument ArrayList constructor constructs an empty list.

• Indices for an ArrayList start at 0 and end at size() − 1, inclusive.

• Trying to access an index outside the valid range (e.g. with the get, set or remove method) will cause an IndexOutOfBoundsException to be thrown.

• Changing the size of an ArrayList while traversing it using an enhanced for loop will cause a ConcurrentModificationException to be thrown. When using an enhanced for loop to traverse an ArrayList, you should not add or remove elements.

• ArrayListis a generic type which means we can write the type ArrayList<E> to mean an ArrayList that can only contain values of the type E. E.g. ArrayList<String> is a list of Strings.

• E is called a “type parameter” because it is filled in with a specific type like String. Type parameters have to be reference types.

• When ArrayList<E> is specified, the types of the parameters in methods that accept elements, e.g. add, and the return types of methods that return elements, e.g. get, will be E.

• The type ArrayList<E> is preferred over the so-called “raw” type ArrayList because it allows the compiler to find errors that would otherwise be found at run-time.

• Typically you invoke the ArrayList constructor as ArrayList<>(), i.e. with nothing between the <>s as the Java compiler will infer the correct element type.

• Iteration statements can be used to access all the elements in an ArrayList. This is called traversing the ArrayList.

• There are standard ArrayList algorithms that utilize traversals to insert and delete elements.

• Deleting elements during a traversal of an ArrayList requires using special techniques to avoid skipping elements.

• Most algorithms that work with arrays work equally well with ArrayLists after switching .length to .size() and array accesses and assignments to get and set calls.

• Some algorithms require multiple String, array, or ArrayList objects to be traversed simultaneously.

• The following ArrayList methods—including what they do and when they are used—are part of the AP Java Quick Reference:

  • int size() — Returns the number of elements in the list

  • boolean add(E obj) — Appends obj to end of list; returns true

  • void add(int index, E obj) — Inserts obj at position index which must be a valid index or the current size of the list, increasing the size of the list by one.

  • E get(int index) — Returns the element at position index in the list

  • E set(int index, E obj) — Replaces the element at position index with obj; returns the element formerly at position index.

  • E remove(int index) — Removes the element from position index, moving elements at position index + 1 and higher to the left, and decreases the size of the list by one. Returns the element formerly at position index.

Wrapper classes

• The College Board is weirdly obsessed with wrapper classes.

• The Integer, Double, and Boolean classes exist primarily because generic types like ArrayList can only use reference types as their type parameters. The wrapper classes exist to “wrap” a primitive value in an object so it can be put into an ArrayList or used with another generic class.

• In general you do not need to explicitly use wrapper classes because the Java compiler will automatically wrap a primitive type used in a context where its wrapper type is expected. This is called “autoboxing”. Conversely, if a wrapper type is used in a context where the corresponding primitive type is expected it will be automatically “unboxed” and converted to the primitive value.

• You will almost never write code where you declare the type of a variable or parameter or the return type of a method to be one of the wrapper types; just use primitive types and let autoboxing take care of things.

• Then one place you will have to use Integer and Double is when you declare an ArrayList: You have to write ArrayList<Integer> rather than ArrayList<int>, ArrayList<Double> rather than ArrayList<double> and ArrayList<Boolean> rather than ArrayList<boolean>.

• The following Integer constructors, methods, and variables—including what they do and when they are used—are part of the AP Java Quick Reference:

  • Integer(int value) — Constructs a new Integer object that represents the specified int value14. This is roughly equivalent to what happens when an int is autoboxed.

  • int intValue() — Returns the value of an Integer as an int. This is equivalent to what happens when an Integer is unboxed.

  • Integer.MAX_VALUE — The maximum value that can be represented by an int.

  • Integer.MIN_VALUE — The minimum value that can be represented by an int.

• The following Double constructor and method—including what they do and when they are used—are part of the AP Java Quick Reference:

  • Double(double value) — Constructs a new Double object that represents the specified double value15. This is roughly equivalent to what happens when a double is autoboxed.

  • double doubleValue() — Returns the value of a Double as a double. This is equivalent to what happens when a Double is unboxed.

• The College Board does not expect you to know about any methods from the Boolean class.

Algorithms

• We can compare algorithms informally by counting statement executions. For instance, sometimes it’s useful to analyze a loop to determine either exactly or approximately how many times it will execute its body. More rigorously we can characterize algorithms by how their run time grows as the size of the problem grows.

• There are standard algorithms to:

  • Compute statistics about numbers in an array or ArrayList such as the sum, average, minimum, and maximum value.

  • Determine if at least one element of an array or ArrayList has a particular property

  • Determine if all elements of an array or ArrayList have a particular property

  • Access all consecutive pairs of elements of an array or ArrayList.

  • Determine the presence or absence of duplicate elements in an array or ArrayList.

  • Determine the number of elements in an array or ArrayList meeting specific criteria

  • Shift or rotate elements of an array or ArrayList left or right.

  • Reverse the order of the elements of an array or ArrayList.

  • Determine the frequency with which a specific criterion is met by elements within an array or ArrayList

  • Identify the individual digits in an integer

• There are standard algorithms that utilize String traversals to:

  • Find if one or more substrings has a particular property

  • Determine the number of substrings that meet specific criteria

  • Create a new String with the characters reversed

• Sequential/linear search algorithms check each element in order until the desired value is found or all elements in the array or ArrayList have been checked. You should be able to write code that performs a linear search.

• Binary search algorithms can search sorted lists much more efficiently than linear search, finding elements in log N time where N is the size of the list. You are unlikely to need to write a binary search yourself for the exam.

• The binary search algorithm starts at the middle of a sorted array or ArrayList and on average eliminates half of the elements in each iteration until the desired value is found or all elements have been eliminated.

• The binary search algorithm can be written either iteratively or recursively.

• Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList. You should be able to recognize them but will not have to write them yourself.

• Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList. You will not have to be able to write a merge sort.

Recursion

• A recursive method is a method that calls itself.16

• Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.

• Each recursive call has its own set of local variables, including its parameters.

• Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.

• Recursion can be used to traverse linear structures like Strings, arrays, and ArrayLists but it is most useful for traversing tree structures which are difficult to traverse with simple loops.

• Any recursive solution can be replicated through the use of an iterative approach. However some recursions, such as tree recursions, will require maintaining extra data structures to keep track of the information that would otherwise be managed by the process of recursion.

Stuff the College Board just had to get off their chest

• System reliability is limited. Programmers should make an effort to maximize system reliability.

• Legal issues and intellectual property concerns arise when creating programs.

• The creation of programs has impacts on society, economies, and culture. These impacts can be beneficial and/or harmful.

• When using the computer, personal privacy is at risk. Programmers should attempt to safeguard personal privacy.