AP® Computer Science A Lecture 3

Presented by TU RUIXUAN
Copyright © TU RUIXUAN, All Rights Reserved
Tailored for College Board® Advanced Placement® Program
According to Course and Exam Description Effective Fall 2020

Contents (AP CED Equivalent)

Unit 2: Using Objects (including 2.6, 2.7, 2.8, 2.9)
Unit 3: Boolean Expressions and if Statements (including 3.5, 3.6, 3.7)
Unit 4: Iteration (including 4.3)
Unit 6: Array
Unit 7: ArrayList
Unit 8: 2D Array
Unit 9: Inheritance (including 9.7)
Unit 10: Recursion

Topics

T 3.1: `String` Objects

String str = 50 + 30 + "String" + 40 + 40;
System.out.println(str); // 80String4040

str = "a" + "b"; // ab
str += "c"; // abc

str = "\""; // "
str = "\\"; // \
str = "\n"; // new line

T 3.2: `String` Methods

Range: 0 to length-1 or IndexOutOfBoundsException

int a = 1;
str s = a.toString() // "1"

String(String str);
int length();
String substring(int from, int to);
String substring(int from);
int indexOf(String str);
boolean equals(String other);
int compareTo(String other); // 0: equal, other: not equal
char charAt(int index);

T 3.3: Wrapper Classes: `Integer` and `Double`

Integer(int value)
Integer.MIN_VALUE // -2147483648
Integer.MAX_VALUE // 2147483647
int intValue()

Double(double value)
double doubleValue()

T 3.4: Using the `Math` Class

import static java.lang.Math.*;

int abs(int x); // integer abstract value
double abs(double x); // decimal abstract value
double pow(double base, double exponent); // decimal power
double sqrt(double x); // decimal square root
double random(); // random decimal [0, 1)

T 3.5: `Object` Superclass

boolean equals(Object other)
String toString()

T 3.6: More Object References

Object reference values can be compared, using == and !=, to identify aliases.

A a = new A();
A b = a;
A c = new A();
A d = a;
A f = c;
A e;
b == d; // true
b == c; // false
b == e; // false
e == null; // true

T 3.7: Array Creation and Access

Creation

int[] a = {1, 2, 3, 4, 5};
int[] b = new int[20];

Default values

int: 0
double: 0.0
boolean: false
reference: null

Access

a[0]; // 1
a[2]; // 3
// a[5]; // ERROR: ArrayIndexOutOfBoundsException

T 3.9: `for` Loop (2)

for (type element : collection) {
    System.out.println(element); // use element
}

T 3.10: Compound Boolean Expressions

Logical operators:

!: NOT
&&: AND
||: OR

Short-circuit evaluation: the second argument is executed or evaluated only if the first argument does not suffice to determine the value of the expression: when the first argument of the AND function evaluates to false, the overall value must be false; and when the first argument of the OR function evaluates to true, the overall value must be true

T 3.8: Traversing Arrays

for (int i = 0; i < 20; i++) {
    System.out.println(b[i]);
}

T 3.11: Equivalent Boolean Expressions

This topic is not included in AP

Definitions:

$0$ : FALSE
$1$ : TRUE
$x\cdot y$ : $x$ AND $y$
$x+y$ : $x$ OR $y$
$\overline x$ : NOT $x$

$\darr$ Boolean algebra laws (part) $\darr$

Boolean algebra laws (part) P1/2

$x+y=y+x$
$x \cdot y = y \cdot x$
$(x + y) + z$ = $x + (y + z)$
$x \cdot (y \cdot z) = (x \cdot y) \cdot z$
$x +x = x$
$x \cdot x = x$
$x + 1 = 1$
$x \cdot 0 = 0$
$x + 0 = x$
$x \cdot 1 = x$
$x + \overline{x} = 1$

$\darr$ Boolean algebra laws (part) $\darr$

Boolean algebra laws (part) P2/2

$x \cdot \overline{x} = 0$
$x+x y = x$
$x +\overline{x}y = x + y$
$x (x+y) = x$
$x \cdot (y + z) = xy + xz$
$(x+y) \cdot (p + q) = xp + xq +yp + yq$
$(x+y)(x+z)=x + yz$
$\overline{x+y} = \overline{x} \cdot \overline{y}$
$\overline{x \cdot y} = \overline{x} + \overline{y}$
$\overline{\overline{x}} = x$

$\darr$ Truth tables $\darr$

Truth tables (© ACSL)

Find all orderd pairs $(A,B)$ that make the following expression true: $\overline{ \overline{(A+B)} + \overline{A}B }$

#1	#2	#3	#4	#5	#6	#7	#8
-	-	OR of Col#1, Col#2	NOT of Col#3	NOT of Col#1	ADD of Col#1, Col#2	OR of Col#4, Col#6	NOT of Col#7
$A$	$B$	$A+B$	$\overline{A+B}$	$\overline{A}$	$\overline{A}B$	$\overline{A+B} + \overline{A}B$	$\overline{\overline{A+B} + \overline{A}B}$
0	0	0	1	1	0	1	0
0	1	1	0	1	1	1	0
1	0	1	0	0	0	0	1
1	1	1	0	0	0	0	1

T 3.12: Introduction to `ArrayList`

ArrayList a = new ArrayList<E>(); // preferable
ArrayList b = new ArrayList();

T 3.13: `ArrayList` Methods

int size()
boolean add(E obj) // true
void add(int index, E obj) // insert at index
E get(int index)
E set(int index, E obj)
E remove(int index)

T 3.14: Traversing ArrayLists

Similar to arrays

Exceptions:

ConcurrentModificationException: size of ArrayList changes in loop
ArrayIndexOutOfBoundsException

T 3.15: 2D Arrays

int[][] a = new int[20][20];
x = sc.nextInt(); y = sc.nextInt();
a[x][y] = 1;
x = sc.nextInt(); y = sc.nextInt();
if (a[x][y] == 1) System.out.println("Exist");

T 3.16: Recursion

int rec(int x) {
    if (x == 0) return 0;
    if (x == 1) return 1;
    return rec(x - 1) + x;
}

int val = rec(10); // 55

T 3.17: Complexity

As the amount of resources required to run an algorithm generally varies with the size of the input, the complexity is typically expressed as a function $n \rarr f(n)$ , where $n$ is the size of the input and $f(n)$ is either the worst-case complexity (the maximum of the amount of resources that are needed over all inputs of size $n$ ) or the average-case complexity (the average of the amount of resources over all inputs of size $n$ ).

Time complexity: the number of required elementary operations on an input of size $n$ , where elementary operations are assumed to take a constant amount of time on a given computer and change only by a constant factor when run on a different computer
Space complexity: the amount of memory required by an algorithm on an input of size $n$
Symbols: Best $\Omega$ , Average $\Theta$ , Worst $O$

T 3.18.1: Linear Searching

$\Omega(1)$ , $\Theta(n)$ , $O(n)$

Guess a integer $n$ between 1 and 100

int judge(int x); // 0: x < n, 1: x = n, 2: x > n
int guess() {
    int a = 1;
    while (judge(a) != 1) {
        if (judge(a) == 0) a++;
        else a--;
    }
    return a;
}

T 3.18.2: Binary Searching

$\Omega(1)$ , $\Theta(\log n)$ , $O(\log n)$

Guess a integer $n$ between 1 and 100

int judge(int x); // 0: x < n, 1: x = n, 2: x > n
int guess() {
    int a = 50;
    while (judge(a) != 1) {
        if (judge(a) == 0) a += (a / 2);
        else a -= (a / 2);
    }
    return a;
}

T 3.19.1: Bubble Sort

$\Omega(n)$ , $\Theta(n^2)$ , $O(n^2)$

The implementation (© GeeksforGeeks) is not included in AP

void bubbleSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1]) {
                // swap arr[j + 1] and arr[j]
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}

T 3.19.2: Selection Sort

$\Omega(n^2)$ , $\Theta(n^2)$ , $O(n^2)$

The implementation is not included in AP

void selectionSort(int arr[]) { 
    int n = arr.length; 

    // One by one move boundary of unsorted subarray 
    for (int i = 0; i < n - 1; i++) { 
        // Find the minimum element in unsorted array 
        int min_idx = i; 
        for (int j = i + 1; j < n; j++) 
            if (arr[j] < arr[min_idx]) 
                min_idx = j; 

        // Swap the found minimum element with the first element 
        int temp = arr[min_idx]; 
        arr[min_idx] = arr[i]; 
        arr[i] = temp; 
    } 
}

T 3.19.3: Insertion Sort

$\Omega(n)$ , $\Theta(n^2)$ , $O(n^2)$

The implementation (© GeeksforGeeks) is not included in AP

void insertionSort(int arr[]) { 
    int n = arr.length; 
    for (int i = 1; i < n; ++i) { 
        int key = arr[i]; 
        int j = i - 1; 

        /* Move elements of arr[0..i-1], that are greater than key,
           to one position ahead of their current position */
        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
}

T 3.19.4: Merge Sort

$\Omega(n \log n)$ , $\Theta(n \log n)$ , $O(n \log n)$

The implementation is not included in AP

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r) {
    // Find sizes of two subarrays to be merged
    int n1 = m - l + 1;
    int n2 = r - m;

    /* Create temp arrays */
    int L[] = new int[n1];
    int R[] = new int[n2];

    /* Copy data to temp arrays */
    for (int i = 0; i < n1; ++i)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[m + 1 + j];

    /* Merge the temp arrays */

    // Initial indexes of first and second subarrays
    int i = 0, j = 0;

    // Initial index of merged subarry array
    int k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy remaining elements of L[] if any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy remaining elements of R[] if any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Main function that sorts arr[l..r] using merge()
void sort(int arr[], int l, int r)
{
    if (l < r) {
        // Find the middle point
        int m = (l + r) / 2;

        // Sort first and second halves
        sort(arr, l, m);
        sort(arr, m + 1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}

T 3.19.5: Quick Sort

$\Omega(n \log n)$ , $\Theta(n \log n)$ , $O(n^2)$

The implementation is not included in AP

/* This function takes last element as pivot,
   places the pivot element at its correct position in sorted array, and
   places all smaller (smaller than pivot) to left of pivot and
   all greater elements to right of pivot */
int partition(int arr[], int low, int high) { 
    int pivot = arr[high];  
    int i = (low - 1); // index of smaller element 
    for (int j = low; j < high; j++) { 
        // If current element is smaller than the pivot 
        if (arr[j] < pivot) { 
            i++; 

            // swap arr[i] and arr[j] 
            int temp = arr[i]; 
            arr[i] = arr[j]; 
            arr[j] = temp; 
        } 
    } 

    // swap arr[i+1] and arr[high] (or pivot) 
    int temp = arr[i + 1]; 
    arr[i + 1] = arr[high]; 
    arr[high] = temp; 

    return i + 1; 
}

/* The main function that implements QuickSort() 
    arr[] --> Array to be sorted, 
    low  --> Starting index, 
    high  --> Ending index */
void sort(int arr[], int low, int high) { 
    if (low < high) { 
        /* pi is partitioning index, arr[pi] is  
            now at right place */
        int pi = partition(arr, low, high); 

        // Recursively sort elements before 
        // partition and after partition 
        sort(arr, low, pi - 1); 
        sort(arr, pi + 1, high); 
    } 
}

Homework

H 3.1: Fibonacci

Expression: $F(x)=F(x-1)+F(x-2)\quad (F(0)=0,F(1)=1)$
Input: a number indicates the number of fibonacci numbers required, and the next line contains the exact numbers that are required
Output: a sequence of numbers indicates the required numbers

$\darr$ Sample $\darr$

Sample Input:

5
1 2 3 4 1000

Sample Output:

1 1 2 3 1556111435

H 3.2: Graph

Input: one number indicating the count of coefficients required, two numbers indicating the weight and the height of each quadrant, and several numbers containing the coefficients from the first term to the last term
Output: a graph of the function entered with the origin, parameters playing a role in size, and the increasing (/), decreasing (\) or constant (-) trend of it

$\darr$ Sample $\darr$

Sample Input #1
The following input means to draw a 20*20 graph of $y=x-1$

2 10 10 1 -1

Sample Output #1 (SCROLL)

$\darr$ Sample $\darr$

Sample Input #2

The following input means to draw a 20*20 graph of $y=x^2+2x+3$

3 10 10 1 2 3

Sample Output #2 (SCROLL)

Thanks for Watching

AP® Computer Science A Series

AP® Computer Science A Lecture 3

Contents (AP CED Equivalent)

Topics

T 3.1: String Objects

T 3.2: String Methods

T 3.3: Wrapper Classes: Integer and Double

T 3.4: Using the Math Class

T 3.5: Object Superclass

T 3.6: More Object References

T 3.7: Array Creation and Access

T 3.9: for Loop (2)

T 3.10: Compound Boolean Expressions

T 3.8: Traversing Arrays

T 3.11: Equivalent Boolean Expressions

Boolean algebra laws (part) P1/2

Boolean algebra laws (part) P2/2

Truth tables (© ACSL)

T 3.12: Introduction to ArrayList

T 3.13: ArrayList Methods

T 3.14: Traversing ArrayLists

T 3.15: 2D Arrays

T 3.16: Recursion

T 3.17: Complexity

T 3.18.1: Linear Searching

T 3.18.2: Binary Searching

T 3.19.1: Bubble Sort

T 3.19.2: Selection Sort

T 3.19.3: Insertion Sort

T 3.19.4: Merge Sort

T 3.19.5: Quick Sort

Homework

H 3.1: Fibonacci

H 3.2: Graph

Thanks for Watching

T 3.1: `String` Objects

T 3.2: `String` Methods

T 3.3: Wrapper Classes: `Integer` and `Double`

T 3.4: Using the `Math` Class

T 3.5: `Object` Superclass

T 3.9: `for` Loop (2)

T 3.12: Introduction to `ArrayList`

T 3.13: `ArrayList` Methods