5 Steps to a 5: AP Computer Science Principles 2024 - Sway J.S. 2023

9 Algorithms and Programming
STEP 4 Review the Knowledge You Need to Score High

IN THIS CHAPTER

Summary: Algorithms are solutions designed to create something new or solve problems. They are fundamental to programming. Programs implement algorithms and can be developed for any reason, personal or professional; can utilize a variety of input and output; and can be easily shared.

This course does not require students to use a particular programming language. Therefore, the format of questions on the exam will use a standard format. There are some key differences from most programming languages. One difference is that lists start at index position 1, which is different than many programming languages. Students must be familiar with this format to ensure they are not slowed down or confused when reading the exam questions!

Students will have a copy of the Exam Reference Sheet (see the Appendix) during the exam.

Key Ideas

Abstractions are created by removing details and making concepts more general. Programs use data abstraction and procedural abstraction to manage complexity.

All algorithms can be written using a combination of sequential, selection, and iterative statements.

Variables hold values in programs. Assignment statements change the value stored in a variable.

Procedures are reusable blocks of code.

Parameters accept values that can differ each time the procedure is used.

Return statements exit a procedure and can send values back from the procedure to the calling program.

Lists are collections of data stored in one variable. FOR EACH loops traverse each item in a list.

Some algorithms cannot run in a reasonable amount of time, usually for large datasets. Heuristics can sometimes be used to find a solution that is close enough. Undecidable problems have no solution for all instances.

Simulations are abstractions to test theories in a safer, controlled, and faster environment.

Key Terms

Algorithm

API

Argument

Arithmetic operators

Assignment statement

Binary search

Boolean values

Clarity

Code statement

Concatenation

Condition

Data abstraction

Decidable problem

Decision problem

Efficiency

Element

Expression

Heuristic

Iterative

Library

Linear search

Lists

Logical operators

Modularity

Modulus

Optimization problem

Parameter

Procedural abstraction

Procedure

Pseudocode

Readability

Relational operators

RETURN statement

Selection statement

Sequential statement

Simulation

String

Substring

Traverse

Undecidable problem

Variable

Algorithms: The Building Blocks of Programming

Computers run the world! Or so it seems, more and more. Therefore, we should all have an idea of what programming is about. Computer programs can be written for a multitude of reasons, such as for businesses, scientific research, the entertainment industry, and personal use. Programs can include video, audio, images, text, buttons to push, and items to drag and swipe.

Algorithms

An algorithm is a set of steps to do a task. Recipes are algorithms. They are a set of steps to prepare food. Instructions for taking medicine make up an algorithm. Directions to get from one location to another are an algorithm.

In computer science, algorithms are the set of steps to solve a problem or complete a task. Algorithms are implemented with software. Examples are programs to:

• Calculate grade averages

• Run the air conditioner when the room temperature reaches 78°F

• Calculate the shortest route from home to school on your GPS

Algorithms have the potential to solve many problems once the programs are written for them to run. For example, a sorting algorithm is simple conceptually. Once it is programmed, an indefinite number of datasets can be sorted using it. As improvements are made to software and hardware, additional programming implementations are now feasible. For example, large datasets can now be handled by distributing the data over multiple programs or multiple devices, each processing a section of the code or data at the same time.

A section of code may work independently or can be used with other programming modules. These program modules read in values, make computations as needed, and produce output to automate processes. Programs may have a variety of data coming in (input) and going out (output). Input or output data could be in the form of text, video or images, audio files, or other formats, depending on the needs of the programming solution.

Languages for Algorithms

Algorithms can be written in several ways. Natural language is our native speaking and writing language, so it is much easier for people to use and understand.

Programming languages are very strict with their syntax, which is like their grammar and structure. This includes both block-style programming languages and textual programming languages. These are written for the computer to execute and may be more difficult for beginning programmers to understand. Pseudocode is used to map out a program’s structure before beginning to write the code and uses a combination of natural and programming languages. As you first start out designing algorithms, you will likely use more natural language features. As you learn more about a programming language, your pseudocode may begin to include more coding-like features. Pseudocode cannot run on computers and needs to be translated to a programming language to do so. While most programming languages are fairly equitable in being able to implement an algorithm in the code, some were written for specific uses in a particular subject area, such as physics, and are better suited for these uses.

Flowcharts

Diagramming an algorithm before programming it is another way, like pseudocode, to plan out your program prior to starting to code it. Flowcharting helps to visualize how the program will be structured. You may see places for loops and procedures at this early stage. In some ways, it’s like doing a puzzle. You can see how requirements are met with the flowchart, and how some may work better in a certain order or combination in your future code.

There are predefined shapes used by programmers for creating flowcharts. While there are many shapes, the basics are as shown in the following chart.

Many software programs, including word processing software, include flowcharting shapes. There are other programs written specifically for creating flowcharts. While you won’t have to create a flowchart on the AP exam, you might have to view one and answer questions about the content of it.

Using Algorithms

Algorithm Readability and Clarity

An important feature of any algorithm and program is how easy it is to read and follow. Hand in hand with readability is clarity. Clarity refers to how easy it is to understand. Generally, a program that is readable is clear. Readability is important to help programmers understand a program. The original programmer may not be the person who makes changes to it later. Even if it is the original author, if a period of time exists between writing it and modifying it, readability and clarity will impact the time and ability of the programmer to revisit and remember the details about the program before modifying or correcting the code. Features of readability and clarity include variables and procedures that are named according to their use and effective documentation of the program with comments in the code along with blank lines to separate sections of code.

Always be aware that there is more than one correct algorithm to solve a problem at hand or to create something new. Finding different algorithmic solutions can be helpful in identifying new insights about the problem. Different algorithms may also have different levels of efficiency or clarity.

Foundations of Computer Programming

Variables

Variables are placeholders for values a program needs to use. A program may need variables for numbers, both integers and real numbers, as well as text fields and Boolean values. Programs can assign values to variables as well as update the value to be a new one. Variables can be used in expressions, both mathematical and textual. An important aspect of variables is naming them well. As discussed earlier, a good name for a variable is one that is descriptive. This makes it “self documenting” in that it describes the value or values that the variable holds, such as age, name, temperature, or score.

Variables are data abstractions because we do not need to know the details of how and where the values are stored in memory. We can reference the data value using the variable name, managing the complexity of programs and making them much easier to create, update, and understand. The variable can hold a single data value or a collection of values, if it is a list.

Data Types

The computer stores everything as 0s and 1s. Data types are the way computers assign some meaning to these binary digits. Doing this allows us to use those values in particular ways, such as numbers and text. There are four main data types you should understand for the exam: strings, integers, real (fractional) numbers, and Booleans.

Strings

Strings are text fields that are just a series of characters and are denoted with quotation marks around the string field. Any character, number, or symbol can be part of a string. When numbers are part of a string, then they will be considered to be text, like in a street address. In this case, you cannot use them in calculations because they are text fields, not numbers. There are many processes that are commonly done with strings, and most programming languages include prewritten procedures providing this functionality.

• Concatenating strings means “adding” them or “gluing” them together.

For example, suppose we have the following two strings stored in the variables msg1 and msg2.

Concatenating them would produce: Coding is great!

Exam questions may use a procedure format and pass the two strings to be concatenated as parameters. The concatenated value would be returned by the procedure.

Concatenate(firstName, lastName)

A procedure such as the one above would take two strings and return the concatenated version as one string holding a person’s full name.

• Substrings are sections of strings.

You can reference a character in a string using its index, or position in the string. The first letter is the index 1, the second character is the index 2, and so on. Using the example above, the substring of msg2, “is great!”, starting at index 6 and going to the end would be:

eat!

Notice the space between “is” and “great!” gets its own index value. A space is a valid character!

You may see questions about substrings on the AP exam in the format:

ProcedureName(string, start, length)

ProcedureName would be the name, such as Substring, given in the question for the procedure.

As the first parameter, string would be the variable to use in the substring operation.

The second parameter, start, is a parameter that tells us the first index position of our new substring.

The last parameter, length, represents how many index positions to include in the new substring.

For example, if a variable msg1 holds the value “Coding”, then calling the procedure Substring with the following start and length would give us:

msg1 ← “Coding”

Substring(msg1, 1, 3) would return: “Cod”

Integers

Integers are whole numbers. (They do not have a decimal point.) Integers can be used in mathematical operations and expressions, whereas strings (text fields) cannot.

“Fractional” Numbers

These are numbers with a decimal point, even if a number has 0 (zero) for the decimal value, such as 52.0. These numbers can also be used in mathematical operations and expressions.

Mathematical Processes

Most programming languages include mathematical operations. For the AP exam, you need to understand the basic math functions of:

Modulus math uses division but only provides the remainder as the answer, not the quotient.

MOD is the symbol used for modulus math in many programming languages and is how you will see it on the AP exam for this course.

A common use for “MOD math” in programming is to find even or odd numbers. A number that is divisible by 2 with a remainder of 0 is even. An IF statement could use this test in its condition:

IF num MOD 2 = 0 The condition is true if the current value of the variable num is even.

Assignment Statements

To assign a value to a variable, the assignment operator is used. In many programming languages, a single equals sign, =, is used as the assignment operator. For this AP exam, the left-facing arrow, ←, is used. The variable name is always on the left of the ← sign. The programming language will evaluate the right-hand side of the assignment operator and then place the value into the variable on the left-hand side of it. The format to assign a value to a variable for text and block coding on the AP exam is:

The previous value stored in a variable is overwritten by a new assignment statement. In this example, a variable named score is assigned the value 10. It is then assigned the value 11. The value 10 is gone and no longer available.

Just like in your math class, expressions are calculations to be evaluated to an answer or single value. In computer science, the value is then assigned to a variable if the value will be needed later. It also could be displayed on a screen or printed.

You will get an error if you write:

5/9 * (fahr — 32) ← celsius

The variable must be on the left and the assignment arrow points left.

The expression will be evaluated and loaded into the variable celsius.

P Parentheses

E Exponents

M Multiplication

D Division

A Addition

S Subtraction

NOTE: MOD has the same precedence as multiplication and division.

The order of operations PEMDAS (see above) used in math is followed by programming languages. It is always better to use parentheses to ensure the correct order of processing for a mathematical expression.

f — 32 * 5 / 9 does not provide the same value as (f — 32) * (5 / 9).

Boolean Values

Boolean values are one of the foundations of computer code. Understanding Boolean is important for writing correct, readable, and efficient code. Boolean values can only be true or false, needing only one bit to represent its value. Relational operators are used with Boolean values. These are just like in your math class:

= equal

≠ not equal

> greater than

< less than

≥ greater than or equal to

≤ less than or equal to

Two values are compared based on the relational operator and determined to be true or false. For example, if we assign values to variables num1 and num2:

num1 > num2 evaluates to false because at this moment, num1 is 5 and num2 is 10. Five is not greater than 10.

Compound Conditional Statements Using Logical Operators: AND, OR, NOT

Boolean expressions can be simple or compound. Multiple expressions can be combined using the logical operators AND, OR, and NOT. These also evaluate to either true or false.

AND LOGICAL OPERATOR To be true, both of the operands on either side of the AND operator must be true when evaluated individually. In the example below, “licenseEligible” will be set to true only when the age is greater than or equal to 16 and the Boolean variable “learnersPermit” is true. Otherwise, “licenseEligible” will be set to false.

licenseEligible ← (age ≥ 16) AND (learnersPermit = true)

These will be on the AP exam and are on the Exam Reference Sheet as:

OR LOGICAL OPERATOR For the OR operator, either or both of the operands can be true for the condition to be true. In this example, if the day is a Saturday OR the month is July, then the sleepLate variable will be true. The day can be any day as long as the month is July, and the month can be any month as long as the day is Saturday for sleepLate to be true.

sleepLate ← day = “Saturday” OR month = “July”

These will be on the AP exam and are on the Exam Reference Sheet as:

NOT LOGICAL OPERATOR With the NOT operator, if a condition was true, then NOT makes it false. If a condition was false, then NOT makes it true.

This will be on the AP exam and is on the Exam Reference Sheet as:

You can have a single Boolean value or a Boolean expression as either operand using the logical operators AND and OR. For example:

(time = 1800) AND (dog = true AND currentTemp < 80)

time = 1800 evaluates to true or false as a single Boolean value

dog = true AND currentTemp < 80 both have to be evaluated first and compared with AND. The result of that as a Boolean is then used as the right-side operand of the first AND.

Let’s assume the time is 1800 (6:00 p.m.), so that is true.

Let’s assume we do have a dog, so that is true.

The currentTemp is 82, so (currentTemp < 80) is false.

Our Boolean expression evaluates to:

true AND (true AND false)

The right-hand side (true AND false) must be evaluated and is false. Remember, both operands must be true for an AND to be true.

true AND false

Finally, the overall condition is evaluated with AND. Both sides are not true, so it evaluates to:

false

I have a dog, and we usually walk at 6:00 p.m., but if it is too hot for her paws on the asphalt, we’ll go later!

Program Statements

Here’s some great news! All programs can be written using a combination of only three types of statements. These statements are used over and over and can be combined for more complex needs, but there are only three! They are:

• Sequential

• Selection

• Iterative

Sequential

These are statements that are executed as written in order in the program. As we start writing our programs, a code statement has an action that will be executed when the program is run. Once a statement is complete, the next statement is run. Naturally, they have to be in the correct order to accurately complete the algorithm. Think of the result if the steps for a recipe or solving an equation were out of order! And if you have the other two types of statements, selection and iteration, then you also have sequential statements.

Selection Statements

These are a key component to many programs. They use the “if (condition)” structure, and the evaluation of the condition uses Boolean values. As we know, Booleans can only be either true or false, so the program statements associated with the condition only run when the condition at that moment evaluates to “true.” This changes the flow of the program from every statement running sequentially to filtering out some of the code that will execute, based on the Boolean value.

These are written on the AP exam as:

Notice that the code to be executed when the condition is true is surrounded by the curly braces, { }, in the “Text” version. The code within the braces is indented, which helps with readability. It also makes it easier to see if you are missing a closing brace }!

For example:

When the condition evaluates to false, the code within the braces is skipped. Sometimes we want to execute different code when the condition is false. We have a way to do that! Each IF statement can also have an ELSE statement. The ELSE is optional, but when included, it must be part of an IF statement’s structure. The statements associated with the ELSE will only run when the IF condition is “false.” Notice that the code to run for the ELSE is included in its own set of curly braces { }. The code within the braces is also indented, which helps with readability.

These are written on the AP exam as:

Example 1:

Example 2:

Example 3:

This could also be written as:

There are often cases where there are multiple possibilities in a condition. One example is converting a number grade to a letter grade. Depending on the student’s number average, the letter grade could be an “A,” “B,” “C,” “D,” or “F.” An IF condition can handle all those possibilities using nested conditional statements. ELSE IF is used in conjunction with an IF when there are multiple options. Using our letter grade example, let’s set up the conditions.

There is no limit on the number of “ELSE IF” statements you can have in a program. Notice that each “ELSE IF” has a condition to evaluate. Only the “ELSE” statement does not have a condition. The braces and indentation are also used to identify the code that will be run when a particular condition is true.

Once a condition evaluates to be true in the nested IF structure, the code associated with that condition is run and the rest of the ELSE IF conditions are not tested. The IF statement is over at that point. The program continues with the next line of code after the complete IF statement or terminates the program if there are no other lines of code.

You could write multiple IF statements rather than use an IF/ELSE IF structure. However, each individual IF statement’s condition would be evaluated. Every condition that is true would then run the code associated with it. This is less efficient, especially if you have large datasets to process. It could also produce unexpected results. For example, let’s rewrite our letter grade code to use multiple IF statements and see what happens.

In this case, if our average was 92, then each letter grade except “F” would print because each condition would be true. The algorithms appear very similar, but this version provides different as well as incorrect results. To get the correct results, we need to modify the structure and use a range in our condition.

You can write the same algorithm in different ways and each can still be correct. Similarly, different algorithms can be written to solve the same problem, just in different ways.

In your Create project, you may have had ELSE IF statements. These will not be tested on the multiple-choice questions on the AP exam.

Iterative

Iterative statements are also referred to as repetitive statements or loops. This type of programming statement also changes the sequence of lines of code that are executed. Code that is associated with these statements repeats as many times as specified before continuing with the rest of the program.

Among several benefits of loops is that the code will be shorter because we can avoid duplication. This also makes the code more readable and easier to understand. Also, if we need to correct an error or make an update, we only have to do this in one place.

You are responsible for understanding three types of loops for the AP exam. The “REPEAT n TIMES” and “REPEAT UNTIL (condition)” are covered here. The FOR EACH loop is covered in a future section in this chapter.

REPEAT n TIMES Loop

This loop will repeat a specified number of times: “n” is a variable that must be set to a positive integer for the loop to run. The code that is repeated is indented underneath the REPEAT statement and within the braces, { }, just like with the IF/ELSE statements. The braces, { }, are required for loops in this course. The indentation is good programming practice.

This is the format you will see on the AP exam.

This example repeats for each player and displays the player’s name and jersey number. In this case, the display screen could be the large screen in a stadium.

REPEAT UNTIL (Condition) Loop The REPEAT UNTIL loop has a condition to evaluate at each iteration of the loop.

The loop will continue to run while the condition evaluates to “false.” This is similar to how an IF statement works except the condition for the IF statement must evaluate to true for it’s code to execute. However, remember that IF statements execute once. REPEAT UNTIL loops can execute multiple times or not at all, depending on how the condition evaluates.

Each iteration or pass through the loop must change the condition. If we did not have this, we would end up with an infinite loop. With an infinite loop, the condition never has a chance to change to “true,” so it continually repeats. Eventually your computer’s resources are used up and it crashes. (A restart of your computer will free up the resources.)

This is the format you will see on the AP exam.

Example:

If the condition is initially true, the code in the loop will not execute at all. In the following example, num is initialized to the value 10. When the REPEAT UNTIL condition is evaluated, num > 5 is true, so the loop will never be run. The program will skip the loop and continue with the next line of code after the closing brace, }.

You can also have a loop of any type within another loop.

Combining Algorithms

One of the key features of algorithms is that once they are created, you can use them over and over, combine them for more complex problem solving, or modify them for a new use.

For example, you can create an algorithm to ask a user to select a menu option by typing in the number.

• To ensure the user typed in a correct number, you could call a different algorithm to check for a valid number.

• If the number is not valid, call a third algorithm to display an error message.

• If the number is valid, call the algorithm to process the selected option.

Each of these algorithms can work in a variety of different scenarios. By creating them and ensuring they are accurate, using them to solve a different problem in a new algorithm saves time and helps ensure the new algorithm produces accurate results.

Common Algorithms

There are common algorithms that are helpful to know. You can easily implement one when needed, which can help speed up development of the program. These include:

Determining the maximum or minimum number from two or more numbers.

The pseudocode for the maximum of two numbers is:

Compare the numbers.

Store the larger number as the maximum.

For the minimum of two numbers:

Compare the numbers.

Store the smaller number as the minimum.

If you have more than two numbers, a computer can still only compare two at a time. One number would be the current largest (or smallest), and the other would be the next number to compare it to.

Another common algorithm is calculating the sum and average of a group of numbers. This is fairly straightforward since it is a concept you have already learned in math class. One key element to remember is that you need to keep count of how many numbers you have added together so you will be able to calculate the average. The pseudocode for this algorithm is:

1. Set counter and sum to 0.

2. Get the current number.

3. Add it to the existing sum and store the new value back into the variable sum.

4. Add 1 to the counter.

5. Repeat steps 2—4 until all numbers have been added and counted.

6. Divide the sum by the counter to calculate the average.

7. Display the sum and average.

A frequent use for “MOD math” in programming is to find if one number is divisible by another. For example, a number that is divisible by 2 with a remainder of 0 is even.

Robots

This course and exam also cover the movements of robots through a grid. There are four commands you are responsible for understanding and using. These are included in the Exam Reference Sheet, which you will have a copy of during the exam. The triangle represents the robot’s starting point and the direction it is facing.

One command the robot can follow is MOVE_FORWARD. The robot moves one step forward in the direction it is already facing. If the command would place the robot in a blacked-out box or past the border of the maze, the command cannot be executed. This is how the command will appear on the exam.

The robot can also rotate left or right. The robot only changes the direction in the square it is already in. It does NOT move forward. Many students forget that and also move the robot forward.

Finally, there is a command, CAN_MOVE, that we can use to determine if the robot can make a valid move forward before moving. It returns a Boolean value, true or false. The mazes often have boxes blacked out. This means that the robot cannot land on or pass through those.

CAN_MOVE can be used in an IF statement in your code to navigate through the maze. This command takes a parameter that indicates the direction to test. Valid values for the direction parameter are:

• left

• right

• forward

• backward. Remember that to go backward, you can turn left or right twice. Each turn is 90 degrees, so two commands would be 180 degrees, or back toward the direction the robot came.

Example to solve the grid above:

You can expect to see questions in a couple of different formats. One way is to provide the code and a starting point for the robot. The question asks where the robot would end up after the code executes. You would have four possible solutions to select from. Don’t forget to consider which direction the robot would be facing at the end! That is one “gotcha” for many students.

Another common format is to provide a maze with the starting and ending points marked. The solutions provide different chunks of code. You are asked which set of code would correctly move the robot through the maze.

Lists

Lists are a collection of items, such as a grocery list or a playlist of music. A list in a program can be a collection of numbers, words, phrases, or a combination of these. Usually a list only contains one type of data in a single list, but some programming languages do allow different types of data in the same list. Lists provide the ability to store more than one value in the same variable, separated by commas, when the variable is defined as a list. This makes designing a solution and processing items in a list much easier! The list is a generalization (or abstraction) of a group of values, numbers, or strings that can be used in certain ways. Lists are also called arrays in some programming languages.

On the AP exam, you will see these notations for lists.

Create a new list that is empty:

Create a new list and initialize it to the values listed.

value1 will be the first item in the list, value2 is the second item, and so on.

Copy all the values from list1 to list2. If list1 contains the values [5, 10, 15], then after the statement is executed, list2 will exist and contain the values [5, 10, 15].

List Indices

Individual items in a list are called elements and are accessed by position using an index. Index positions are always integers and are enclosed within square brackets [index]. For the AP Computer Science Principles exam, the list index starts at 1. This is different from many programming languages, so be alert to this on questions!

On the AP exam, the format to access an element of a list will look like:

You can assign a value directly to a list position using the index. This code assigns the string “popcorn” to index position 1 of the list snacks and the value in the variable fruit, which holds the string “grapes” to index position 2.

The list snacks will look like this: [“popcorn”, “grapes”]

The AP exam format to assign a value to a list element is:

You can also assign the value stored in a list to another variable. Here the variable favFruit will be assigned the value currently in the second element of the list, which is “grapes.”

favFruit ← snacks[2]

The exam format for assigning a list element to a variable looks like:

If you attempt to reference a position in the list that does not exist, your program will end with an “index out of bounds” error. It could be an index value less than 1 or an index value higher than the length of your list. If our list of snacks is:

To assign the value of one list element to another list element, use the same format where the element indicated is through the index position. The current value in the list element is overwritten with the new one. The element in the index position you are writing from does not change!

Example:

snacks[1] ← snacks[4]

Our list now becomes: [“cheese”, “grapes”, “chips”, “cheese”, “nuts”]

Built-in Methods

Most programming languages will have built-in procedures, or “methods,” of common functionality to use with lists. These generally include functionality such as:

• Adding an item to a specific position in a list. The INSERT command causes elements to the right of the indicated index position, i, to shift right one position to make room for the new element. Nothing is overwritten. The new value is inserted into the given index position, and the size of the list is now one element longer.

Example:

If we have a list:

numbers ← [1, 3, 14, 15]

The command:

INSERT (numbers, 3, 5)

Will change our list to be:

numbers ← [1, 3, 5, 14, 15]

• Appending an item to the end of the list. The APPEND command will add the new element to the end of the list, so no index position is needed. The size of the list increases by one.

Example—using our same list of numbers:

numbers ← [1, 3, 5, 14, 15]

The command:

APPEND(numbers, 29)

Changes our list to be:

numbers ← [1, 3, 5, 14, 15, 29]

• Removing an item from a list. The REMOVE command deletes the element at the provided index position and shifts the remaining elements one position to the left. The size of the list decreases by one.

Example—using our list of numbers:

numbers ← [1, 3, 5, 14, 15, 29]

The command:

REMOVE (numbers, 2)

Changes our list to be:

numbers ← [1, 5, 14, 15, 29]

• Length. The length of a list is the number of elements in the list.

Example—using our list of numbers:

numbers ← [1, 5, 14, 15, 29]

The command:

LENGTH (numbers)

Returns the value 5 because there are five elements currently in the list.

This number can be useful in processing items in a list. You can use references such as:

snacks[LENGTH(snacks)]

to access the last item in the list without having to know the length in advance. First, the value LENGTH(snacks) is evaluated and returns the number 5 for our current list. Our statement now looks like: snacks[5], which is the value “nuts”.

With thousands or millions of elements in a list, we can’t count them all. Even with a few dozen, people would occasionally make mistakes, and it would take so much longer than the split millisecond a computer would take. Write the code and let a computer do it!

There are many other built-in methods, and you should become comfortable with looking these up along with their format for programming languages you use in the programming language documentation.

Checking Each Item in a List

The FOR EACH loop is the third type of iterative statement you must know for the AP exam.

FOR EACH item IN list

The above statement is a loop that will automatically repeat the code for each element in the list. This is called traversing a list. The programmer chooses the name for the iteration variable “item”. Each pass of the loop will assign the value of the next element in the list to the variable “item”. Processing lists with a FOR EACH loop takes advantage of features of both structures.

The format for the AP exam is:

For example, let’s define a list and initialize it to various fruits.

fruit ← [“kiwi”, “grapes”, “peach”, “pineapple”, “orange”]

We can set up a FOR EACH loop to process each element in our list. This FOR EACH loop will repeat once for each element in our fruit list, in this case, 5 times.

With each pass, the variable food will take on the next element in the list. We can then add “IF” conditions or other statements to process the elements. When the list element stored in food is “watermelon” or “pineapple”, the condition in the IF statement is true and a message will be displayed. The table shows each numbered pass through the loop, the value of the variable food with each pass, and the Boolean result of evaluating the condition.

The FOR EACH loop stops after the last element in the list has been processed. You will not get an “index out of bounds” error nor will you have an infinite loop when processing a list with the FOR EACH loop.

NOTE: The Exam Reference Sheet that you will be given for the exam has information about lists and the FOR EACH loop.

Common Algorithms

There are algorithms that are frequently needed for processing lists with iteration. These include finding the largest or smallest number in a list. Here is an example using a REPEAT UNTIL loop with a list of grades.

Another common algorithm is finding the sum and average of the values in a list. This example uses block programming like you would see on the AP exam.

Notice that we did not have to count the number of items in the list. We used the LENGTH() method to count for us!

Searching

Searching deals with finding the needed element from everything in the dataset or determining that it is not there. There are several common algorithms that have been written to search for items in a list. You are responsible for understanding two of them: linear and binary searches.

LINEAR SEARCH Linear searches, also called sequential searches, check each individual record, starting at the beginning and going to the end, one after the other in order to either find the desired data or to determine it is not in the dataset. Such a search is easy to understand and simple to implement, and it does not matter if the data is sorted. With a linear search, the best case is if the item is first in the list; the worst case is if it is not in the list at all. It is easily implemented using the FOR EACH loop.

Search for 10

FOR EACH num in list

BINARY SEARCH Binary searches are far more efficient than linear searches. However, data must be sorted to use a binary search. The binary search is considered a “divide and conquer” algorithm because it divides the dataset into two equal parts. Feedback about whether the value in question is higher or lower than the midpoint of the list determines which half to discard and which half to continue searching. The dividing and searching steps are repeated until the value is found or determined to not be in the list.

For example, if we are looking for a number in a list of integers from 1 to 100, we can find it within 7 searches. The binary search method is that efficient! Let’s look for the number 42, and remember our list has to be sorted for the binary search to work.

Our first guess would be 50, the midpoint of the list.

The feedback would be that our number is lower, so we throw away numbers from 50 to 100.

Our second guess would be 25, the midpoint between 1 and 49.

The feedback would be that our number is higher, so we throw away numbers between 1 and 25.

Our third guess would be halfway between 26 and 49, or 37.

The feedback is that the number is higher, so 26—37 is gone.

Our fourth guess is halfway between 38 and 49, or 43.

The feedback is lower, so our fifth guess is halfway between 38 and 42, or 40.

The feedback is higher this time, so we know our number is either 41 or 42.

If we guessed 41, the feedback is higher, and on the seventh guess, we get the correct number, 42!

Since our first guess is in the middle of the list, a REPEAT UNTIL (item is found) loop works better for the binary search. The binary search is so efficient that you can find a number within 10 guesses in a list of 1,000 numbers. Make sure you follow the binary search algorithm for it to work!

You will not have to analyze algorithms on the AP exam but you will need to recognize the common ones included in this course.

Procedures

Procedures are also called functions in some programming languages. These are sections of code that will be executed only when they are called by the main program or another procedure. They must be defined in a program before they can be used in the program.

There are several benefits of using procedures.

• Reuse of code reduces the length and complexity of programs by not duplicating code.

• Procedures increase the ease of maintaining or fixing programs because you only have one place to update code rather than several.

• Use of shorter blocks of code that do only a few tasks makes the code more readable and easier to understand.

When you find yourself needing the same section of code more than once in a program, that is a clue that you should put the code in a procedure. You can then use it as many times as needed in your program by calling it. Procedures should have descriptive names to help identify their purpose.

The format for defining a procedure on the AP exam is:

Parameters/Arguments

The use of parameters can make procedures more flexible. Parameters allow the calling program to send values to the procedure. They are passed to the procedure as arguments when the procedure is called. The values sent to the procedure can be different each time, making the procedure more flexible through the ability for multiple calls to the same section of code.

The values sent to the procedure must be sent in the same order that the parameters are defined, if there are multiple parameters. They also must be of the same data type (number or text field) that the procedure is expecting. If a number is expected and the procedure receives a string, then an error will occur. The number and type of parameters are identified when the function is defined.

For example, if we define a procedure to calculate the amount owed for a purchase, we would need to know the item name, represented by a string field, the price, which would be a decimal number, and the quantity, an integer. These are parameters because this information would need to be passed to the procedure each time it is used as the quantity and price would vary for each item.

PROCEDURE checkOut (item, price, quantity)

The parameters are: item, price, and quantity.

Calling a Procedure

When the procedure is “called,” the program will pause at that location and execute the code in the procedure. When the procedure finishes, control returns back to the line of code where the call occurred. This is another programming structure that modifies the sequential flow of the program.

You call a procedure by its name and include parentheses. Any arguments are passed in the parentheses, separated by commas. The AP exam will show procedures being called with arguments using the format:

procedureName(arg1, arg2, . . . )

The call to the procedure checkOut for 5 cookies at $1.19 each would be:

checkOut(cookie, 1.19, 5)

The arguments are: cookie, 1.19, and 5.

Recall that abstraction is the removal of details to make something more general and therefore more flexible. This is exactly what procedures do in programs. Details are abstracted away so the procedure is more general and can be used multiple times. Once a procedure is working, you don’t need to worry about how it works, just that it does. The details of how it works are abstracted away. You only need to know the name of the procedure, the number and type of parameters, and the output to expect. This is called procedural abstraction.

Return

Procedures have an optional feature called a return statement. The return statement has two uses. One purpose is to end a procedure before the end of the code is reached. No other code in the procedure will be executed after the return statement. The other use is to send a value back to the calling program.

The format for the RETURN statement on the AP exam is:

Procedures may perform a calculation or collect data in the procedure and need to send it back to the calling program. To do this, the data value or variable name is included in the RETURN statement. The procedure can also use an expression in the RETURN statement. The expression will be calculated prior to the RETURN being executed and only the value will be sent back to the calling program. When the RETURN statement is run, the procedure ends and control is returned to the calling program along with the value sent back, if any.

This RETURN statement calculates the area of a circle but does not store it in a variable. It sends the value calculated back to the code where it was called.

The RETURN statement in this example sends back the value currently stored in the variable, area.

When a procedure is called expecting a value to be returned, that value must be stored in a variable so it will be available to use elsewhere in the program. Otherwise, it is lost in cyberspace and cannot be retrieved. Just as we can execute a calculation with an assignment statement and store the end result in the variable, we can use the same format with a call to a procedure. The program will see the call to the procedure, pause the program to execute the procedure’s code, and then store the returned value in the variable.

variable ← procedureName(arg1, arg2, . . . )

Using our checkOut procedure, we would store the amount due for the item in a variable.

toPay ← checkOut(cookie, 1.19, 5)

The format for defining a procedure with a RETURN statement on the AP exam is:

Built-in Procedures

Built-in procedures are prewritten and tested code that are included with the programming language.

DISPLAY()

DISPLAY() is a built-in procedure used for this course on the exam. We do not know how this procedure is coded, only that we can use it multiple times, pass it different types and values to print, and that it works.

The AP exam will show the DISPLAY built-in procedure in the format:

INPUT()

INPUT() is another built-in procedure that you will see on the AP exam. It accepts data from the user, usually from the keyboard. When the programming language sees this command, it will pause the program and wait for something to be typed on the keyboard. As soon as it detects that the “Enter” key has been pressed, it will capture the keystrokes up to that point.

The AP exam format is:

We need to store the user input in a variable to use in our program. Otherwise, whatever was typed is not saved and is lost in cyberspace. It would therefore not be available to make decisions, select options, display messages, or for other features of your program. For example, this INPUT() statement will assign what the user types to a variable called name.

name ← INPUT()

APIs AND “LIBRARIES” For each programming language, there are prewritten programs to provide commonly needed functionality, and these programs are stored in libraries, which are folders with several programs. These could be written by you to reuse in other programs, shared by a friend or classmate, or posted on a trusted website and saved for others to use. The “INPUT” procedure is an example of a built-in program in a library. You have to use it in the way specified, but you do not have to write the “behind the scenes” code to use it in your program, greatly simplifying your program and the time it would take to write it.

Some of these built-in programs are already included in the programming language. There are others that you can import into your program when needed. You will need the exact name of the library to import, and you must import it before using any of the programs in the library to let your program know where to find them. API stands for “Application Programming Interface.” The API documentation provides the information needed to set up the interface and use the newly connected software.

You can always look up the APIs/libraries for the programming language you are using in the program documentation. Documenting the procedures in an API and how to use them is important so others can use them successfully. Some APIs connect various software components. For example, including Google Maps in an app can be accomplished using an API that allows the user of the app to use Google Maps without leaving the original app. This is how businesses provide directions to their location from your location on their website.

RANDOM Generating random numbers is a frequently needed feature in programs. Most programming languages have a library of prewritten code for a variety of random number generators.

num ← RANDOM(1,10)

RANDOM needs two values passed to it using arguments, the beginning and ending range for the selected random number. In this example, the program generates a random number between 1 and 10 inclusive and stores it in the variable num. Inclusive means both the starting and ending numbers are included in the pool of possible numbers. Each time the code is executed, a random number will be generated. Sometimes it could repeat the prior number since it is randomly generated each time, and sometimes it will be different, but it will always be within the given range.

The AP exam format for using RANDOM is:

Simulations

Simulations are designed to represent and mirror the real world for testing. This is an example of abstraction at a very high level. The details are removed to focus on the impact of the conditions to be measured or evaluated during the simulation. The tests and results enable insights, knowledge, and discoveries to be made without constraints that would exist in the real world. For example, flight simulators let pilots test without lives being lost or aircraft destroyed. Anyone working with simulators needs to watch for bias that could be included because of the choices of elements from the real environment that were included or excluded. Different simulations with different elements included or excluded can help determine if bias is present.

Hypotheses can be evaluated and then refined with the use of simulations without real-world impact or constraints. For example, scientific phenomena can be tested in the laboratory, simplifying the environment and functionality tested rather than having to wait for the next real-world occurrence. This reduces cost and saves time. Simulations can be used to test potentially dangerous situations without putting anyone at risk. The simulations can also be modified based on the results of tests and then retested. In a simulated environment, many more tests can be performed and evaluated, leading to new findings, insights, and solutions. To introduce the variability of the real world, simulations often use a random number generator as a factor.

For example, Google Earth is a model of the planet Earth, with topography, borders, roads, cities, and some buildings represented. Simulations could determine the shortest distance to travel between two locations as well as the fastest travel time based on the landscape and infrastructure.

Analyzing Algorithms

To review some vocabulary, a problem is a task that can or cannot be solved with an algorithm. An instance of a problem is a specific example. A decision problem has a yes or no answer. An optimization problem is one that should find the best solution for the problem. We use these terms in determining an algorithm’s efficiency.

Algorithm Efficiency

The efficiency of algorithms deals with resources needed to run it in terms of how long it will take and how much memory will be needed. This becomes especially important with extremely large datasets, and efficiency is usually stated in terms of the size of the input. While the time will vary based on the computer used, general rules are used to determine the efficiency of these algorithms.

You will not be asked about the formal analysis (Big-O) of algorithm efficiency on the AP exam.

Efficiency can be determined by mathematically proving it and informally measured by actually running it on datasets of different sizes and measuring how long it took and the memory resources needed. It checks these based on the number of times the statements execute for the input size.

We have talked about how there can be more than one right solution to a problem in computer science. These different algorithms may all be correct and readable but could have different efficiencies. Sometimes more complex algorithms can be more efficient, and more efficient algorithms may be able to better handle larger datasets. Algorithms that run with a linear, squared, cubed, or other polynomial efficiency run in a reasonable amount of time. In the chart below, notice how rapidly the exponential line becomes almost vertical even while the size of the dataset is quite small. This shows how quickly algorithms with exponential efficiency may not run in a reasonable amount of time.

Limits of Algorithms

Algorithms have limits, and there are some problems for which we do not have efficient enough algorithms to solve. These algorithms can’t run in a reasonable amount of time with our current technology. As the dataset grows large, the algorithm is too inefficient to process the data. The algorithm could work for smaller datasets but needs exponential or factorial time or resources to run for large amounts of data. This can be good, as this is an aspect of cryptography that keeps our personal information private. There are too many options to check each one. We couldn’t have online shopping without it! However, the day may come when these problems can be solved as advances continue to be made in computers.

Often these problems that do not run in a reasonable amount of time can use a heuristic approach. This is an approach that may not be optimal or the best but is close enough to use as a solution. One common example is the traveling salesman problem. Given a list of cities, the goal is to find the shortest path between them all. The algorithm to make a list of every possible path and then choose the shortest one becomes unwieldly very quickly. The heuristic approach is to find the nearest neighbor to a city and take that path. Then find the nearest neighbor to that city and so on. This modified algorithm is achievable in a reasonable amount of time and resource usage, so it is a viable solution.

You will not have to find heuristic solutions on the AP exam. Just be sure you understand the concept.

Undecidable/Unsolvable Problems

A decidable problem is one where an algorithm can be written that results in a correct “yes” or “no” answer for all inputs. Determining if a number is prime is an example of a decidable problem.

In contrast, an undecidable problem does not have an algorithm that can give a correct “yes” or “no” for all cases of the problem. An algorithm may work for some cases, but not all. The halting problem is one famous example of an unsolvable problem. It states that “given an arbitrary computer program, with an arbitrary input, decide whether it has an infinite loop.” (It sounds simple but can make your head spin!)

You will not have to determine whether a problem is undecidable on the AP exam. Just be sure you understand the concept!

Review Questions

Concepts

1. What term describes values that can only be either true or false?

(A) Decidable

(B) Algorithmic

(D) Sequential

2. What is/are used to determine whether code should be run for both “IF” statements and “REPEAT UNTIL” loops?

(A) Pseudocode

(B) Iterations

(D) Events

3. Which combination of statements can be used to express algorithms?

(A) Iterative, sequential, and selection

(B) Correctness, efficiency, and clarity

(D) Selection, conditional, and Boolean

4. What type of problem cannot currently be determined or explained by an algorithm?

(A) Indefinite problem

(B) Undecidable problem

(D) Unreasonable problem

5. When is a compound condition using the logical operator AND true?

(A) When either of the conditions are true

(B) When both conditions are false

(D) When the NOT operator is also used

6. Which type of loop runs a set number of times?

(A) Indefinite

(B) REPEAT UNTIL

(D) REPEAT n TIMES

7. Why is a “divide and conquer” search more efficient than a linear search?

(A) You only look at half the dataset.

(B) You eliminate half the dataset with each iteration.

(D) It divides the data into two sections based on even and odd index values.

8. Sequential statements

(A) run one after the other in the order given.

(B) run only when the condition is true.

(D) run until the user enters “done.”

9. Else statements

(A) run each time an “if” condition is true.

(B) run when an “if” condition is false.

(D) do not need an “if” statement to run.

10. With a problem that cannot be solved for all cases, what can sometimes be used as a close approximation?

(A) A travelling solution

(B) A solvable solution

(D) A tractable solution

11. What are variables used for in programs?

(A) They hold values: numbers, Booleans, or strings.

(B) They link libraries of programs to the current program.

(D) They hold the indices for a list name.

12. How can an individual element in a list be identified?

(A) Use the index or number of the element’s position in the list.

(B) Use the built-in procedures for lists.

(D) Use the list name plus the value in the list at the needed position.

13. How do parameters and arguments differ?

(A) The words can be used interchangeably.

(B) Parameters are sent to procedures where they are then used as arguments.

(D) Arguments are the intermediate values in a calculation until the calculation is complete and then stored in the parameter.

14. What is a reason to use a procedure?

(A) When you need a section of code once in a program

(B) To avoid duplicating code

(D) To use with a condition

15. How are assignment statements processed?

(A) The left side of the ← is processed and then assigned to the variable on the right.

(B) The right side of the ← is processed and then assigned to the variable on the left.

(D) Numbers are processed first and then strings.

16. What helps manage complexity in a program by abstracting out the details and allowing programmers to use variable names?

(A) Data abstraction

(B) Element abstraction

(D) Procedural abstraction

17. What is string1 concatenated with string2 when:

(A) Tik Tok

(B) “Tik” “Tok”

(D) “TikTok”

18. If the variable name has the value “Hannah”, what is the value if we take the substring of name starting at position 4 and going to the end?

(A) “ah”

(B) “Hann”

(D) “nah”

19. With Boolean, what does “A OR B” mean?

(A) Neither A or B can be true for the condition to be true.

(B) If A is true, then the condition is true.

(D) Both A and B must be true for the condition to be true.

20. Which are more abstract: high-level or low-level programming languages?

(A) High-level

(B) Low-level

(D) Neither are abstract.

21. Procedures are abstract:

(A) By the use of parameters

(B) By being easier to manage

(D) All of the above

22. How are simulations useful?

(A) They allow the modification of multiple variables at a time to determine what changes make the most impact.

(B) They provide the freedom of testing all possibilities without interference.

(D) They allow testing of hypotheses without impacting or being impacted by the real world.

23. What does an API provide?

(A) The pseudocode for commonly used algorithms

(B) A way for apps or programs to communicate with each other

(D) The program code for commonly used modules

Application of Concepts

24. How can a smaller representation of something, such as an event or process, be used to determine what could happen in the real world?

(A) Through simulations

(B) Through planning

(D) Through the use of lab work

25. What is the output of the algorithm written in pseudocode below at 7:00 a.m. Friday?

If Monday—Friday at 8:00 a.m.

Set thermostat to 62

If Saturday or Sunday

Set thermostat to 70

If time is 5:00 p.m.

Set thermostat to 68

(A) 62

(B) 68

(D) Unknown

26. The algorithm below is not working correctly. Which line of code will make it work as intended?

(Compare cars to available parking spots)

(A) APPEND(parkingLot, availSlot)

(B) REMOVE(parkingLot, availSlot)

(D) REPEAT UNTIL (LENGTH(parkingLot) = LENGTH(availSlots))

27. Which line of code can be placed inside the braces { } to fix the following loop so it will not be an infinite loop?

(A) IF name ≠ “done”)

(B) count = count + 1

(D) name ← studentRoster

28. Below is a flowchart of an alarm clock snooze process. What value does the variable “count” have after tracing through the flowchart?

(A) 0

(B) 4

(D) Count ← Count + 1

29. Are the two conditional statements equivalent?

age > 42 NOT (age < 42)

(A) Yes

(B) No

(D) Only when age is 0

30. What are the elements in the list “fruit” after the code below?

(A) grapes, mango, apples, blueberries, kiwi

(B) oranges, mango, apples, blueberries, kiwi

(D) bananas, mango, apples, kiwi, grapes

31. What is the result of executing the following code when called with LeapYear(3004)?

(A) 3004 is not a leap year.

(B) 304 is not a leap year.

(D) Invalid year entered.

32. Which block of code sets the alarm for each day of the week?

(A) Block 1

(B) Block 2

(D) Neither Block 1 nor Block 2

33. What is returned from the procedure below after the call: weight (9, 10, 11)?

(A) 9

(B) 10

(D) 1011

34. What type of algorithm is the following code using?

(A) Binary search

(B) Bubble sort

(D) Merge sort

35. How are procedures a form of abstraction?

(A) By being able to use a procedure without knowing how it works

(B) By understanding the code in a procedure to use it correctly

(D) Through eliminating the use of comments to make the code more abstract

36. At which ending location does the code place the robot?

Answers and Explanations

1. C—Boolean values can only be either true or false.

2. C—Conditions can be used to determine whether code should be run for both “IF” statements or “REPEAT UNTIL” loops. The conditions evaluate to True or False and processing continues based on the Boolean value.

3. A—Algorithms can be expressed using a combination of iterative (loops), sequential, and selection (IF) statements.

4. B—Problems that cannot currently be solved by an algorithm are called undecidable.

5. C—A compound condition using the logical operator AND is true when both conditions are true.

6. D—A “REPEAT n TIMES” loop will run “n” times, where “n” must be a positive integer.

7. B—A “divide and conquer” search is more efficient than a linear search because you eliminate half of the dataset with each iteration.

8. A—Sequential statements run one after the other in the order given.

9. B—“Else” statements run when an “IF” condition is false. They are skipped when the IF condition is true.

10. C—A heuristic solution can be used with an unreasonable problem that cannot be solved for all cases. It provides a “close enough” solution.

11. A—Variables are used to hold values, which can be numbers, Booleans, or strings in programs.

12. A—An individual element in a list can be identified using the index, which is the number of the element’s position in the list.

13. C—Arguments are sent to procedures, where the values are then passed to the parameters that are local to the procedure.

14. B—One reason to use a procedure is to avoid duplicating code, because the procedure can be resused as many times as needed in a program.

15. B—Assignment statements process the right side of the ←, which is then assigned to the variable on the left.

16. A—Data abstraction manages complexity with the use of variable names and lists to reference and update data values without needing to know the details of computer memory and addresses.

17. D—Concatenate means to glue two strings together. No additional spaces or new lines are added between the strings. Therefore, string1 concatenated with string2 becomes “TikTok”. The quotation marks indicate that it is a string rather than a variable name.

18. D—The index positions for the string “Hannah” are shown in the table below. If we take the substring of name starting at position 4 and go to the end, we have the string “nah”.

19. B—OR means either or both conditions can be true for the condition to be true. Since A is true, then the entire condition is true.

20. A—High-level programming languages are more like natural language than low-level ones. The commands in the language are more general and therefore more abstract than low-level languages, which are closer to machine language.

21. D—The use of parameters allows a procedure to be called multiple times and apply the same code to different values. Descriptive names for procedures help identify their general function. Therefore, all of these are reasons why procedures are abstract.

22. D—Hypotheses can be evaluated without the constraints of the realworld and without adversely impacting the real world.

23. B—The API provides the details for how to use the program modules it is associated with.

24. A—Models can be used to test events through simulations on a smaller scale to help determine the impact of the same event in real life.

25. B—The temperature on Friday morning at 7:00 a.m. will still be 68 degrees from the third “IF” statement, which set it to 68 degrees at 5:00 p.m. the night before. It won’t change until one of the other “IF” conditions evaluate to true.

26. A—The list, parkingLot, starts out empty. If elements are not placed into the list, then the DISPLAY statement at the end will show an empty list. Either APPEND or INSERT can be used to add elements to a list. However, we do not have the “name” of the person assigned to a parking place, so answer A, to APPEND the number of the available parking slots to the list, is the best answer.

27. C—The variable name is initialized to be an empty text field. This is the variable that is tested in the REPEAT UNTIL condition. An infinite loop will occur unless a way is provided to update the “name” field. The INPUT() command allows the user to enter student names and the value “done” into the “name” variable. This will provide a value to be tested in the condition that will eventually be set to “done” and stop the loop.

28. B—The condition to keep hitting the snooze button tests to see if count is greater than or equal to 4. After count equals 4, the flowchart processing continues to the message that it’s time to wake up without increasing “count.” Therefore, count equals 4 and B is the correct answer.

29. B—The keyword NOT flips the value it references to its opposite. Therefore, if age is greater than 42, the opposite of that is age less than or equal to 42. Many students forget to include or remove the equals sign, =, when they apply the NOT operator. The two expressions do not match, and the correct answer is B.

30. B—Our list starts with one element, “grapes.” The APPEND operation adds the element to the end of the list. The INSERT operation places the element at the index position provided and moves elements to the right, increasing the size of the list. The REMOVE operation deletes the element at the given index position and adjusts the remaining elements down a position. Lists for this course all begin with index position 1. Therefore, the correct answer is B.

31. C—The user keys in 3004 as the year to check. The procedure LeapYear(3004) is called with this value. The MOD function returns the remainder after dividing the two numbers. If the remainder is 0, then the year is a leap year. The ELSE IF statement that uses MOD 4 = 0 is true, so the year is a leap year and the correct message is printed. The correct answer is C.

32. A—Block 1 correctly sets the alarm time for every day of the week. Block 2 sets the correct alarm time for Monday to Friday. The weekend days do not have an alarm time set, which might be our preferred results, but not the question asked. The correct answer is A.

33. B—The first IF statement compares wt1 to the other two values. Since 9 is not greater than or equal to either value, the code moves on to compare wt2, which is 10. This condition is an OR, so only one comparison needs to be true. While 10 is not greater than 11, it is greater than 9. Therefore, the value of 10 for wt2 is returned. The correct answer is B.

34. C—A linear search is used to check each item in the list to see if it equals 42.

35. A—Procedures are abstractions because they can be used multiple times in programs with different values passed in through parameters without needing to know how they work.

36. B—The robot moves forward as long as it can move. If it cannot move, then it rotates left. These steps continue until it reaches the end block pointing right.

Rapid Review

Algorithms are a set of steps to complete a task. Algorithms can be written in natural language, which is our speaking language; pseudocode, which is a combination of natural language and a programming language; diagrammed with a flowchart; and coded in both block (drag and drop) and text-based programming languages.

Programs can be developed for almost any purpose, including for fun and for professional purposes. Programs implement algorithms and use a variety of techniques, such as variables, procedures, and lists, in their processing.

Features to make algorithms more readable and clearer include adding comments, adding blank lines, and using well-named variables and procedures. Variables are a holding place for data. Assignment statements change a variable’s value. Lists, like a grocery list, can store many values in one variable name. Individual elements in lists are referenced using their index position. This exam starts the index position at 1. Programming languages have built-in functions for common processing needs for lists, such as APPEND, INSERT, REMOVE, and LENGTH. These are on the Exam Reference Sheet (see Appendix), and you will have a copy of it during the exam.

The data types used in programs are integers (whole numbers), real numbers (with decimals), Booleans (true or false), and strings (text). String functions include concatenation, or gluing two strings together, and substring, which is taking a section of a string.

Data abstraction allows us to store data using variables and lists. We can use the name we assign, which makes programs easier to code and understand.

The arithmetic operators used in programming are the same as in math: addition, subtraction, multiplication, and division. MOD provides only the remainder after dividing.

All algorithms can be written using a combination of sequential, selection, and iterative statements. Sequential means each step is executed, in order, one right after the other.

Selection statements filter out some lines of code using an IF (condition) statement. The condition uses the relational operators, <, ≤, >, ≥, =, ≠, to make a comparison. The condition will always evaluate to either true or false. These are Boolean values. The logical operators AND, OR, and NOT are used to make more complex conditions.

When the condition is false, the code associated with the IF statement is skipped. An ELSE statement can be added to execute different code when the IF statement’s condition is false. Multiple ELSE IF (condition) statements can be added after the IF to construct a nested IF statement. The conditions will be evaluated until the first one is true. All others will then be skipped. ELSE is always last in the structure.

Iterative statements repeat code. The REPEAT n TIMES loop executes a block of code a specified number of times. The REPEAT UNTIL (condition) repeats the code until the condition is true. It checks the condition at the start of each pass. Just like with IF statements, the condition will only evaluate to true or false, a Boolean value. The FOR EACH loop will repeat the code for each element in a list or string.

Binary searches use a “divide and conquer” technique and can only be used with sorted datasets. Lower or higher feedback is provided to determine the next midpoint. Linear searches check every element to either find the item in question or determine that it is not in the dataset. Linear searches can be used with sorted or unsorted datasets.

Procedures are blocks of code that can be used repeatedly in programs. They can have parameters that provide a way for different values to be passed to them, and procedures can return values processed back to the calling program. Using parameters makes a procedure more general, and therefore more abstract, by enabling it to be used with different values each time it is called to run.

Procedures, once working, can be used by anyone, without them having to understand the code or know how it works. They can trust that it works as expected. This provides procedural abstraction, as all the details of how the procedure works are unknown or abstracted away (the “black box” effect). This helps with program complexity and readability. It also simplifies coding by having only one place to make corrections or updates. Application Programming Interfaces (APIs) connect a program to external software, and import statements pull in libraries of working code to an application, saving time in the development process. These are also examples of procedural abstraction, as you don’t see the source code and can trust that it works as described.

Algorithms can be combined to create a new algorithm. An example is an algorithm to play a video along with the algorithms to provide features to speed it up, slow it down, mute the sound, or display the captions. Be familiar with common algorithms, such as finding the maximum or minimum number, finding the total and average of a group of numbers, and determining if one integer is divisible by another (MOD).

The commands to use to navigate a robot through a maze are MOVE_FORWARD(), ROTATE_RIGHT(), ROTATE_LEFT(), AND CAN_MOVE(direction).

Algorithms can be evaluated for their readability, clarity, and efficiency. There can be more than one correct algorithm to solve a problem, and different solutions can be more efficient with different size datasets. Remember that efficiency includes memory and processing time. There can be trade-offs among different solutions, since more efficient solutions may be more complex and less clear.

Some problems cannot be solved in a reasonable amount of time or with a reasonable amount of resources. As the dataset gets larger, the amount of time and/or memory required becomes too large and is beyond our current capabilities to process. Heuristic approaches can often find solutions that are good enough for the need at hand. Undecidable problems are those that no algorithm can solve for all instances of the problem. There may be solutions for some cases but not all of them.

Simulations enable people to test hypotheses by changing the values of variables with different tests while holding others constant, running multiple tests, and doing so quickly and in a safe environment.

5 Steps to a 5: AP Computer Science Principles 2024 - Sway J.S. 2023

9 Algorithms and ProgrammingSTEP 4 Review the Knowledge You Need to Score High

9 Algorithms and Programming
STEP 4 Review the Knowledge You Need to Score High