APCSP Big Idea 3 Review

AP CS Principles Exam Review

1

Big Idea 3:
Algorithms and
Programming

Exam
Weighting:
30% - 35%

Adapted from:
https://longbaonguyen.github.io/courses/apcsp/apprinciples.html

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

With material from:
Reichelson, Seth. AP Computer Science Principles Premium with 6 Practice Tests
(Barron's Test Prep). Barrons Educational Series.

Big Idea 3:
Programming
and Algorithms, I

2

Big Idea 3:
Programming
and Algorithms, II

3

Big Idea 3: Programming and Algorithms

The AP exam will use a language-agnostic syntax for programming and
algorithm questions.

Please see the following reference sheet (also available during the
actual exam) for more details about the syntax.

https://apcentral.collegeboard.org/pdf/ap-computer-science-principle
s-exam-reference-sheet.pdf

4

Big Idea 3: Programming and Algorithms

In computer science, an abstraction is a way to represent essential
features without including the background details or explanations.
Abstractions reduce complexity and allow for efficient design and
implementation of complex software systems.

Abstractions become a necessity as systems become more complex.
For example, anytime you check your stories on Instagram, you are
using a bunch of processes in the background that you have no control
over.

Without these abstractions, it would be difficult to send a message to a
friend. With the use of abstractions, you can focus on content, not the
technical details of how the application works.
5

Big Idea 3: Programming and Algorithms

Programmers also use abstractions. The purpose of abstraction is to hide
coding details so the programmer can focus on the current problem.

Computers can understand only binary machine code. Machine code is a
strictly numerical language that runs fast but is hard to use.

The code on the right is written in machine
code to outputs "Hello World" to the
screen.

In Python it can be done using the print()
abstraction:
print("Hello World")

6

Big Idea 3: Programming and Algorithms

Abstractions allow for programmers to use semi-human language to
program (Python, Java, etc…).

Rarely will programmers deal directly in machine code. Machine code
is a base language where no abstractions are implemented.
Programmers have worked to hide details by using abstractions.

Different program languages offer different levels of abstractions.
High-level programming languages provide more abstractions than do
lower-level languages.

Coding in a programming language is often translated into code in
another low-level language that the computer can execute.
7

Big Idea 3: Programming and Algorithms

Abstraction Examples Used on the AP Exam:

DISPLAY(expression) is an abstraction that is used on your AP exam to
display a value of expression followed by a space. The input parameter
for the DISPLAY abstraction is expression.

Another abstraction used on your AP exam is RANDOM(a, b), which
evaluates to a random number from a to b inclusive. The input
parameters in this abstraction are a and b.

An abstraction generalizes functionality with input parameters that
allow software reuse. Being aware of and using multiple levels of
abstractions in developing programs helps to apply available resources
and tools more effectively to solve problems.

8

9

Multiple Choice

What is the exam weighting for the AP CS Principles Exam's Big Idea 3: Algorithms and Programming?

• A) 10% - 15%

• B) 20% - 25%

• C) 30% - 35%

• D) 40% - 45%

Multiple Choice

What is the purpose of data abstraction in programming?

• To represent algorithmic processes without using a programming language.

• To evaluate solution options.

• To manage complexity in a program.

• To determine the result of code segments.

Multiple Choice

What is an abstraction in computer science?

• A detailed explanation of how software systems work.

• A way to represent essential features without including background details or explanations.

• A complex software system.

• A type of computer hardware.

Multiple Choice

Why do abstractions become a necessity in computer science?

• Because they make it easier to send messages to friends.

• Because they allow users to control background processes.

• As systems become more complex, they reduce complexity and allow for efficient design and implementation.

• Because they provide detailed technical information to users.

Multiple Choice

What is the benefit of using abstractions when using applications like Instagram?

• They allow you to control the processes in the background.

• They enable you to focus on content without worrying about how the application works.

• They provide a detailed understanding of the technical details of the application.

• They make it difficult to use the application.

Multiple Choice

What is the purpose of abstraction in programming according to Big Idea 3?

• To make the code run faster

• To hide coding details so the programmer can focus on the current problem

• To convert code into binary format

• To output "Hello World" to the screen

Multiple Choice

How can the phrase "Hello World" be output to the screen in Python?

• print("Hello World")

• echo "Hello World"

• console.log("Hello World")

• write("Hello World")

Multiple Choice

What do abstractions in programming allow for?

• They allow for the use of machine code exclusively.

• They enable programmers to use semi-human language to program.

• They prevent programmers from using high-level programming languages.

• They require programmers to deal directly with hardware details.

Multiple Choice

What is machine code considered in terms of abstractions?

• A high-level language with many abstractions.

• A semi-human language.

• A base language with no abstractions implemented.

• A form of high-level programming language.

Multiple Choice

Compared to lower-level languages, what do high-level programming languages provide?

• Fewer abstractions.

• No abstractions.

• More abstractions.

• Direct interaction with machine code.

Multiple Choice

What happens to code written in a high-level programming language for it to be executed by a computer?

• It is directly executed without any translation.

• It is translated into a high-level language that the computer can execute.

• It is often translated into code in another low-level language that the computer can execute.

• It is converted into an abstract form that cannot be executed.

Multiple Choice

What does the RANDOM(a, b) abstraction evaluate to?

• A specific number between a and b

• A random number from a to b inclusive

• The sum of a and b

• The product of a and b

Multiple Choice

What does the operator '+' represent in mathematical operations?

• Subtraction

• Division

• Addition

• Modulus

Multiple Choice

Which example correctly shows the use of the '*' operator?

• 5 + 7 = 12

• 2 - 1 = 1

• 3 * 3 = 9

• 3 MOD 2 = 1

Multiple Choice

What is the result of the operation 3 MOD 2?

• 0.5

• 2

• 1

• 1.5

Multiple Choice

According to the Operator Precedence (Order of Operations), which operation should be performed first?

• Addition

• Division

• Parentheses

• Modulus

Multiple Choice

Which set of operators have the same precedence level?

• +, -

• *, /

• MOD, +

• MOD, *, /

Multiple Choice

What is the value of a after the expression 26 MOD 2 is evaluated?

• 0

• 1

• 2

• 13

Big Idea 3: Programming and Algorithms

10

Multiple Choice

What is the value of a after the expression 17 MOD 2 is evaluated?

• 0

• 1

• 2

• 8

Big Idea 3: Programming and Algorithms

10

Big Idea 3: Programming and Algorithms

11

Multiple Choice

What error is encountered when a zero is to the right of MOD in a modulus calculation?

• No error, the result is 0.

• The result is the value of the dividend.

• DIVIDE BY ZERO error.

• The result is the value of the divisor.

Multiple Choice

Is it feasible to have a zero to the left of MOD in a modulus calculation, and if so, what is the result?

• No, it results in a DIVIDE BY ZERO error.

• Yes, the result is the value of the divisor.

• Yes, the result is 0.

• No, it results in an undefined operation.

Multiple Choice

What will the following program display?

• A) 13

• B) 17

• C) 9

• D) 21

Big Idea 3: Programming and Algorithms

12

Multiple Choice

What will the following program display if the INPUT function reads an even number such as 4?

• 1

• 2

• 0

• 4

Big Idea 3: Programming and Algorithms

13

Multiple Choice

What will the following program display?

• False

• 0

• 3

• True

Big Idea 3: Programming and Algorithms

13

Multiple Choice

What will be the output of DISPLAY(a) after executing the given code?

• 3

• 5

• 14

• 0

Multiple Choice

What will be the output of DISPLAY(b) after executing the given code?

• 3

• 5

• 14

• 0

Multiple Choice

What will be the output of DISPLAY(c) after executing the given code?

• 3

• 5

• 14

• 0

Big Idea 3: Programming and Algorithms

14

Multiple Choice

If the code "a ← RANDOM 1,4" followed by "DISPLAY a = 3" is executed several times, what is the percentage of times "false" would be expected to be displayed?

• 25%

• 50%

• 75%

• 100%

15

Multiple Choice

If the code "a ← RANDOM 1,10" followed by "DISPLAY a ≤ 3" is executed several times, what is the percentage of times "true" would be expected to be displayed?

• 10%

• 20%

• 30%

• 40%

15

Multiple Choice

What is the value at index 3 in the list scores?

• 11

• 35

• 6

• 75

Lists

16

Multiple Choice

According to the content, how do indexes in lists start on the AP exam?

• At 0

• At 1

• At -1

• At 2

Multiple Choice

What will happen if you try to access scores[6]?

• It will return the value 11.

• It will return the value 37.

• It will return an index out of bounds error.

• It will return the value 75.

Lists

16

Lists

17

Multiple Choice

What will happen if you try to access an index in a list that is less than 1 or greater than the length of the list?

• The list will automatically expand to accommodate the new index.

• The program will ignore the operation.

• An error message is produced and the program will terminate.

• A new element will be created at that index.

Multiple Choice

What is the result of the operation a <- newList[0] given the list namesOfMyDogs <- ["Waffles", "Novack the 3rd", "Benji"]?

• a is assigned the value "Waffles"

• a is assigned the value "Novack the 3rd"

• a is assigned the value "Benji"

• This operation causes an error because the index is out of bounds

Lists

17

The INSERT(list, i, item) will insert the item at index i and shift right
items at index i or higher.

18

Multiple Choice

What does the INSERT method do when applied to a list?

• It deletes the item at the specified index.

• It replaces the item at the specified index with a new item.

• It inserts the item at the specified index and shifts right items at index or higher.

• It appends the item to the end of the list.

Multiple Choice

After using the INSERT method with the parameters (words, 3, "Green"), what will the list 'words' look like?

• ["The", "Little", "Frog", "Jumping"]

• ["The", "Little", "Green", "Frog", "Jumping"]

• ["The", "Green", "Little", "Frog", "Jumping"]

• ["Green", "The", "Little", "Frog", "Jumping"]

The INSERT(list, i, item) will insert the item at index i and shift right
items at index i or higher.

18

19

The APPEND(list, item) will add the item to the end of the list.

Multiple Choice

What does the APPEND function do in the context of the list provided?

• Inserts an item at a specified index in the list

• Adds the item to the beginning of the list

• Adds the item to the end of the list

• Deletes an item from the list

Multiple Choice

After performing the operations shown, what is the correct order of items in the 'words' list?

• Fox

• Elephant

• Green

• Pig

• The

Multiple Choice

What is the final position of "The" in the 'words' list after all the operations are performed?

• 1

• 2

• 3

• 4

19

The APPEND(list, item) will add the item to the end of the list.

Line 4: REMOVE(words, 3)
Line 5: DISPLAY(words)

20

The REMOVE(list, i) will remove the item at index i and shift left items
at index i or higher.

Multiple Choice

What is the result of executing Line 2 in the given code snippet?

• 5

• 6

• 7

• 8

Multiple Choice

What does the REMOVE function do according to the description provided?

• It adds an item at the specified index.

• It removes the item at the specified index and shifts left the remaining items.

• It replaces the item at the specified index with a new item.

• It creates a copy of the list without the item at the specified index.

Multiple Choice

After executing Line 3, what will the DISPLAY function show if it is called?

• "Elephant", "Green", "The", "Fox", "Pig", "Rhino"

• "Green", "The", "Fox", "Pig", "Rhino"

• "Elephant", "The", "Fox", "Pig", "Rhino"

• "Elephant", "Green", "Fox", "Pig", "Rhino"

Multiple Choice

What will be the final output after executing Line 5?

• "Green", "The", "Pig", "Rhino", "Fox"

• "Green", "The", "Rhino", "Fox"

• "Green", "The", "Fox", "Pig"

• "Green", "The", "Pig", "Rhino"

Line 4: REMOVE(words, 3)
Line 5: DISPLAY(words)

Answer: ["Green", "The", "Pig", "Rhino", "Fox"]

20

The REMOVE(list, i) will remove the item at index i and shift left items
at index i or higher.

21

Multiple Choice

What will be the output of the given code snippet?

• 96 93 90 100 92 90

• 93 96 90 100 92 90

• 90 92 93 96 100 90

• 96 96 93 90 100 92 90

Multiple Choice

In some programming languages, what is another term for a procedure?

• Object

• Class

• Method or subroutine

• Array

Multiple Choice

What is the initial value of 'count' when the PROCEDURE doubling(list) starts?

• 0

• 1

• 2

• Undefined

Multiple Choice

How many times does the loop inside the PROCEDURE doubling(list) run?

• Once

• Twice

• As many times as the length of the list

• Indefinitely

Multiple Choice

What operation is performed on each element of the list in the PROCEDURE doubling(list)?

• The element is incremented by 1

• The element is decremented by 1

• The element is multiplied by 2

• The element is divided by 2

Multiple Choice

What happens to 'count' after each iteration of the loop in the PROCEDURE doubling(list)?

• It is reset to 0

• It is incremented by 1

• It is decremented by 1

• It remains unchanged

Multiple Choice

What is the purpose of the 'findTotal' procedure in the given code snippet?

• To find the average of the scores

• To display the scores

• To find the sum of the scores

• To count the number of scores

Multiple Choice

What will be the value of 'total' after the 'findTotal' procedure is executed with the given 'scores' list?

• 467

• 475

• 485

• 500

Multiple Choice

What does the 'FOR EACH' statement in the code do?

• It repeats a set of statements for each element in 'scores'

• It adds each item in 'scores' to the sum

• It returns the sum of the scores

• It initializes the sum to 0

Multiple Choice

What is the result of executing the ROTATE_RIGHT() command if the initial robot direction is pointing upwards (▲)?

• The robot will point to the right (►)

• The robot will point downwards (▼)

• The robot will point to the left (◄)

• The robot will make a 180-degree turn

Multiple Choice

What is the result of executing the ROTATE_RIGHT() command if the initial robot direction is pointing to the right (►)?

• The robot will point upwards (▲)

• The robot will point downwards (▼)

• The robot will point to the left (◄)

• The robot will point downwards (▼)

Multiple Choice

What is the result of executing the ROTATE_RIGHT() command if the initial robot direction is pointing downwards (▼)?

• The robot will point to the right (►)

• The robot will point upwards (▲)

• The robot will point to the left (◄)

• The robot will point to the left (◄)

Multiple Choice

What is the result of executing the ROTATE_RIGHT() command if the initial robot direction is pointing to the left (◄)?

• The robot will point to the right (►)

• The robot will point upwards (▲)

• The robot will point downwards (▼)

• The robot will point upwards (▲)

Multiple Choice

What is the result of executing the ROTATE_LEFT() command on a robot facing upwards (↑)?

• The robot will face to the right (→)

• The robot will face downwards (↓)

• The robot will face to the left (←)

• The robot will remain facing upwards (↑)

Multiple Choice

What is the result of executing the ROTATE_LEFT() command on a robot facing to the right (→)?

• The robot will face upwards (↑)

• The robot will face to the left (←)

• The robot will face downwards (↓)

• The robot will remain facing to the right (→)

Multiple Choice

What is the result of executing the ROTATE_LEFT() command on a robot facing downwards (↓)?

• The robot will face to the right (→)

• The robot will face upwards (↑)

• The robot will face to the left (←)

• The robot will remain facing downwards (↓)

Multiple Choice

What is the result of executing the ROTATE_LEFT() command on a robot facing to the left (←)?

• The robot will face upwards (↑)

• The robot will face to the right (→)

• The robot will face downwards (↓)

• The robot will remain facing to the left (←)

Multiple Choice

What happens when the MOVE_FORWARD command is executed with the robot facing a black square?

• The robot moves to the next white square.

• The robot turns to the right.

• The robot moves to the next black square.

• The robot reports an ERROR.

Multiple Choice

When the MOVE_FORWARD command is executed and the robot is facing a white square, what is the next action of the robot?

• The robot turns to the left.

• The robot moves forward to the next square.

• The robot reports an ERROR.

• The robot turns to the right.

Multiple Choice

What is the purpose of the CAN_MOVE(direction) abstraction in the context provided?

• To allow the robot to move in any direction without restrictions.

• To prevent the robot from moving off the grid and resulting in an error.

• To calculate the distance the robot moves in a certain direction.

• To record the number of moves the robot makes.

Multiple Choice

What is the purpose of the Goal_Reached() procedure in the robot's program?

• To move the robot to the gray square

• To return "true" if the robot is in the gray square and "false" otherwise

• To rotate the robot to the right

• To repeat the program until the robot moves

Multiple Choice

What action does the robot take if it can move to the right according to the program?

• It moves forward

• It rotates left

• It rotates right

• It does nothing

Multiple Choice

What will the robot do if it cannot move forward according to the program?

• It will rotate right

• It will rotate left

• It will move to the gray square

• It will stop executing the program

Multiple Choice

What does the procedure Goal_Reached() return when the robot is in the gray square?

• false

• error

• true

• undefined

Multiple Choice

According to the comment in the image, what happens when the robot runs the given code?

• The robot successfully reaches the gray square

• The robot exits the grid

• The robot gets stuck in an infinite loop at the top right corner

• The robot turns off automatically

Multiple Choice

What is the maximum number of times the ROTATE_LEFT() procedure can be called according to the given code snippet?

• 0

• 1

• 2

• 3

Multiple Choice

What is the maximum number of times the MOVE_FORWARD() procedure can be called according to the given code snippet?

• 0

• 1

• 2

• 3

Multiple Choice

How many times does the robot rotate left according to the procedure?

• 1 time

• 2 times

• 3 times

• 1 to 3 times randomly

Multiple Choice

Which of the following is a possible final position of the robot after executing the procedure?

• The square immediately to the left of the starting position

• The square two places above the starting position

• The square immediately to the right of the starting position

• The square immediately below the starting position

Multiple Choice

What is the common algorithm mentioned in the text?

• Sorting

• Searching

• Swapping

• Queuing

Multiple Choice

What will be the result of the swap operation in the animals' data structure?

• animals[1] = frog; animals[3] = sheep

• animals[1] = bear; animals[2] = sheep

• animals[2] = sheep; animals[3] = bear

• animals[1] = sheep; animals[3] = frog

Multiple Choice

What is the first step in the algorithm to swap the first and third items in a list?

• Replace the first item with the second item.

• Assign the third item to a temporary variable.

• Create a temporary variable to store the value of the first item.

• Swap the second and third items in the list.

Multiple Choice

What is done with the first item in the list after creating a temporary variable?

• It is deleted from the list.

• It is swapped with the second item.

• It is replaced with the third item in the list.

• It is moved to the end of the list.

Multiple Choice

After replacing the first item in the list with the third item, what is the next step in the algorithm?

• Replace the second item with the value in the temporary variable.

• Replace the third item with the value in the temporary variable.

• Replace the first item with the value in the temporary variable.

• No further action is required.

Multiple Choice

What will be the output after executing the given pseudocode?

• A list containing all the numbers from list1

• A list containing some numbers from list1

• An empty list

• A list containing all numbers from list1 that are either even or odd

Multiple Choice

What is a linear search also known as?

• Binary search

• Sequential search

• Hash search

• Depth-first search

Multiple Choice

In a linear search, where does the search start?

• At the end of the list

• At a random point in the list

• From the beginning of the list

• In the middle of the list

Multiple Choice

What types of lists can a linear search be used on?

• Only sorted lists

• Only unsorted lists

• Both sorted and unsorted lists

• Neither sorted nor unsorted lists

Multiple Choice

If a list has n elements, what is the worst case for the number of searches in a linear search?

• n/2

• n-1

• n+1

• n

22

Multiple Choice

What is a procedure in programming?

• A set of instructions that performs a specific task and is not referred to by name.

• A set of code that is referred to by name and can be called at any point in a program.

• A variable that stores data values.

• A programming language.

What does the code do?

Answer: Double each value in the list.

23

What does the code do?

Answer: Add negative numbers from alist to the end of bList.

24

25

Big Idea 3: Programming and Algorithms

26

Big Idea 3: Programming and Algorithms

27

28

29

What is the result of executing the above code?

Answer: Robot moves forward 4 steps.

30

Does the code work as intended?
Yes, as an exercise, trace the code to convince yourself that the robot will
reach destination.

31

Does the code work as intended?
No! Robot get stuck in an infinite loop at the top right corner.

32

33

34

35

36

What is the output?
Answer: Empty list, a number cannot be both even and odd. No number is
appended to list2.

37

38

39

Multiple Choice

Using a linear search, how many comparisons would it take to find the number 11?

• 1 comparison

• 2 comparisons

• 10 comparisons

• 11 comparisons

Multiple Choice

What is the best case scenario for the number of comparisons in a linear search?

• The element is found after checking half of the list

• The element is found at the end of the list

• The element is not found in the list

• The element is found with the first comparison

40

41

42

43

44

Program Design

45

46

Trace the code and determine the output of the following program.

Answer:

47

Trace the code and determine the output of the following program.

Answer: Display 3.

48

Algorithms to Know

The AP MCQ will ask questions about standard algorithms every programmer
should know:

1)

Find total sum of a list of numbers

2)

Find average of a list of numbers

3)

Find maximum/minimum of a list of numbers

4)

Find word from a list of words

Please know these algorithms and know how to quickly recognize them! If the
code for any of the algorithm above is given with the name
"mystery_algorithm", you should be able to quickly recognize what it does.

We'll go over each of them.

49

Find total sum of a list

50

Find average of a list (implementation #1)

Implementation #1: Use for Each Loop.

51

Find average of a list (implementation #2)

Implementation #2: Use REPEAT n times loop.

52

Find maximum of a list (implementation #1)

Implementation #1: Use for Each Loop.

53

Find maximum of a list (implementation #2)
Implementation #2: Use REPEAT n times loop.

54

Common Error Example 1
The AP exam will try to give you code that is the wrong implementation
of an algorithm. Can you find the error?

55

Common Error Example 2
The AP exam will try to give you code that is the wrong implementation
of an algorithm. Can you find the error?

56

Correct findMinimum
Here's the correct implementation of findMinimum.

57

Find word from list of words

58

This code also works if we remove the Else block:

IF(item = word)
{

RETURN index

}
index 🡨 index + 1

Algorithmic Efficiency

Some problems cannot be solved in a reasonable amount of time
because there is no efficient algorithm for solving them. In these cases,
approximate solutions are sought.

Algorithms with a polynomial efficiency(constant, linear, square, cube,
etc.)
are said to run in a reasonable amount of time. They can be executed
quickly on a modern processor.

However, there exists important and practical problems for which there
exists no known polynomial time algorithm. Algorithms with
exponential or factorial efficiencies are examples of algorithms that run
in an unreasonable amount of time.

59

Algorithmic Efficiency

A heuristicis an approach to a problem that produces a solution that is
not guaranteed to be optimal but may be used when techniques that
are guaranteed to always find an optimal solution are impractical.

For example, a file-organizing algorithm determines the content of a
file based on a certain number of bytes in the beginning of the file. This
is an approximate solution since only a few bytes are examined. But it is
more practical and faster to run than examining every byte of every file.

60

Programmers break down problems into smaller and more manageable
pieces. By creating procedures and leveraging parameters, programmers
generalize processes that can be reused.

Procedures allow programmers to draw upon existing code that has
already been tested, allowing them to write programs more quickly and
with more confidence.

A software library contains procedures that may be used in creating new
programs. (e.g. Python's random, numpy libraries)

The use of libraries simplifies the task of creating complex programs
(abstraction).

61

Application program interfaces (APIs) are specifications for how the
procedures in a library behave and can be used.

For example, Twitter's API allow programmers to access and analyze tweets.

Documentation for an API/library is necessary in understanding the
behaviors provided by the API/library and how to use them. Twitter has
documentation that allows programmers to learn how to use their API.

A computing device is a physical artifact that can run a program. Some
examples include computers, tablets, servers, routers, and smart sensors.
The device must be able to take inputs, process the inputs, and then
calculate results based on those inputs.

62