Time estimate: 90 min.

6.4. Array Algorithms (FRQs)¶

In this lesson, you will study different Free Response Questions and responses that develop algorithms using arrays.

Here are some common algorithms that you should be familiar with for the AP CSA exam:

Determine the minimum or maximum value in an array
Compute a sum, average, or mode of array elements
Search for a particular element in the array
Determine if at least one element has a particular property
Determine if all elements have a particular property
Access all consecutive pairs of elements
Determine the presence or absence of duplicate elements
Determine the number of elements meeting specific criteria
Shift or rotate elements left or right
Reverse the order of the elements

Here are two common array traversal loops that can be used for these algorithms:

for (int value : array)
{
    if (value ....)
        ...
}

for(int i=0; i < array.length; i++)
{
   if (array[i] ....)
       ...
}

Coding Exercise

The code below finds the minimum (smallest element) in an array. Try it in the Java visualizer with the CodeLens button. Can you change it to find the maximum element instead? Can you also compute the average of the elements?

public class MinMax
{
    public static void main(String[] args)
    {
        int[] values = {6, 2, 1, 7, 12, 5};
        int min = values[0]; // initialize min to the first element
        for (int val : values)
        {
            if (val < min) // found a new min!
            {
                min = val;
            }
        }
        System.out.println("Min is " + min);
    }
}

====
// Test for Lesson MinMax
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    public RunestoneTests()
    {
        super("MinMax");

int[] numArray = {2, 6, 7, 12, 5};
        setDefaultValues(new Object[] {numArray});
    }

@Test
    public void test1()
    {
        String output = getMethodOutput("main");
        String expect = "Max is 12";

boolean passed = output.contains(expect);

passed = getResults(expect, output, "Max element", passed);
        assertTrue(passed);
    }

@Test
    public void test2()
    {
        String output = getMethodOutput("main");
        String expect = "Average is 5.5";

boolean passed = output.contains(expect);

passed = getResults(expect, output, "Average", passed);
        assertTrue(passed);
    }

@Test
    public void test3()
    {
        boolean passed = checkCodeContains("if statement using val >", "if (val >");
        assertTrue(passed);
    }
}

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today

Coding Exercise

The code below rotates array elements to the left. Note that you need to use an indexed loop for this because you need to change the array and access two elements at different indices. Try it in the Java visualizer with the CodeLens button. Can you change it to rotate the elements to the right instead? Hint: use a backwards loop.

public class Rotate
{
    public static void main(String[] args)
    {
        int[] values = {6, 2, 1, 7, 12, 5};
        int first = values[0];
        for (int i = 0; i < values.length; i++)
        {
            // if it's not the last element, copy the next one over
            if (i < values.length - 1)
            {
                values[i] = values[i + 1];
            }
            else
            {
                // last element gets first
                values[i] = first;
            }
        }
        // print them out to see the results
        for (int val : values)
        {
            System.out.print(val + " ");
        }
    }
}

====
// Test for Lesson 6.4.2 - Rotate
import static org.junit.Assert.*;

import org.junit.*;

import java.io.*;

public class RunestoneTests extends CodeTestHelper
{
    public RunestoneTests()
    {
        super("Rotate");
    }

@Test
    public void test1()
    {
        String output = getMethodOutput("main");
        String expect = "5 6 2 1 7 12";

boolean passed = output.contains(expect);

passed = getResults(expect, output, "Rotate numbers to the right", passed);
        assertTrue(passed);
    }

@Test
    public void test3()
    {
        boolean passed =
                checkCodeContains("copying values[i-1] into values[i]", "values[i] = values[i-1]");
        assertTrue(passed);
    }
}

We encourage you to work in pairs or groups to tackle the following challenging FRQ problems and take them one step at a time. These will get easier with practice!

You have attempted 1 of 3 activities on this page