AP Computer Science A

An algorithm 算法 is a finite, step-by-step procedure that solves a problem. A program 程序 expresses an algorithm in a language a computer can run. Java is compiled 编译: the compiler 编译器 translates your source code into bytecode, which the Java Virtual Machine (JVM) runs. A syntax error 语法错误 (breaking the grammar) is caught by the compiler; a logic error 逻辑错误 (wrong result) is not – the program runs but misbehaves.

A compiler translates the whole program at once; an interpreter runs it line by line

A variable 变量 is a named box that stores a value of a fixed type 类型. Java's main primitive types 基本类型 are int (whole numbers), double (decimals), and boolean (true/false). Declare with the type first:

Java's basic data types, each storing a different kind of value

int score = 90;
double price = 4.99;
boolean passed = true;

An expression 表达式 combines values and operators to compute a result: + - * / and % (modulus 取模, the remainder). Integer division truncates: 7 / 2 is 3, while 7 % 2 is 1. Operator precedence follows math (*,/,% before +,-). Print with:

System.out.print("no newline");
System.out.println("with newline");

An assignment 赋值 x = expr; evaluates the right side and stores it in the left variable. Read input with a Scanner:

Scanner in = new Scanner(System.in);
int age = in.nextInt();
String name = in.next();

Each type has a fixed range; an int overflows past about 2.1 billion. Casting 类型转换 converts between types. Widening (int to double) is automatic; narrowing needs an explicit cast, which truncates (does not round):

double avg = (double) total / count;   // force real division
int whole = (int) 3.9;                 // 3, truncated

Exam skill: watch for integer division producing a truncated result when a decimal was expected – cast one operand to double first.

Worked example. Trace each expression:

• 7 / 2 → 3 (both int, so division truncates);
• 7.0 / 2 → 3.5 (one double forces real division);
• 7 % 2 → 1 (the remainder);
• (double) 7 / 2 → 3.5 (the cast binds tighter than /, so it is 7.0 / 2);
• (double) (7 / 2) → 3.0 (the parentheses compute 7 / 2 = 3 in int first, then widen).

The last two look alike but differ – the position of the cast decides whether the truncation happens.

Shorthands combine an operation with assignment: x += 5 means x = x + 5; likewise -=, *=, /=, %=. The increment and decrement operators x++ and x-- add or subtract one.

An API (Application Programming Interface) 应用程序接口 is the published list of classes and methods you may use. A library 库 is a collection of ready-made classes (like Math, String, Scanner). You read the API documentation to learn what a method needs (its parameters) and returns, without seeing its inner code – an example of abstraction 抽象.

Comments 注释 are ignored by the compiler but explain code to humans: // for a single line, /* ... */ for a block, and /** ... */ for a Javadoc comment that documents a method's purpose, parameters, and return value. Precise preconditions and postconditions are written here.

A method signature 方法签名 is a method's name plus its parameter types, e.g. nextInt() or substring(int, int). To call a method you must supply arguments 实参 that match the parameters in number, type, and order. The signature also states the return type – the type of value the method gives back (void if none).

A class (static) method 类方法 belongs to the class itself, so you call it on the class name: ClassName.method(args). No object is needed.

The Math class provides static math methods: Math.abs(x), Math.pow(base, exp), Math.sqrt(x), and Math.random() (a double in $[0,1)$). To get a random integer from 0 to n-1: (int)(Math.random() * n).

A class 类 is a blueprint; an object 对象 is a concrete instance 实例 built from it. A class bundles data (fields) with behavior (methods) – the heart of object-oriented programming 面向对象编程. String, Scanner, and ArrayList are all classes you instantiate.

A class diagram: private attributes and public methods

A class is a blueprint; each object is one instance built from it

Instantiation 实例化 creates an object with the new keyword, which calls a constructor 构造函数:

Scanner in = new Scanner(System.in);
String s = new String("hi");   // or just "hi"

The variable holds a reference 引用 (the object's address), not the object itself. Two references can point to the same object; comparing them with == compares addresses, not contents.

A primitive variable holds its value directly, a reference holds an arrow to the object

An instance method 实例方法 acts on a specific object, so you call it on the object reference: object.method(args). Example: in.nextInt(), word.length().

String objects are immutable 不可变 – methods return a new string rather than changing the original. Key methods (all indices start at 0):

s.length();            // number of characters
s.substring(2, 5);     // chars at index 2,3,4 (5 excluded)
s.indexOf("ab");       // first position, or -1
s.equals(other);       // content comparison (never use == for Strings)
s.compareTo(other);    // <0, 0, >0 by dictionary order

Exam skill: substring(a, b) includes index a but excludes b, and String comparison must use .equals, not == – two of the most-tested String pitfalls.

Worked example. Let String s = "COMPUTER"; (indices 0–7). Then s.length() is 8; s.substring(0, 4) is "COMP" (indices 0,1,2,3 – index 4 excluded); s.substring(4) is "UTER" (from index 4 to the end); s.indexOf("PU") is 3; and s.indexOf("X") is -1 (not found). Counting the excluded endpoint of substring is the single most common slip.

String indices start at 0

• Trace code by hand line by line, tracking each variable's value in a table — the exam rewards careful tracing over guessing.
• Know Java's primitive types and that integer division truncates ($7/2$ gives $3$); use a cast or a double for real division.
• Distinguish compile-time errors (syntax, types) from run-time errors (divide by zero, null) and logic errors (wrong output).
• Follow operator precedence and initialise every variable before you use it.
• On the free-response, write complete, compilable Java — return the right type and match the method header exactly.

Algorithms are built from three control structures 控制结构: sequence (steps in order), selection 选择 (choosing a path), and iteration 迭代 (repeating steps). This topic covers selection and iteration – the tools that let a program make decisions and loop.

The three control structures: sequence, selection, and iteration

A boolean expression 布尔表达式 evaluates to true or false, using relational operators 关系运算符: == (equal), != (not equal), <, >, <=, >=. Note == compares primitive values but object references for objects, so use .equals for Strings.

The three families of operators: arithmetic, relational, and logical

An if statement 条件语句 runs a block only when its condition is true; an optional else gives an alternative:

if (score >= 60) {
    System.out.println("Pass");
} else {
    System.out.println("Fail");
}

Placing an if inside another, or chaining with else if, tests several cases in order. Only the first matching branch runs:

if (g >= 90) grade = 'A';
else if (g >= 80) grade = 'B';
else grade = 'C';

Logical operators 逻辑运算符 combine conditions: && (and – both true), || (or – at least one true), ! (not – reverse). Java uses short-circuit evaluation 短路求值: && stops if the left side is false, and || stops if the left side is true – useful to guard against errors, e.g. if (n != 0 && total / n > 5).

De Morgan's laws 德摩根定律 rewrite negations: !(a && b) equals !a || !b, and !(a || b) equals !a && !b. Two boolean expressions are equivalent if they give the same result for every input – a truth table proves it. Simplifying conditions this way is a common exam task.

A while loop 循环 repeats while its condition stays true, testing before each pass. You must change something inside so the loop eventually stops, or it becomes an infinite loop 无限循环:

The three loop types differ in where the condition is tested

int i = 0;
while (i < 5) {
    System.out.println(i);
    i++;
}

A for loop packs initialization, condition, and update into one line – best when you know the count:

for (int i = 0; i < n; i++) {
    // runs n times, i = 0..n-1
}

A for and an equivalent while do the same work; be able to convert between them.

Combine loops and conditions to solve real problems – count, sum, find a maximum, or test a property:

int max = arr[0];
for (int k = 1; k < arr.length; k++) {
    if (arr[k] > max) max = arr[k];
}

Standard patterns like a running total, a counter, or a flag 标志 (a boolean that records whether something happened) recur throughout the course.

Loop through a string by index to process each character:

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // count vowels, reverse, check for a substring, ...
}

Typical tasks: count occurrences, build a reversed or filtered copy, or test whether one string contains another.

A nested loop 嵌套循环 puts one loop inside another; the inner loop completes fully for each pass of the outer. If the outer runs $n$ times and the inner $m$ times, the body runs $n\times m$ times – the basis for processing grids and comparing all pairs.

Run-time analysis 运行时间分析 counts how many basic steps an algorithm takes as the input size $n$ grows. Count the executions of the innermost statement: a single loop over $n$ items is linear ($n$ steps); two nested loops over $n$ are quadratic ($n^2$). This informal counting lets you compare two algorithms' efficiency.

How the running time grows with the number of elements n

Exam skill: for a nested loop, be able to state how many times the inner statement runs in terms of the loop bounds – a frequent multiple-choice question.

Worked example. How many stars does this print?

for (int i = 0; i < 4; i++)
    for (int j = 0; j < i; j++)
        System.out.print("*");

The inner loop runs i times for each outer i: 0 + 1 + 2 + 3 = 6 stars. When the inner bound is the outer variable, the total is the triangular sum $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ – here $\dfrac{4\times3}{2}=6$ – not the full $n^2=16$ of a rectangular nested loop.

• Get boundary conditions right: use < vs <= deliberately, and watch the first and last iteration of every loop (off-by-one is the classic bug).
• Build compound conditions with &&, ||, ! and remember short-circuit evaluation (put the null check first).
• Trace nested loops by counting how many times the inner body runs in total.
• Choose the right structure — if/else if for ranges, a loop for repetition — and avoid an infinite loop by updating the loop variable.
• Apply De Morgan's laws when you simplify or negate a boolean condition.

Abstraction 抽象 means hiding detail behind a simple interface – you use a String without knowing how it stores characters. Good design breaks a problem into classes, each responsible for one idea. This topic is about writing your own classes.

Decomposing a program into modules and sub-modules

Design choices affect whether code is correct, readable, and reusable. Encapsulation 封装 – keeping data private and exposing it only through methods – protects an object's state from misuse and lets you change the inside without breaking users of the class. Thoughtful naming, single-purpose methods, and testing reduce bugs.

A class has three parts: instance variables 实例变量 (fields – the object's data), constructors (build objects), and methods (behavior). Fields are usually private; methods are usually public:

A class diagram: private attributes and public methods

public class Student {
    private String name;      // instance variable
    private int score;

    public Student(String n, int s) {   // constructor
        name = n;
        score = s;
    }
    public int getScore() { return score; }   // accessor
}

A constructor 构造函数 has the same name as the class and no return type. It runs when you write new, and its job is to initialize the fields. A class can have several constructors with different parameter lists (overloading 重载); a no-argument constructor sets defaults.

A method has a signature, a return type, and a body. An accessor (getter) 访问器 returns information without changing the object; a mutator (setter) 修改器 changes a field. A method returning a value must have a return of the right type on every path; a void method returns nothing.

public void setScore(int s) { score = s; }   // mutator
public String toString() { return name + ": " + score; }

When you pass an object to a method, Java copies the reference, so the method acts on the same object – changes to its fields are visible to the caller. (Primitives are copied by value, so changes to them are not.) A method can also return a reference to an object. Because a String is immutable, passing one is safe; passing a mutable object lets a method change it.

Pass by value gives a copy; pass by reference lets the method change the original

Exam skill: know that mutating an object's fields inside a method affects the original, but reassigning the parameter (param = new...) does not affect the caller.

Worked example. Suppose s is a Student with score 50, and we call tweak(s):

public static void tweak(Student a) {
    a.setScore(100);          // (1) mutates the shared object
    a = new Student("Z", 0);  // (2) repoints the local copy only
    a.setScore(5);            // (3) changes only the new local object
}

Line (1) changes the object s points to, so the caller now sees 100. Line (2) makes the method's own copy of the reference point at a fresh object – the caller's s is untouched – and line (3) affects only that new object. After the call, s.getScore() is 100: the mutation stuck, the reassignment did not.

A static (class) variable 类变量, marked static, is shared by all objects of the class – one copy total (e.g. a counter of how many objects exist). A static method belongs to the class and cannot use instance fields directly. Access them by class name: Student.getCount().

Scope 作用域 is where a name is visible. A local variable declared in a method exists only inside it; a parameter exists only in its method; an instance variable is visible throughout the object. Access modifiers control visibility across classes: private (this class only) versus public (anywhere). Local variables shadow fields of the same name – a source of bugs.

A global variable is visible everywhere; a local variable only inside its block

this is a reference to the current object. Use it to tell a field apart from a parameter with the same name, or to call another method of the same object:

public Student(String name, int score) {
    this.name = name;      // this.name is the field; name is the parameter
    this.score = score;
}

Exam skill: when a constructor or setter's parameter has the same name as a field, you must write this.field = param – without this, the assignment does nothing useful.

• Design with methods and classes: encapsulate data as private fields and expose behaviour through public methods.
• Know the difference between an object and its class, and that objects are passed by reference (a method can change the object's state).
• Traverse arrays and ArrayLists safely — size is length vs .size(), and removing during a loop shifts indices.
• Write and trace a recursive method: find the base case first, then check the recursive call moves toward it.
• Use inheritance and polymorphism (override, super) so the right method runs at run time.

Programs that gather data raise questions of privacy 隐私 and consent 同意. Collect only what is needed, protect it, and be honest about its use. Data can carry bias 偏见 if it does not represent everyone fairly, leading to unfair results – a responsibility that comes with storing information.

A single variable holds one value; real problems need to store many related values – a class roster, pixels, sensor readings. A data structure 数据结构 organizes a collection so we can store, find, and process items efficiently. The AP course uses three: the array, the ArrayList, and the 2D array.

An array 数组 is a fixed-size, ordered collection of same-type values. Indices run from 0 to length - 1:

A one-dimensional array (a list) with its indices and bounds

int[] nums = new int[5];        // five zeros
int[] vals = {3, 1, 4, 1, 5};   // initialized
int first = vals[0];            // 3
int n = vals.length;            // 5 (a field, not a method)

Accessing an index outside 0..length-1 throws an ArrayIndexOutOfBoundsException.

Traverse 遍历 an array with a for loop (gives the index) or an enhanced for / for-each loop (gives each value, read-only):

for (int i = 0; i < a.length; i++) { a[i] *= 2; }   // can modify
for (int v : a) { System.out.println(v); }          // read each value

Master these patterns: compute a sum or average, find the max/min, count items meeting a condition, check for a duplicate, and reverse or shift elements. Each is a traversal with a running result:

int sum = 0;
for (int v : a) sum += v;
double avg = (double) sum / a.length;

A Scanner can read a file line by line, using hasNext... to test before reading:

Scanner f = new Scanner(new File("data.txt"));
while (f.hasNextLine()) {
    String line = f.nextLine();
}

An ArrayList stores objects, not primitives, so a primitive is wrapped in an object: Integer wraps int, Double wraps double. Java does this with autoboxing 自动装箱 (int to Integer) and unboxing (back again) automatically, so you can write list.add(5) and int x = list.get(0).

An ArrayList 动态数组 grows and shrinks as you add or remove items. Declare it with the element type in <>:

ArrayList<String> names = new ArrayList<String>();
names.add("Amy");           // append
names.add(0, "Bob");        // insert at index
names.get(0);               // read
names.set(1, "Cara");       // replace
names.remove(0);            // delete, shifts the rest left
names.size();               // count (a method, unlike array.length)

Traverse with an index loop or a for-each loop, just like arrays (use size() and get(i)):

for (int i = 0; i < list.size(); i++) { ... list.get(i) ... }
for (String s : list) { ... }

Exam skill: when removing items in an index loop, either loop backwards or do not increment i after a removal – otherwise removing shifts elements left and you skip one.

The same algorithms as arrays – max/min, count, sum – plus insertion and deletion that arrays cannot do easily. A common task is to remove all elements matching a condition, handling the index-shift carefully.

A 2D array 二维数组 is a grid (rows and columns) – an array of arrays:

A two-dimensional array (a table) with row and column indices

int[][] grid = new int[3][4];   // 3 rows, 4 columns
grid[r][c] = 7;                 // row r, column c
int rows = grid.length;         // 3
int cols = grid[0].length;      // 4

Visit every cell with nested loops – the outer over rows, the inner over columns (row-major order 行主序):

for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++)
        System.out.print(grid[r][c]);

Typical grid tasks: sum a row or column, find the max in the grid, count matching cells, or sum a diagonal (where r == c). Each is a nested traversal with a running result.

• Linear search 线性搜索 checks each element in turn – works on any list, taking up to $n$ steps.
• Binary search 二分搜索 works only on a sorted list: check the middle, then discard the half that cannot contain the target, repeating. It takes about $\log_2 n$ steps – far faster on large data.

Binary search halves the range at each step

Linear search checks every element in turn until the target is found

int lo = 0, hi = a.length - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

Exam skill: binary search requires sorted data; know how many comparisons it makes and how lo, hi, mid update.

Worked example. Search for target = 40 in the sorted array {3, 9, 14, 23, 31, 42, 55} (indices 0–6). Start lo=0, hi=6:

• mid = (0+6)/2 = 3, a[3]=23 < 40, so lo = 4;
• mid = (4+6)/2 = 5, a[5]=42 > 40, so hi = 4;
• mid = (4+4)/2 = 4, a[4]=31 < 40, so lo = 5;
• now lo (5) > hi (4), so the loop ends – 40 is not present.

Each step halved the range, so even this miss took only three comparisons.

• Selection sort 选择排序 repeatedly finds the smallest remaining element and swaps it into place.
• Insertion sort 插入排序 grows a sorted front, inserting each new element where it belongs.

An insertion sort, shifting each key into place pass by pass

Both are simple and take about $n^2$ steps on average – fine for small arrays. Be able to trace the array after each pass.

Recursion 递归 is a method that calls itself on a smaller input. It needs a base case 基本情况 that stops the calls, and a recursive case that moves toward the base:

public static int factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

Without a reachable base case, recursion never stops (a stack overflow).

Recursion powers efficient algorithms. Binary search can be written recursively (search the correct half). Merge sort 归并排序 splits the array in half, sorts each half recursively, then merges the two sorted halves – taking about $n\log_2 n$ steps, much faster than selection or insertion sort on large data.

Merge sort splits the array to single elements, then merges sorted halves back up

Worked example. Trace factorial(4). Each call defers to a smaller one: factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1) hits the base case and returns 1, so the calls unwind inward: 2 * 1 = 2, then 3 * 2 = 6, then 4 * 6 = 24. Writing each call above its returned value is the reliable way to trace recursion.

Exam skill: trace a recursive method by writing out each call and its return value, and know that merge sort's efficiency ($n\log n$) beats the $n^2$ simple sorts.

• Weigh both benefits and harms of collecting data — this unit is tested through short written justification, not code.
• Protect personally identifiable information (PII) and explain privacy and security risks in context.
• Name real harms: data breaches, surveillance, and algorithmic bias from unrepresentative data.
• Respect intellectual property and licensing when you reuse code or data.
• Give a specific, reasoned answer — a vague "it could be bad" earns no marks.