** ArrayLists are used to store data and algorithms and can be used to access, traverse, and sort through this data.**

Why ArrayLists?

ArrayLists don’t have a fixed size like Arrays and we can add and remove items from them, making them more verstaile and having more functions

Key Topics:

Topic 7.1 - Intro to Arraylists (Sri) Topic 7.2 - Methods with Arraylists (Sri & Saathvik) Topic 7.3 - Traversing ArrayLists (Tanav) Topic 7.4 - Developing Algorithms Using ArrayLists (Tanav) Topic 7.5 - Searching (Aidan) Topic 7.6 - Sorting (Aidan) Topic 7.7 - Ethical Issues Around Data Collection (Saathvik)

AP Exam Details

2.5-7.5% of the test

1 to 2 mc questions

Might be on an FRQ (making ArrayLists and ArrayList algorithms)

Screenshot 2024-09-24 at 9 34 30 PM

7.1: ArrayList Intro

ArrayLists are dynamic (size can grow and shrink unlike arrays which are static)
Instead of creating a different size array each time, we can use ArrayLists!
Ex: You and ur beautiful wife…

Screenshot 2024-09-18 at 8 05 02 PM

In order to use the ArrayList class, it needs to be imported from the java util package. This can be done by writing import java.util.ArrayList; at the beginning of the code

To use Arraylist class, it needs to be imported from java.util package
At beginning of code using an Arraylist, type the command below!

import java.util.ArrayList;

// your amazing code here!

ArrayList objects are initialized the same way as most object classes. However, the element type (String, Integer, Boolean) must be specified in the <>. Look at the example below, where the element type is String in this case.

Arraylist objects are initialized like most object classes
the element type must be initialized in <>
The objects can’t store primitive types directly

ArrayList<String> bobtheminion = new ArrayList(); // example of initializing an arraylist of strings called "awesomeword"
ArrayList<Integer> bobtheminionage = new ArrayList<>();
ArrayList<Boolean> isbobtheminionavailable = new ArrayList<>(); 
ArrayList<Double> minionheights = new ArrayList<>();

Popcorn Hack #1

What’s wrong with the code below?

import java.util.ArrayList;

ArrayList<String> awesomeword = new ArrayList(); 
ArrayList<Integer> coolnumbers = new ArrayList();
ArrayList<Boolean> truefalse = new ArrayList();
// change code and comment what you changed when doing homework
// int changes to integer

Screenshot 2024-09-24 at 8 12 38 PM

ArrayLists can be created without specifying a type, allowing them to hold any object type. However, its better to define the type because it allows the compiler to catch errors at compile time whcich makes the code more efficient and easier to debug. Example is below

Arraylists can be created without specifying a type (they can hold any)
Better to define the type as it makes code easier to debug and more efficient

ArrayList list = new ArrayList(); // no object type specified!

Popcorn Hack #2

Create two ArrayList objects, one for storing integers (called sritestgrades) and another for storing strings (called srishobbies).

import java.util.ArrayList;

ArrayList<Integer> sritestgrades = new ArrayList(); 
ArrayList<String> srishobbies = new ArrayList(); 
        
        sritestgrades.add(45);
        sritestgrades.add(32);
        sritestgrades.add(1);
        sritestgrades.add(90);
        sritestgrades.add(74);
        
        srishobbies.add("watching netflix");
        srishobbies.add("sleeping");
        srishobbies.add("");
        srishobbies.add("annoying saathvik");
        
        // Printing the values
        System.out.println("Sri's horrible test grades are: " + sritestgrades);
        System.out.println("Sri's hobbies are: " + srishobbies);

Sri's horrible test grades are: [45, 32, 1, 90, 74]
Sri's hobbies are: [watching netflix, sleeping, , annoying saathvik]

Screenshot 2024-09-24 at 8 13 10 PM

7.2: ArrayList Methods

Getting access to elements stored in an ArrayList can be done with iteration statements
This is called “traversing” the ArrayList

Here are some useful ArrayList methods:

void add(int index, Object obj) - Inserts obj at the specified index, shifting elements at and above that position to the right, and increases the list’s size by one.
boolean add(Object obj) - Adds obj to the end of the list and returns true.
Object get(int index) - Retrieves the element located at the specified index.
int size() - Returns the total number of elements currently in the list.
Object set(int index, Object obj) - Replaces the element at index with obj and returns the element previously at that position.
Object remove(int index) - Deletes the element at index, shifts all subsequent elements to the left, and returns the removed element.

Note on Arraylist<> (Specifying Elements)

When Arraylist is specified, then the code will only allow or return objects of that specific type
You don’t have to define an element, its just better to because the compiler will show an error and it’ll catch bugs easier

Examples below!

ArrayList<String> names = new ArrayList<>();  // Will only store Strings
ArrayList<Integer> numbers = new ArrayList<>();  // Will only store Integers

ArrayList<Integer> ages = new ArrayList<>();
ages.add(25);    // Works fine
ages.add("25");  // Compiler error because "25" is a String, not an Integer

|   ages.add("25");  // Compiler error because "25" is a String, not an Integer

incompatible types: java.lang.String cannot be converted to java.lang.Integer

Size of the ArrayList

int size(); : returns the number of elements in the list

Example below!

ArrayList<Integer> a1 = new ArrayList<>();
a1.add(10);
a1.add(20);
a1.add(30);

System.out.println(a1.size());

Adding Items to an ArrayList

boolean add(Object obj); : adds obj to the end of the `rrayList and returns true
void add(int index, Object obj) : inserts obj at the specified index and if the index is valid, it shifts all the elements to the right from that position and increases the size of the Arraylist (wow i bet arrays cant do that!)

example below!

ArrayList<Double> numbers = new ArrayList<>();
numbers.add(5.5);
numbers.add(7.2);
numbers.add(9.8);

numbers.add(1, 6.3);  // inserts 6.3 at index 1

System.out.println(numbers);

[5.5, 6.3, 7.2, 9.8]

Screenshot 2024-10-03 at 10 17 22 PM

Popcorn Hack #3 (Long)

Step 1: Declare and Initialize

Create an ArrayList that stores Double values, called scores.

Step 2: Add Elements

Add the following values to your scores list: 85.6, 92.4, 78.9, 88.1. Print the size of the list after adding these elements

Step 3: insert at index

use the add(int index, Double obj) method to insert the value 90.0 at index 2. Print the list to verify the insertion.

Step 4: Remove an Element

Remove the element at index 3 using remove(int index). Print the list to see the updated values.

Step 5: Get and Set

Retrieve the element at index 1 and print it. Then, use set(int index, Double obj) to update the element at index 0 to 91.5. Print the list after the modification.

Deleting Items from an ArrayList

E remove(int index) : Deletes the element at the specified index and shifts all elements after that index one position to the left. it reduces the size of the arraylist by 1. (also returns element thats removed when used)

ArrayList<String> cars = new ArrayList<>();
cars.add("MortMobile");
cars.add("Lopez Lambo");
cars.add("Jonathan Jeepatron");
cars.add("Cybertruck");

// prints the initial list of cars
System.out.println("initial cars list: " + cars);

// removing the car at index 2 (Jonathan Jeepatron)
cars.remove(2);

// prints updated list of cars after deletion (rip jonathan jeepatron)
System.out.println("updated cars list: " + cars);

initial cars list: [MortMobile, Lopez Lambo, Jonathan Jeepatron, Cybertruck]
updated cars list: [MortMobile, Lopez Lambo, Cybertruck]

Updating Items in an `ArrayList`

To update variables or object properties in Java, simply assign new values using the = operator or update object fields through methods. Make sure the data types match and understand how scopes affect where updates can occur.

import java.util.ArrayList;

ArrayList<String> fruits = new ArrayList<>();


fruits.add("Apple");
fruits.add("Banana");
fruits.add("Orange");

System.out.println("Original list: " + fruits);


fruits.set(1, "Grapes");


System.out.println("Updated list: " + fruits);

Original list: [Apple, Banana, Orange]
Updated list: [Apple, Grapes, Orange]

Popcorn hack

You have an ArrayList that contains the names of 5 cities:

["New York", "Los Angeles", "Chicago", "Houston", "Phoenix"]

Write a Java program to update the third city (index 2) to "San Francisco" using the set() method, and then print the updated list.

```Java

import java.util.ArrayList;

ArrayList<_____> cities = new ArrayList<>();
cities.add("New York");
cities.add("Los Angeles");
cities.add("Chicago");
cities.add("Houston");
cities.add("Phoenix");

System.out.println(cities);

|   ArrayList<_____> cities = new ArrayList<>();

cannot find symbol

  symbol:   class _____

Expected Output: [New York, Los Angeles, San Francisco, Houston, Phoenix]

Accessing Items in an `ArrayList`

In Java, you can access items in an array by using the index of the element, with array indices starting from 0. For example, array[0] will access the first element, and array[2] will access the third element. You can use a loop, such as a for or while loop, to iterate through all the elements of the array.


import java.util.ArrayList;

ArrayList<Integer> numbers = new ArrayList<>();

numbers.add(10);
numbers.add(20);
numbers.add(30);
numbers.add(40);

int firstNumber = numbers.get(0);  
int thirdNumber = numbers.get(2);  


System.out.println("First number: " + firstNumber);
System.out.println("Third number: " + thirdNumber);

First number: 10
Third number: 30

Passing an `ArrayList` as a Method Parameter

The only time that it is wise to use ArrayList instead of ArrayList<E> is when it is as a function parameter and it is only using ArrayList<>.get(E) or ArrayList<>.size(). Consider the following code:


import java.util.ArrayList;

public class Main {

    public static void main(String[] args) {
        // Create an ArrayList of strings
        ArrayList<String> animals = new ArrayList<>();
        animals.add("Dog");
        animals.add("Cat");
        animals.add("Elephant");

        printArrayList(animals);
    }
    
    public static void printArrayList(ArrayList<String> list) {
        System.out.println("ArrayList Elements:");
        for (String element : list) {
            System.out.println(element);
        }
    }


}

Main.main(null);

ArrayList Elements:
Dog
Cat
Elephant

Returning an `ArrayList` from a Method

In order for you to return an ArrayList, the data type must be specified, and the return type must be the same as the return value. Consider the following code:


import java.util.ArrayList;

public class Main {

    public static ArrayList<String> createAnimalList() {
        ArrayList<String> animals = new ArrayList<>();
        animals.add("Lion");
        animals.add("Tiger");
        animals.add("Elephant");
        return animals;
    }

    public static void main(String[] args) {
        ArrayList<String> animalList = createAnimalList();

        System.out.println("Returned ArrayList: " + animalList);
    }
}

Main.main(null);

Returned ArrayList: [Lion, Tiger, Elephant]

Hard Hack: “Simple Inventory Manager”

Problem Statement:

You are building a basic inventory system using Java’s ArrayList to manage a list of items in a store. You will implement functions to add, update, delete, and view items in the inventory.

Starting Inventory:
The inventory already contains the following items:

"Laptop", "Mouse", "Keyboard"

Your task is to:

Add items to the inventory.
Update an item at a specific position in the inventory.
Delete an item from the inventory.
View all the items currently in the inventory.

Directions:

Create an ArrayList called inventory that holds strings representing the items.
Implement the following methods:
- addItem(ArrayList<String> inventory, String item): Adds an item to the inventory.
- updateItem(ArrayList<String> inventory, int index, String newItem): Updates the item at the specified index.
- deleteItem(ArrayList<String> inventory, int index): Deletes the item at the specified index.
- viewInventory(ArrayList<String> inventory): Displays all the items in the inventory.
In your main() method:
- Initialize the inventory with the starting items.
- Add one new item to the inventory.
- Update the second item.
- Delete the third item.
- Display the final inventory.

Example Workflow:

Start with the inventory: ["Laptop", "Mouse", "Keyboard"].
Add "Monitor".
Update "Mouse" to "Gaming Mouse".
Delete "Keyboard".
Display the final inventory.

Expectations:

Ensure valid index when updating or deleting items (handle out-of-bounds indices).
Use the get(), set(), add(), and remove() methods to manage the ArrayList.
After all operations, print the final version of the inventory using viewInventory().

Starter Code

import java.util.ArrayList;

public class InventoryManager {

    // Method to add an item to the inventory
    public static void addItem(ArrayList<String> inventory, String item) {
        inventory.add(item);
    }

    // Method to update an item at a specific index in the inventory
    public static void updateItem(ArrayList<String> inventory, int index, String newItem) {
        if (index >= 0 && index < inventory.size()) {
            inventory.set(index, newItem);
        } else {
            System.out.println("Invalid index. Cannot update.");
        }
    }

    // Method to delete an item from the inventory
    public static void deleteItem(ArrayList<String> inventory, int index) {
        if (index >= 0 && index < inventory.size()) {
            inventory.remove(index);
        } else {
            System.out.println("Invalid index. Cannot delete.");
        }
    }

    // Method to display all items in the inventory
    public static void viewInventory(ArrayList<String> inventory) {
        System.out.println("Current Inventory: " + inventory);
    }

    public static void main(String[] args) {
        // Initialize the inventory with starting items
        ArrayList<String> inventory = new ArrayList<>();
        inventory.add("Laptop");
        inventory.add("Mouse");
        inventory.add("Keyboard");

        // Add a new item
        addItem(inventory, "Monitor");

        // Update the second item
        updateItem(inventory, 1, "Gaming Mouse");

        // Delete the third item
        deleteItem(inventory, 2);

        // View the final inventory
        viewInventory(inventory);
    }
}

7.3 Traversing Arraylists

You can traverse through the elements in an ArrayList using loops. In order to traverse ArrayLists, we can use iterative statements, or loops. We can use For Each Loops, For Loops, and While Loops

The following code uses a For Each loop to traverse through the ArrayList.

//7.3.1: For Each Loop
ArrayList<Integer> myList = new ArrayList<Integer>();
        myList.add(50);
        myList.add(30);
        myList.add(20);
        for (Integer value : myList)
        {
            System.out.println(value);
        }

50
30
20

Popcorn Hack #1:

Modify the code above so that it prints out the sum of all the elements in the list.

The problem with For Each loops is that you can’t modify the ArrayList. To do that, you will need to use another type of loop. If you attempt to modify the ArrayList, you will get a ConcurrentModificationException error.

ConcurrentModificationException Error:

Happens when you try to modify the structure of an ArrayList using a For Each loop.

Think about it this way: Imagine you are standing in a line at the store and then somebody cuts the line. The order of the line has changed. The store doesn’t want people cutting the line becaues it changes the order and creates confusion. So, it throws out a ConcurrentModificationError to alert you that something is wrong and that you shouldn’t do it.

It’s the same for For Each Loops in Java - You can’t add or remove elements because it changes the structure of the loop.

Common mistakes with For Each Loops:

Make sure that the data type of your variable is the same as the data type of the ArrayList
Don’t try to modify the ArrayList!!!!!! I can’t stress this enough

For Loops

Here’s how to traverse through an arraylist using a For Loop. The following code will give you an IndexOutOfBounds error, do you know how to fix this error?

There are three major parts of a for loop:

Initialisation, this is where you declare the variable index
Boolean condition, this is where you declare the stop condition, when it’s true, it stops.
Update, this is the increment value, i++ is increment and i– is decrement

// 7.3.2 For Loops
ArrayList<Integer> myList = new ArrayList<Integer>();
        myList.add(50);
        myList.add(30);
        myList.add(20);
        for (int i = 0; i <= myList.size(); i++)  
        {
            System.out.println(myList.get(i));
        }

50
30
20

---------------------------------------------------------------------------

java.lang.IndexOutOfBoundsException: Index 3 out of bounds for length 3

	at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)

	at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)

	at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:266)

	at java.base/java.util.Objects.checkIndex(Objects.java:359)

	at java.base/java.util.ArrayList.get(ArrayList.java:427)

	at .(#85:1)

IndexOutOfBoundsException

This happens when the program is trying to fetch something that isn’t there. If we have the equals since in the for loop, it will try to fetch up to index 3 because thats the list size. When we remove the equals sign, it goes to whatever is <3, which is 2. So, it fetches up to index 2, meaning 3 elements.

Popcorn Hack 2:

Suppose we have an arraylist named grades, and we want to remove the entries that are lower than 70. Use a for loop to achieve this.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        ArrayList<int> grades = new ArrayList<>();
        grades.add(68.9);
        grades.add(71);
        grades.add(100);
        grades.add(80);
        for(int i = 0; i<; i++){
            if(grades.get(i)<70){
                grades.remove(i);
            }
        }
        System.out.println(grades);
    }
}

|           for(int i = 0; i<; i++){

illegal start of expression

While Loops

Here is the final example of traversing through ArrayLists using while loops

ArrayList<String> fruits = new ArrayList<>();
fruits.add("apple");
fruits.add("banana");
fruits.add("orange");

int index = 0;
while (index < fruits.size()) {
    System.out.println(fruits.get(index));
    index++;
}

apple
banana
orange

7.4 Developing Algorithms Using ArrayLists

Common Arraylist Methods:

size(): Returns the size of the arraylist as an Integer
add(object): Adds an object to the end of your ArrayList
void add(index, object): Addes an object to an index of your choice. Shifts the index of everything to the right by one and increases size by 1
get(index): Retrieves the object at the index specified
set(index, obj): Like void add, but instead of adding, it replaces the object that’s already in that index
remove(index): Removes the object at specified index

//size() & add(object)

ArrayList<Double> numbers = new ArrayList<>();
    numbers.add(1.0);
    numbers.add(2.0);
    numbers.add(3.0);

int size = numbers.size();

System.out.println(size);

//void add(index, object)
//get(index)
ArrayList<Double> numbers = new ArrayList<>();
    numbers.add(1.0);
    numbers.add(2.0);
    numbers.add(3.0);

System.out.println(numbers.get(2));

    numbers.add(2,4.0);

System.out.println(numbers.get(2));
System.out.println(numbers.get(3));

0
0
0

// set(index, obj)


ArrayList<Double> numbers = new ArrayList<>();
    numbers.add(1.0);
    numbers.add(2.0);
    numbers.add(3.0);

System.out.println(numbers.get(2));

    numbers.set(2,4.0);

System.out.println(numbers.get(2));

3.0
4.0

// remove(index)


ArrayList<Double> numbers = new ArrayList<>();
    numbers.add(1.0);
    numbers.add(2.0);
    numbers.add(3.0);
System.out.println(numbers.get(2));
    numbers.remove(2);

System.out.println(numbers.get(0));
System.out.println(numbers.get(1));
System.out.println(numbers.get(2));

//anybody know why we get an IndexOutofBoundsException eror?

3.0
1.0
2.0

---------------------------------------------------------------------------

java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2

	at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)

	at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)

	at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:266)

	at java.base/java.util.Objects.checkIndex(Objects.java:359)

	at java.base/java.util.ArrayList.get(ArrayList.java:427)

	at .(#118:1)

Here’s an example of a program using Arrays that finds the maximum value:

public class Main {
    public static void main(String[] args) {
        double[] values = {1, 2, 3, 4, 5};

        double maxValue = findMax(values);
        System.out.println("The maximum value is: " + maxValue);
    }

    private static double findMax(double[] values) {
        double max = values[0];
        for (int index = 1; index < values.length; index++) {
            if (values[index] > max) {
                max = values[index];
            }
        }
        return max;
    }
}
Main.main(null);

Now, how can we modify this to use an ArrayList?


public class Main {
    public static void main(String[] args) {
        ArrayList<Double> values = new ArrayList<>();
        values.add(1.2);
        values.add(3.4);
        values.add(2.6);
        values.add(4.9);
        values.add(0.8);

        double maxValue = findMax(values);
        System.out.println("The maximum value is: " + maxValue);
    }

    private static double findMax(ArrayList<Double> values) {
        double max = values.get(0);

        for (int index = 1; index < values.size(); index++) {
            if (values.get(index) > max) {
                max = values.get(index);
            }
        }
        return max; 
    }
}
Main.main(null);

The maximum value is: 4.9

Homework:

(Paragraph Answer)

What is the difference between the two examples above. Which one is better and why? A: ArrayLists are the better option because they’re more dynamic as opposed to static. The first code example uses a primitive array (double[]), while the second uses an ArrayList; Double. Arrays have a fixed size and are more efficient with memory, but ArrayLists are more flexible, and dynamic (Code Answer)
Make your own algorithm using ArrayLists that finds the sum of the elements in the ArrayList

public class Main {
    public static void main(String[] args) {
        ArrayList<Double> values = new ArrayList<>();
        values.add(1.2);
        values.add(3.4);
        values.add(2.6);
        values.add(4.9);
        values.add(0.8);

        double sum = findSum(values);
        System.out.println("The sum of the values is: " + sum);
    }

    public static double findSum(ArrayList<Double> values) {
        double sum = 0;

        for (int index = 0; index < values.size(); index++) {
            sum += values.get(index);
        }

        return sum;
    }
}

Binary and Linear Search

There are two search algorithms you will see on the AP exam:

Linear Search

Binary Search

Linear(Sequential) Search

Linear Search GIF 2

Search Process

Remember iteration and selection? Its the same for ArrayLists: a for loop with an if statement inside.

The for loop parameter uses comparison operators to compare an item inside the ArrayList to the desired searched value

Keep repeating 1 and 2 until we find the desired searched value

Binary Search

Binary Search GIF 2

Search Process

Before anything, the ArrayList HAS to be sorted

Set the initial minimum, middle, and max of the ArrayList. Your target value is the value you want to find

Check middle value in comparison with the minimum and maximum

If the middle value is less than the target value, only check the right half of the ArrayList

If the middle value is greater than the target value, only check the left half of the ArrayList

Yes its very confusing but just look at the GIF

Now lets look at an example of Linear Search

Visualize this while going through the code

A for loop will go through each index and its corresponding value until it finds the desired value.

Code

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        
        // missing 3, 6, 7, and 10
        numbers.add(1);
        numbers.add(2);
        
        numbers.add(4);
        numbers.add(5);
        
      
        numbers.add(8);
        numbers.add(9);
        
        
        Scanner scanNumber = new Scanner(System.in);
        System.out.println("Enter a number 1-10");
        Integer desiredNumber = scanNumber.nextInt();
        

        for (int index = 0; index < numbers.size(); index++) {
            // notice how the == operator is used to compare integers
            if (numbers.get(index) == desiredNumber) {

                System.out.println(desiredNumber + " is in the list");
                scanNumber.close();
            } else {
                System.out.println(desiredNumber + " is not in the list.");
                scanNumber.close();
            }
        }

        
    }   

}

Popcorn Hack #1(0.2 mins)

Sequential Searching Flow

What does each hop or jump represent? What code(look above) is used to achieve this?

Now lets look at an example of Binary Search

Visualize this while going through the code

Repeatedly divide the search range in half until the target is found or the range is empty

this is a great GIF to visualize binary searching

Code

import java.util.ArrayList;
import java.util.Collections;


public static int binarySearch(ArrayList<Integer> elements, int target)
{
    // min and max is the RANGE of the ArrayList
    int min = 0;
    int max = elements.size() - 1;

    // while loop will ensure the array continues to be split in half until target is found
    while (min <= max)
    {
        // this middle value is the INDEX not VALUE. 
        int middle = (min + max) / 2;

        // now we check if the middle VALUE is less than the number we want. 
        // *remember* the list is sorted so...
        // if middle is less than the target, you want to split the array into the UPPER HALF
        // if middle is more than the target, you want to split the array into the LOWER HALF
        if (elements.get(middle) < target) { // too low
            min = middle + 1;
        } else if (elements.get(middle) > target) { // too high
            max = middle - 1;
        } else if (elements.get(middle) == target) { // just right
            return middle;
        }
    }

    return -1;
}

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(-20);
numbers.add(3);
numbers.add(15);
numbers.add(81);
numbers.add(432);

// binary searches HAVE to be sorted
Collections.sort(numbers);


int index = binarySearch(numbers, 15);
System.out.println(index);

index = binarySearch(numbers, -20);
System.out.println(index);

index = binarySearch(numbers, 432);
System.out.println(index);

index = binarySearch(numbers, 53);
System.out.println(index);

Homework

Imagine you’re an online E-store that sells video games. Use linear searching to help Aidan find if the game, Grand Theft Auto V, is offered in the E-store. If it is, tell him the price. If it isn’t, tell him where he can find it

import java.util.ArrayList;

public class searchString {
    public static void main(String[] args) {
        ArrayList<String> videoGames = new ArrayList<String>();
        videoGames.add("Roblox");
        videoGames.add("Fortnite");
        videoGames.add("Valorant");
        videoGames.add("Apex Legends");
        videoGames.add("GTA V");

        // *code*
}

7.6 Sorting

Two of the following sorting algorithms will be on the AP exam.(merge sort is discussed in Unit 10)

Selection sort: Look for the smallest element, swap with first element. Look for the second smallest, swap with second element, etc…

Insertion sort: Build an increasingly large sorted front portion of array.
All sorting algorithms have…

comparison-based sorting, which determines order of elements by comparing them to each other. Ways to compare are:

<, >, compareTo

Selection Sort

Process: Orders a list of values by repeatedly putting the smallest or largest unplaced value into its final position.

Look through the list to find the smallest value.

Swap it so that it is at index 0.

Look through the list to find the second-smallest value.

Swap it so that it is at index 1.

…

Repeat until all values are in their proper places.

Visualize this diagram as you go through the code

Code Implementation:

import java.util.ArrayList;

public static void selectionSort(ArrayList<Integer> elements)
{
    // outer loop to iterate through every element in the ArrayList
    for (int j = 0; j < elements.size() - 1; j++)
    {
        // set the current value being compared 
        int minIndex = j;
        // INNER LOOP TO ITERATE EVERY ELEMENT AFTER THE minIndex VALUE
        for (int k = j + 1; k < elements.size(); k++)
        {
            // FIND THE SMALLEST ELEMENT IN THE LIST AND SET IT TO THE minINDEX
            if (elements.get(k) < elements.get(minIndex))
            {
                minIndex = k;
            }
        }
        // swap minIndex value with new smaller value
        int temp = elements.get(j);
        elements.set(j, elements.get(minIndex));
        elements.set(minIndex, temp);
    }
}

// test cases
ArrayList<Integer> arr1 = new ArrayList<>();
arr1.add(3);
arr1.add(86);
arr1.add(-20);
arr1.add(14);
arr1.add(40);
System.out.println(arr1.toString());
selectionSort(arr1);
System.out.println(arr1.toString());

Insertion Sort

Process: Shift each element into a sorted sub-array.

To sort a list of n elements.

Loop through indices i from 1 to n – 1:

For each value at position i, insert into correct position in the sorted list from index 0 to i – 1.

Visualize this GIF as you go through the code:

Code Implementation:

import java.util.ArrayList;

public static void insertionSort(ArrayList elements) { // outer loop to iterate through every element in the list // notice how it starts at 1 because the 0 index is considered "sorted" for (int j = 1; j < elements.size(); j++) { // store current element in a temporary variable int temp = elements.get(j); // initialize the possible index where the current element might be inserted int possibleIndex = j;

    // shift elements to the right until the correct position for temp is found
    while (possibleIndex > 0 && temp < elements.get(possibleIndex - 1)) 
    {
        // move previous element to the right
        elements.set(possibleIndex, elements.get(possibleIndex - 1));
        
        // decrement index to check values to the left
        possibleIndex--;
    }
    
    // insert current element into correct position
    elements.set(possibleIndex, temp);
} }

// test cases ArrayList arr1 = new ArrayList<>(); arr1.add(3); arr1.add(86); arr1.add(-20); arr1.add(14); arr1.add(40); System.out.println(arr1.toString()); insertionSort(arr1); System.out.println(arr1.toString());

Homework

You’re a teacher for a computer science class at Rancho Bernardo. You have a list of all the grades of the students in your class but its hard to see who has the highest and lowest grade. Use either insertion sort or selection sort to sort the ArrayList so the grades are easy to see.

Helpful Resources

Watch these if you’re still unsure about selection and insertion sort. These helped me a lot.

import java.util.ArrayList;

public class SortTest
{
    public static void someSortingAlgorithm(ArrayList<Integer> elements)
    {   
        /* code */
    }

    public static void main(String[] args)
    {
        ArrayList<Integer> arr1 = new ArrayList<>();
        arr1.add(85);
        arr1.add(92);
        arr1.add(76);
        arr1.add(88);
        arr1.add(67);
        arr1.add(94);
        arr1.add(73);
        arr1.add(89);
        arr1.add(91);
        arr1.add(82);
        arr1.add(78);
        arr1.add(88);
        arr1.add(95);
        arr1.add(60);
        arr1.add(84);
        arr1.add(77);
        arr1.add(91);
        arr1.add(68);
        arr1.add(97);
        arr1.add(83);

        /* code */
    }
}

7.7: Ethical issues around Data Collection

Learning Objectives:

Explaining the risks of privacy from collecting and storing personal data on computer systems.

Essential Knowledge:

Data Collection: Methods (cookies, tracking, etc.)
Ethical Data Use: Identifying Personal data (Personal Identifiable Information, Sensitive Personal Information)
Security Practices: Data Encryption, Data Anonymization, Data Minimization

Privacy Protection mechanisms

Encryption: Encode data for only authorized users to access.
Anonymization: Remove personal information from data.
Data Minimization: Collect only necessary data.
User Control: Allowing users to control how their data is used

// Example string data
String originalData = "mySecretPassword123";

// Generate a hash code for the string
int hash = originalData.hashCode();

// Display the original data and its hash
System.out.println("Original Data: " + originalData);
System.out.println("Hash Code: " + hash);

// Demonstrate that the same string always produces the same hash
String sameData = "mySecretPassword123";
int sameHash = sameData.hashCode();
System.out.println("Same Data Hash: " + sameHash);

// Demonstrate that a small change in data produces a different hash
String modifiedData = "mySecretPassword124";
int modifiedHash = modifiedData.hashCode();
System.out.println("Modified Data: " + modifiedData);
System.out.println("Modified Data Hash: " + modifiedHash);

Uses of Hashing

Hashing is used to store passwords securely but it is not enough for large scale industries.
Hashing is used to conceal sensitive information like credit card information but not enough to protect it entirely.

Hashing with Salt

As we talked about earlier in the hashing section, hashing is a one-way function. This means that once you hash a value, you can’t get the original value back. This is useful for storing passwords, but it also means that if two users have the same password, they will have the same hash. This is a problem because if an attacker gets access to the hash, they can use a rainbow table to look up the hash and find the original password.

Thus, we use Hasing with Salt which means that even if 2 users have the same password, they will have different hashes because we add a random value to the password before hashing it. This random value is called a salt.

Homework

Homework Problem: Exploring Hashing and Privacy Protection (Extra Credit)

Problem:

Write a Java program that simulates how hashing works in protecting passwords. You will implement the following tasks:

Task 1: Basic Password Hashing
- Write a program that accepts a user’s password input and generates a hash using the hashCode() method.
- Display the original password and the hash to show how the same input always produces the same hash.
Task 2: Salting the Password
- Enhance the program by generating a random salt for the password. Append the salt to the password before hashing, and display both the salt and the hashed password.
- Store the salt separately and demonstrate that the same password with a different salt produces a different hash.
Task 3: Verifying the Password
- Write a method that simulates logging in by taking a password and salt as input, hashing them again, and comparing the result to the previously stored hash.
- If the hash matches, display “Login Successful”; otherwise, display “Login Failed.”

Extra Challenge (Optional):

Research and use the MessageDigest class in Java to implement password hashing with a more secure algorithm like SHA-256. Modify your program to use this instead of hashCode().

AP Computer Science A - Unit 6 Home Page

Main Idea

Why ArrayLists?

Key Topics:

AP Exam Details

7.1: ArrayList Intro

Popcorn Hack #1

Popcorn Hack #2

7.2: ArrayList Methods

Note on Arraylist<> (Specifying Elements)

Size of the ArrayList

Adding Items to an ArrayList

Popcorn Hack #3 (Long)

Deleting Items from an ArrayList

Updating Items in an ArrayList

Popcorn hack

Accessing Items in an ArrayList

Passing an ArrayList as a Method Parameter

Returning an ArrayList from a Method

Hard Hack: “Simple Inventory Manager”

Problem Statement:

Directions:

Example Workflow:

Expectations:

Starter Code

7.3 Traversing Arraylists

Popcorn Hack #1:

ConcurrentModificationException Error:

Common mistakes with For Each Loops:

For Loops

IndexOutOfBoundsException

Popcorn Hack 2:

While Loops

7.4 Developing Algorithms Using ArrayLists

Now, how can we modify this to use an ArrayList?

Binary and Linear Search

Linear(Sequential) Search

Binary Search

Now lets look at an example of Linear Search

Code

Popcorn Hack #1(0.2 mins)

Now lets look at an example of Binary Search

Code

Homework

7.6 Sorting

All sorting algorithms have…

Selection Sort

Code Implementation:

Insertion Sort

Code Implementation:

Homework

Helpful Resources

7.7: Ethical issues around Data Collection

Learning Objectives:

Essential Knowledge:

Privacy Protection mechanisms

Uses of Hashing

Hashing with Salt

Homework

Homework Problem: Exploring Hashing and Privacy Protection (Extra Credit)

Problem:

Extra Challenge (Optional):

Updating Items in an `ArrayList`

Accessing Items in an `ArrayList`

Passing an `ArrayList` as a Method Parameter

Returning an `ArrayList` from a Method