Data Analysis | AP - Wyatt's Notes

A fixed-size, ordered collection of elements of the same type.

Java:

int[] scores = new int[10];
int[] nums = {3, 1, 4, 1, 5, 9};

• Index from 0 to length - 1.
• $O(1)$ access by index.
• $O(n)$ search (unsorted), $O(\log n)$ search (sorted, binary search).
• Insertion and deletion are $O(n)$ (requires shifting elements).

Common pitfalls with arrays:

• ArrayIndexOutOfBoundsException when accessing an index outside the valid range.
• The length of a Java array is fixed after creation.
• Java initializes all array elements to default values: 0 for integers, null for objects.

Traversing and processing:

int[] scores = {85, 92, 78, 95, 88};
int sum = 0;
int max = scores[0];
int min = scores[0];
for (int s : scores) {
    sum += s;
    if (s > max) max = s;
    if (s < min) min = s;
}
double average = (double) sum / scores.length;

A resizable array from the java.util package.

ArrayList<String> names = new ArrayList<String>();
names.add("Alice");
names.add("Bob");
names.add(1, "Charlie");
String s = names.get(0);
names.set(0, "Alicia");
names.remove(2);
int size = names.size();
boolean found = names.contains("Bob");
int index = names.indexOf("Alice");

Array vs ArrayList:

Arrays of arrays, useful for grids, matrices, and tables.

Java:

int[][] grid = new int[3][4];
int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

• grid[row][col]: row-major order.
• grid.length: number of rows.
• grid[0].length: number of columns.

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

1. Filtering: Selecting data that meets criteria.
2. Mapping/Transforming: Applying a function to each element.
3. Reducing/Aggregating: Combining data into a summary (sum, average, max, min).
4. Sorting: Arranging data in a specific order.

PROCEDURE findMin(list)
{
    min <- list[1]
    FOR EACH item IN list
    {
        IF (item < min)
        {
            min <- item
        }
    }
    RETURN(min)
}

Proof of correctness. The algorithm maintains the invariant: “min is the smallest element among All elements seen so far.” Initially, min = list[1], true. At each step, if the new Element is smaller, we update min. By induction, after all elements, min is the smallest. $\blacksquare$

PROCEDURE average(list)
{
    sum <- 0
    FOR EACH item IN list
    {
        sum <- sum + item
    }
    RETURN(sum / LENGTH(list))
}

Edge case. If the list is empty, division by zero occurs. A robust implementation should check For this.

PROCEDURE findMode(list)
{
    mode <- list[1]
    modeCount <- 1
    FOR i <- 2 TO LENGTH(list)
    {
        count <- 1
        FOR j <- 1 TO i - 1
        {
            IF (list[j] = list[i])
            {
                count <- count + 1
            }
        }
        IF (count > modeCount)
        {
            modeCount <- count
            mode <- list[i]
        }
    }
    RETURN(mode)
}

Time complexity: $O(n^2)$. A more efficient $O(n \log n)$ approach sorts the list first.

• Personally identifiable information (PII): Information that can identify an individual.
• Anonymization: Removing PII from datasets before analysis or sharing.
• Metadata: Data about data (e.g., timestamps, GPS coordinates in photos).

• Symmetric encryption: Same key for encryption and decryption (e.g., AES). Fast.
• Asymmetric encryption: Public key for encryption, private key for decryption (e.g., RSA). Slower, but no need to share a secret key.
• Hashing: One-way function that produces a fixed-size output. Not encryption.

Salting passwords. A salt is a random string added to the password before hashing. This prevents Rainbow table attacks.

• Digital certificates bind a public key to an identity, verified by a certificate authority (CA).
• PKI manages the creation, distribution, and revocation of digital certificates.

public static int binarySearchList(ArrayList<Integer> list, int target) {
    int low = 0;
    int high = list.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int cmp = Integer.compare(list.get(mid), target);
        if (cmp == 0) return mid;
        else if (cmp < 0) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

ArrayList<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");

for (String name : names) {
    System.out.println(name);
}

for (int i = names.size() - 1; i >= 0; i--) {
    if (names.get(i).length() < 3) {
        names.remove(i);
    }
}

public class Student implements Comparable<Student> {
    private String name;
    private int grade;

    public int compareTo(Student other) {
        return this.grade - other.grade;
    }
}

Reversing a string:

public static String reverse(String s) {
    String result = "";
    for (int i = s.length() - 1; i >= 0; i--) {
        result += s.charAt(i);
    }
    return result;
}

Time complexity: $O(n^2)$ because string concatenation creates a new object each time. A more Efficient approach uses StringBuilder for $O(n)$.

Counting character frequency:

public static int[] charFrequency(String s) {
    int[] freq = new int[26];
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c >= "a' && c <= 'z') {
            freq[c - 'a']++;
        }
    }
    return freq;
}

Time complexity: $O(n)$.

• GDPR (EU): Right to access, right to be forgotten, data portability.
• CCPA (California): Right to know, right to delete, right to opt out.
• COPPA (US): Protects children under 13 online.

A data breach is an incident where sensitive data is accessed without authorisation. Consequences Include identity theft, financial loss, and reputational damage.

Prevention strategies:

• Encrypt sensitive data at rest and in transit.
• Implement access controls (principle of least privilege).
• Regular security audits and penetration testing.
• Employee training on security awareness.
• Monitor for unusual access patterns.

int abs = Math.abs(-5);           // 5
int max = Math.max(3, 7);          // 7
int min = Math.min(3, 7);          // 3
double sqrt = Math.sqrt(16.0);     // 4.0
int random = (int)(Math.random() * 10); // 0-9
int pow = (int)Math.pow(2, 10);    // 1024

ArrayList<Integer> list = new ArrayList<>();
list.add(5);        // autoboxing: int -> Integer
int value = list.get(0);  // unboxing: Integer -> int

int a = 5 / 2;        // 2 (integer division)
double b = 5.0 / 2;   // 2.5 (double division)
int c = (int) 2.9;    // 2 (truncation)
double d = (double) 5 / 2;  // 2.5

Caution: Always cast to double before division when you need a decimal result.

1. Write a Java method that finds and returns the mode (most frequent element) in an array of integers.

2. Write a Java method isSorted(int[] arr) that returns true if the array is sorted in ascending order.

3. Given a 2D array representing a seating chart (0 = empty, 1 = occupied), write a method that counts the number of occupied seats.

4. Write pseudocode for a procedure that removes all occurrences of a given value from a list.

5. Explain the difference between symmetric and asymmetric encryption.

6. Write a Java method that takes a string and returns a new string with all vowels removed.

7. Given an ArrayList of student names, write code to find all names that start with “A”.

8. Explain why == should not be used to compare String objects in Java.

9. Write a Java method that takes a 2D array and returns the sum of the main diagonal elements.

10. Explain what a salt is and why it is important for password security.

11. Write pseudocode for a procedure that finds the median value in a sorted list.

12. Explain the difference between anonymization and encryption.

13. Write a Java method isPalindrome(String s) that ignores case and non-alphanumeric characters.

14. Explain the difference between ArrayIndexOutOfBoundsException and NullPointerException. Give an example of code that causes each.

15. Write a Java method that finds the two largest values in an array in a single pass.

16. Write pseudocode for a procedure mergeSorted(list1, list2) that merges two sorted lists into one sorted list.

17. Explain what metadata is and give two examples where metadata could reveal sensitive information.

18. Write a Java method that counts the frequency of each character in a string and returns the results in a Map.

19. Explain the difference between an array and an ArrayList. Give three scenarios where you would use each.

20. Write a Java method that takes a 2D array and returns the transpose of the matrix. What is the time complexity?

Row-major traversal:

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

Column-major traversal:

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

public static int findMax2D(int[][] grid) {
    int max = grid[0][0];
    for (int r = 0; r < grid.length; r++) {
        for (int c = 0; c < grid[r].length; c++) {
            if (grid[r][c] > max) {
                max = grid[r][c];
            }
        }
    }
    return max;
}

Time complexity: $O(r imes c)$ where $r$ is rows and $c$ is columns.

A jagged array is a 2D array where rows have different lengths.

int[][] jagged = {
    {1, 2, 3},
    {4, 5},
    {6, 7, 8, 9}
};

Iterating over a jagged array: Use grid[r].length for each row, not grid[0].length.

for (int[] row : grid) {
    for (int val : row) {
        System.out.print(val + " ");
    }
    System.out.println();
}

import java.util.Arrays;

int[] arr = {5, 3, 8, 1};
Arrays.sort(arr);                    // [1, 3, 5, 8]
int idx = Arrays.binarySearch(arr, 5); // 2
String s = Arrays.toString(arr);       // "[1, 3, 5, 8]"

String s = "Hello, World!";

s.length()              // 13
s.substring(7)          // "World!"
s.substring(0, 5)       // "Hello"
s.indexOf("World")      // 7
s.charAt(1)             // 'e'
s.equals("hello, world!")  // false (case-sensitive)
s.equalsIgnoreCase("hello, world!")  // true
s.compareTo("Hello")    // > 0 (positive)
s.toUpperCase()         // "HELLO, WORLD!"
s.toLowerCase()         // "hello, world!"
s.trim()                // removes leading/trailing whitespace
s.replace("World", "CS") // "Hello, CS!"

String concatenation pitfall:

String result = "";
for (int i = 0; i < 10000; i++) {
    result += "x";  // Creates 10,000 String objects! O(n^2)
}
// Better:
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10000; i++) {
    sb.append("x");  // O(n)
}
String result = sb.toString();

Scatter plots are used to visualise the relationship between two variables.

• Positive correlation: As x increases, y increases.
• Negative correlation: As x increases, y decreases.
• No correlation: No visible pattern.

Correlation does not imply causation. Two variables may be correlated due to a confounding Variable, not because one causes the other.

Real-world data is often messy and requires cleaning before analysis:

• Handling missing values: Remove records, impute with mean/median, or flag as unknown.
• Removing duplicates: Prevents double-counting in analysis.
• Correcting formats: Standardising date formats, fixing inconsistent capitalisation.
• Outlier detection: Identifying and deciding whether to include or exclude extreme values.

1. Using == to compare strings. Always use .equals() for content comparison.
2. Off-by-one errors with substring. substring(a, b) includes index a but excludes b.
3. Confusing ArrayList size with array length. list.size() vs arr.length.
4. Forgetting that strings are immutable. Methods return new strings; they do not modify the original.
5. Not handling empty arrays or null inputs.
6. Confusing row and column indices in 2D arrays. grid[row][col].
7. Integer division in Java. 5 / 2 equals 2Not 2.5. Cast to double.
8. Confusing substring parameters across languages. Java substring(1, 4) returns chars at indices 1, 2, 3.

public static int binarySearchList(ArrayList<Integer> list, int target) {
    int low = 0;
    int high = list.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int cmp = Integer.compare(list.get(mid), target);
        if (cmp == 0) return mid;
        else if (cmp < 0) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

ArrayList<String> names = new ArrayList<>();
names.add("Alice");
names.add("Bob");
names.add("Charlie");

for (String name : names) {
    System.out.println(name);
}

The digital world runs on algorithms and data. From search engines to social media, software systems process information through carefully designed procedures. Computer science teaches us to think systematically about problems, design efficient solutions, and understand the technologies that shape modern life. These skills are essential for innovation in every field.

• Computational Thinking
• Algorithms