AP CS A Crib Notes

Basic Syntax

Arithmetic behaviour in Java for division and mod is to strip sign then do floored division.

Casting floating point to integer type rounds it in the direction of 0.

Else statements attaches to nearest unattached if.

if (X)
if (Y)
if (Z) a;
else b;
else c;

is equivalent to

if (X){
    if (Y){
        if (Z) a;
        else b;
    }
    else {
    	c;
    }
}

You can cast null to anything

Implicit casting only happens when:

default operations and functions arguments for primitive types, only can get upgraded
auto-boxing (int → Integer)
auto-unboxing (Integer → int)

Promotions for primitive types:

byte → short → int → long → float → double
char →int

Note that for implicit casting, values can only be promoted, they cannot be demoted unless they are explicitly cast.

All types get implicit casted to string using their toString() method when right-concatenating with a string. They cannot be cast to string using usual syntax.

In Java, only local primitive variables do not have default initializations. So Java enforces local primitive variables to be initialized at declaration. Most other things are default initialized to 0, "", or null or something similar.

Method overloading: same function name, different parameters. Note that primitive types can get promoted for methods in this order

widening (primitive types and classes)
boxing
variable arguments

Note that a method can only have at most 1 variable argument which must be the last argument

If there are multiple methods which a call can be promoted to, it seems that Java will send it to the minimum one, if the minimum one does not exist, it is a compile time error.

Java passes all function arguments by value.

If a function in Java is not void, the program logic but guarantee that there will be a return value or else it will be a compile error.

Classes

A is-a B: A is a child class of B, A extends B A has-a B: A contains some variables of B

access levels:

private: class
(none): package
protected: subclass
public: world

Only if there are no constructors, Java will implicit make a default constructor with no arguments.

For child class constructors, a super call must be the first call. If super is not called in the constructor, an implicit super() will be called at the start.

Method overridding: same function name and parameters in child class

Polymorphism: if A is a child of B, and B overrided a method of A, an object of B stored in variable of A will called the B’s overrided method instead of A’s original method. Note that polymorphism happens even if the method is called from inside object A. Note that if A does not define the method, it will result in a compile time error.

Standard Library

In Math library, basically everything is static

double Math.pow(double base, double exp)
double Math.sqrt(double x)
double Math.random(): $[0,1]$

a.compareTo(b):

$<0$ if $a<b$
$0$ if $a=b$
$>0$ if $a>b$

Integer class:

required cause ArrayList cant hold primitive types
construct using new Integer(x) or Integer.valueOf(x)
obj.intValue() to get value of int
cannot do set, increment, or do binary operations (+,-,*,/) directly, need to cast to int then reconvert to Integer
x.equals(y) for value comparison, cannot use ==
can do inequality comparisons, and Java will auto-unbox to int
caches values -128 to 127 that are used when auto-boxing, or defined from valueOf

String class:

s.indexOf(t), return first occurance of t in s, or $-1$ is t not in s
s.substrng(s) $[s,)$
s.substring(s,e) $[s,e)$

Java common RTEs:

division by 0 (for int only)
casting into a non-parent class
array out of bound
negative array size
storing wrong datatype in array. Usually this will be caught at compile time. A case where it would not be caught is suppose A and B are different classes. Then an array of type A is stored as an array of type parent(A,B), then there will be a type mismatch.

Array syntax: Obj[] arr = new Obj[len]

arr[idx]
arr.length

Arraylist syntax: ArrayList<Obj> arr = new ArrayList<Obj>()

get(idx)
add(val), append back
add(idx, val)
set(idx, val)
remove(idx)
clear()
size()

Recursion

A recursive algorithm can always be written iteratively. In recursion, a function is defined in terms of a simpler case of itself.

Tail recursion is when the recursive call of the method is made at the last step of the method.

Sorting and Searching

Insertion sort:

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

Selection sort:

for i in 0 to length(A)-1
    jmin ← i
    for j in i+1 to length(A)	
    	if a[j]<a[jmin]
    		jmin ← j
    	end if
    end for
    swap(a[i],a[jmin])
end for

Program Design and Analysis

Iterative development process: create working prototype and imrpove it Incremental development proces: break program into small pieces and make sure each piece works before adding the rest A single program is usually developed using spectrum of above 2 methods

Top-down programming: write in terms of the operations to be performed and then refine by adding more detail Bottom-down programming: write and test the lowest level methods first and then combine them to form more abstract operations

Phases of program development:

investigation and reflection: get program specs agreed by all parties, if in doubt check with client
design code: details how to establish goals of program

What should influence choice of algorithm:

ML
TL
ease that it can be understood

Robustness: ability of program to handle all data (including extreme values) correctly

Precondition of a method: describe the condition that must be true when method is called

Program documentation: description of how program works

document a program by breaking it down and explaining it, allows for easier collaboration
one of the most common forms is comments

Croatian Olympiad in Informatics 2024

Bought Entire Series of はなにあらし