These examples are in AP CSP Pseudocode. For Java, see Lists as abstractions.
For different ways to traverse a list with AP CSP Pseudocode, see Traversals in AP CSP language.
Abstractions in computer science hide details so programmers can focus only on what matters now.
Commonly used abstractions include:
- Variables
- Procedures (often called methods or functions)
- Parameters
- Classes (in object oriented languages such as Java)
- Lists (see details below)
- Strings
In AP CSP Pseudocode a list has a length that can be changed by inserting, appending, or removing elements.
A programmer can write code once that executes for each element in a list. In many cases, the code will work regardless of the number of elements in the list. (The programmer does not need to know exactly how many elements will be in the list before they can write the code.)
Example 1: Finding an average
With a list
PROCEDURE findAverage(scores)
{
sum ← 0
FOR EACH score IN scores
{
sum ← sum + score
}
RETURN(sum / LENGTH(scores))
}
findAverage([90.0, 100.0, 80.0]) returns 90.0.
findAverage([90.0, 100.0, 80.0, 70.0]) returns 85.0.
The statement sum ← sum + score executes once for each element in scores. The expression sum / LENGTH(scores) divides by the number of elements in scores. As long as there is at least 1 element in scores, the procedure correctly returns the average.
Without a list
PROCEDURE findAverage(s1, s2, s3)
{
sum ← 0
sum ← sum + s1
sum ← sum + s2
sum ← sum + s3
RETURN(sum / 3)
}
The call findAverage(90.0, 100.0, 80.0) returns 90.0. The procedure correctly finds the average of exactly 3 scores.
(The code inside the procedure could be written on a single line. The approach above more clearly illustrates the point.)
This code might initially appear less complex than the solution that uses a list. Consider what happens if the programmer wants to find the average of 4 scores, instead of 3.
PROCEDURE findAverage(s1, s2, s3, s4)
{
sum ← 0
sum ← sum + s1
sum ← sum + s2
sum ← sum + s3
sum ← sum + s4
RETURN(sum / 4)
}
The procedure header must be modified (or a new procedure written) to accept an additional parameter. The additional value must be added to sum. The computation of the average must be modified to account for the new value.
Consider what happens if the programmer wants to find the average of anywhere between 3 and 10 values. The programmer must write 8 procedures, each of which must take the correct number of parameters. The programmer must ensure that each procedure correctly adds each parameter to sum and that the calculation of the average divides by the correct number of parameters.
The list manages complexity
Using a list manages complexity by removing the need for the programmer to consider the exact number of values. It allows the programmer to focus on the (simple) algorithm to calculate the average.
The example below is slightly more complex.
Example 2: Finding the largest
With a list
PROCEDURE findMax(nums)
{
max ← nums[1]
index ← 2
REPEAT UNTIL(index > LENGTH(nums))
{
IF(nums[index] > max)
{
max ← nums[index]
}
index ← index + 1
}
RETURN(max)
}
As long as nums contains at least one element, the method correctly returns the largest value in nums. The programmer does not need to worry about how many elements might be in nums nor does the programmer need to manually handle each element. The programmer can focus on the algorithm.
Without a list
PROCEDURE findMax(a, b, c)
{
max ← a
IF(b > max)
{
max ← b
}
IF(c > max)
{
max ← c
}
RETURN(max)
}
Procedure findMax correctly returns the maximum of exactly 3 numbers.
The code to handle each parameter is more complex than in findAverage. Adding additional parameters requires writing more significant additional code without error.
The list manages complexity
When designing and implementing an algorithm that processes multiple values of the same type in the same way, a list is a natural choice. The list allows the programmer to focus on how the algorithm should process a single value, rather than on how many values are to be processed and on correctly duplicating the code to handle each value.
Example 3: Collecting values
Example 1 demonstrates finding the average of scores. Consider the problem of accepting input of scores.
If the exact number of scores is known before the program is written, a list offers a relatively minor advantage. If the number of scores is not known, a list offers a much bigger advantage. The solutions below work when the number of scores is not known.
With a list
scores ← []
DISPLAY("Score (-1 when done):")
score ← INPUT()
REPEAT UNTIL(score = -1)
{
APPEND(scores, score)
DISPLAY("Score (-1 when done):")
score ← INPUT()
}
DISPLAY(scores)
The code segment prompts the user to enter scores and to enter a sentinel (-1) to indicate no more scores. (The code does not attempt to ensure at least 1 score, nor does it attempt to validate each score.)
Each score is stored in the scores list. The code works correctly. Each score entered by the user is appended to scores. The -1 entered to signal no more input is not added.
Without a list
s1 ← 0
s2 ← 0
s3 ← 0
count ← 0
DISPLAY("Score (-1 when done):")
input ← INPUT()
REPEAT UNTIL(input = -1)
{
count ← count + 1
IF(count = 1)
{
s1 ← input
}
ELSE
{
IF(count = 2)
{
s2 ← input
}
ELSE
{
s3 ← input
}
}
IF(count < 3)
{
DISPLAY("Score (-1 when done):")
input ← INPUT()
}
ELSE
{
input = -1
}
}
DISPLAY(count)
DISPLAY(s1)
DISPLAY(s2)
DISPLAY(s3)
Without a list, a variable must be declared for each possible score. This code segment declares s1, s2, and s3 to store up to 3 scores. The variable count makes the code segment easier to understand.
The code segment correctly accepts and stores input of zero, one, two, or three scores.
The list manages complexity
Without a list, accepting more than 3 scores requires modifying the code segment. With a list, any number of scores can be accepted with the same code segment.
Without a list, conditional statements determine which variable should store the current input. With a list, the current input is simply appended to the end of the list.
Help & comments
Get help from AP CS Tutor Brandon Horn