Algorithms To capabilities …

We can compare algorithms informally by counting statement executions. For instance, sometimes it’s useful to analyze a loop to determine either exactly or approximately how many times it will execute its body. More rigorously we can characterize algorithms by how their run time grows as the size of the problem grows.

There are standard algorithms to compute statistics about numbers in an array or ArrayList such as the sum, average, minimum, and maximum value.
There are standard algorithms to determine if at least one element of an array or ArrayList has a particular property
There are standard algorithms to determine if all elements of an array or ArrayList have a particular property
There are standard algorithms to access all consecutive pairs of elements of an array or ArrayList.
There are standard algorithms to determine the presence or absence of duplicate elements in an array or ArrayList.
There are standard algorithms to determine the number of elements in an array or ArrayList meeting specific criteria
There are standard algorithms to shift or rotate elements of an array or ArrayList left or right.
There are standard algorithms to reverse the order of the elements of an array or ArrayList.
There are standard algorithms to determine the frequency with which a specific criterion is met by elements within an array or ArrayList
There are standard algorithms to identify the individual digits in an integer

There are standard algorithms that utilize String traversals to find if one or more substrings has a particular property
There are standard algorithms that utilize String traversals to determine the number of substrings that meet specific criteria
There are standard algorithms that utilize String traversals to create a new String with the characters reversed

Linear, or sequential, search algorithms check each element in order until the desired value is found or all elements in the array or ArrayList have been checked. You should be able to write code that performs a linear search.
Binary search algorithms can search sorted lists much more efficiently than linear search, finding elements in \i{log N} time where \i{N} is the size of the list. You are unlikely to need to write a binary search yourself for the exam.
The binary search algorithm starts at the middle of a sorted array or ArrayList and on average eliminates half of the elements in each iteration until the desired value is found or all elements have been eliminated.
The binary search algorithm can be written either iteratively or recursively.

Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList. You should be able to recognize them but will not have to write them yourself.
Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList. You will not have to be able to write a merge sort.

A recursive method is a method that calls itself.\note{Technically a method doesn’t have to call itself directly. There can also be “mutual recursions” where method \i{a} calls \i{b} which then calls \i{a}. But in the AP curriculum we are only concerned with simple one-method recursions.}
Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call.
Each recursive call has its own set of local variables, including its parameters.
Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.
Recursion can be used to traverse linear structures like Strings, arrays, and ArrayLists but it is most useful for traversing tree structures which are difficult to traverse with simple loops.
Any recursive solution can be replicated through the use of an iterative approach. However some recursions, such as tree recursions, will require maintaining extra data structures to keep track of the information that would otherwise be managed by the process of recursion.