Skip to content
Marlbridge
Free trial

Flashcards · AP® Computer Science Principles · Unit 3

Unit 3: Algorithms and Programming (AAP) flashcards

109 cards on topics 3.1 to 3.18. Pick a topic or study the whole unit.

Study mode needs JavaScript. Every card is listed below, so you can still cover the answers and test yourself.

All 109 cards

For a quick read-through or printing. Cover the right-hand side to test yourself.

3.1 Variables and Assignments

What does the assignment a ← expression do?
It evaluates the expression, then stores a copy of the result in a, replacing the old value. A variable always holds the most recent value assigned.
What does DISPLAY(b) show after a ← 2, b ← a × 5, a ← b − a, b ← a + b?
18. a is 2, then b is 10, then a is 8, then b is 8 + 10 = 18, using the new value of a. Using the old a would wrongly give 12.
Does b ← a make b follow later changes to a?
No. It copies the value once. Later changes to a do not change b. Assigning a list stores a copy of the list as well.
How do you swap the values of two variables a and b?
Use a temporary variable: temp ← a, a ← b, b ← temp. With only two assignments both variables end up with the same value.
What is the difference between ← and = in the exam notation?
← assigns a value to the variable on the left. = tests whether two values are equal and gives true or false.
What is a good method for a what-is-displayed question?
Draw a table with a column for each variable, run one line at a time using current values, add a new row for each change, and read the output only after the last line has run.

3.2 Data Abstraction

What is a data abstraction?
A way to give a collection of data a name without showing how it is represented. A list is the standard example.
What are a list, an element and an index?
A list is an ordered sequence of elements. Each element has an index, and in the exam notation the first index is 1. A list can mix types, such as ["Aroha", 15, true].
What does an index outside the list do?
An index below 1 or above LENGTH(aList) gives an error and the program terminates.
What is the last valid index of a list?
LENGTH(aList). Using LENGTH(aList) + 1 is out of range.
How does a list manage complexity?
One name holds many values, code can adapt when the data grows, and the program is easier to develop and maintain. A specific answer names the list, what it holds, where it is used and what the program would need without it.
What is displayed? colours ← ["red", "green", "blue"], DISPLAY(LENGTH(colours)), DISPLAY(colours[2])
3 green. LENGTH gives 3 and colours[2] is the second element. colours[4] would end the program with an error.

3.3 Mathematical Expressions

What is the order of operations in the exam notation?
Brackets first, then × / MOD from left to right, then + − from left to right. MOD is at the same level as multiplication and division.
What does a MOD b give?
The remainder when a is divided by b, with a ≥ 0 and b > 0. 17 MOD 5 = 2, and 3 MOD 7 = 3 because 3 is smaller than 7.
What is 17 / 5 in the exam notation?
3.4. The / operator gives a real-number result and does not round down to 3.
How do you test whether n is even, or divisible by d?
Even: n MOD 2 = 0. Divisible by d: n MOD d = 0. For example 21 MOD 7 = 0 is true.
How do you find the last digit of a number?
n MOD 10. For 4826 the last digit is 4826 MOD 10 = 6.
What is y after x ← 14 and y ← x MOD 5 + x / 2 × 3?
25. 14 MOD 5 = 4, and 14 / 2 × 3 = 7 × 3 = 21 by working left to right, so y = 4 + 21 = 25.
How do you wrap a value around a 24-hour clock?
Add, then use MOD 24. For 21 hours plus 8 hours: (21 + 8) MOD 24 = 29 MOD 24 = 5.

3.4 Strings

What is a string, and what is the empty string?
A string is an ordered sequence of characters: letters, digits, spaces and punctuation. The empty string "" has length 0. "7" is a string, but 7 is a number.
What does concatenation do?
It joins strings end to end and makes a new string. Order matters: concat("sun", "shine") is "sunshine" but concat("shine", "sun") is not.
What is a substring?
A part of an existing string. In this course's pages substring(text, start, length) counts positions from 1, and the original string does not change.
What is substring("Mina", 1, 1)?
"M". It takes 1 character starting at position 1.
What is displayed? s ← "banana", part ← substring(s, 2, 3), DISPLAY(concat(part, "!"))
ana!. Positions 2, 3 and 4 of banana are a, n and a. Joining "!" gives "ana!".
How should you read a string question that uses its own definitions?
Follow the definition the question supplies for position counting and for the arguments. Write the string with each character numbered, evaluate inner concat calls first, and check the length of your answer.

3.5 Boolean Expressions

What are the relational and logical operators?
Relational: =, ≠, greater than, less than, ≥, ≤, which give true or false. Logical: NOT flips a value, p AND q needs both true, p OR q needs at least one true (inclusive).
How do you test that x is in a range with both ends included?
x ≥ lo AND x ≤ hi. Using OR would accept every value.
How do you test that x is outside a range?
x is less than lo OR x is greater than hi, which is the same as NOT(x ≥ lo AND x ≤ hi).
What are De Morgan's laws for NOT?
NOT(p AND q) equals (NOT p) OR (NOT q). NOT(p OR q) equals (NOT p) AND (NOT q). Negating swaps AND and OR.
What is NOT(a ≥ b) written without NOT?
a is less than b. The boundary flips: ≥ becomes less than.
What does DISPLAY(NOT(p OR q)) show when p is true and q is false?
false. p OR q is true, so NOT of it is false. Evaluate the comparisons first, then NOT, then AND, then OR, using brackets.

3.6 Conditionals

What does IF(condition) { ... } do?
It runs the block only if the condition is true. If the condition is false the block is skipped and flow continues with the next statement.
What does IF/ELSE guarantee?
Exactly one of the two blocks runs, never both and never neither.
What is the difference between IF/ELSE and two separate IFs?
IF/ELSE runs exactly one block. Two separate IFs are independent, so zero, one or both blocks can run.
Why give a variable a default value before an IF with no ELSE?
If the condition is false nothing is assigned, so the variable would keep an old or unset value. For example discount ← 0 before an IF that raises it.
What are the three building blocks of every algorithm?
Sequencing, selection and iteration. Selection decides which statements run based on a Boolean condition.
What is displayed? n ← 14, IF(n MOD 2 = 0) { DISPLAY("even") } ELSE { DISPLAY("odd") }
even. 14 MOD 2 is 0, so the condition is true and the first block runs. For n = 15 the remainder is 1 and the ELSE block runs.

3.7 Nested Conditionals

What is a nested conditional?
A conditional inside the block of another. The outer condition is evaluated first, and the inner one is evaluated only when control enters its block.
How do you match an ELSE with its IF?
Follow the braces: an ELSE belongs to the IF whose block closes just before it. Layout does not decide it, the braces do.
When is IF(a) { IF(b) { X } } with no ELSE blocks equivalent to something simpler?
IF(a AND b) { X }. With no ELSE blocks the two have the same effect. If the nesting has distinct ELSE results, it cannot be flattened this way.
Why does the order of range tests in a chain matter?
Each test sits inside the previous ELSE, so an earlier test catches values first. For grades, test the highest range first (≥ 80), then ≥ 60, and so on.
Which inputs fully test a three-outcome nested conditional?
One input for each outcome plus the boundaries. For a chain at 80 and 60, test 90, 70, 50 and the boundaries 80, 60 and 59.
What is a leap year condition in one expression?
(year MOD 4 = 0 AND year MOD 100 ≠ 0) OR year MOD 400 = 0. So 2024 and 2000 are leap years, but 2023 and 1900 are not.

3.8 Iteration

What does REPEAT n TIMES do?
It runs the block exactly n times.
What does REPEAT UNTIL(condition) do?
It checks the condition before each pass, runs the block while it is false, and stops when it becomes true. If the condition is true at the start, the block runs zero times.
What causes an infinite loop?
A stopping condition that can never become true, such as REPEAT UNTIL(n = 0) when n starts at 10 and decreases by 3, so it jumps past 0.
What are a counter and an accumulator?
A counter adds a fixed amount each pass (i ← i + 1). An accumulator builds a running total (total ← total + n). Both need a starting value.
What is displayed? n ← 1, count ← 0, REPEAT UNTIL(n ≥ 100) { n ← n × 2, count ← count + 1 }, DISPLAY(count), DISPLAY(n)
7 128. n goes 2, 4, 8, 16, 32, 64, 128. After the 7th pass n is at least 100, so the loop stops.
How do you trace a loop?
Draw columns for every variable and the condition, write the starting values, check the condition or count the pass, run the block line by line updating the row, and note how many times the block ran.

3.9 Developing Algorithms

What is an algorithm?
A finite set of instructions that accomplish a specific task. It can be written as natural language, a diagram, pseudocode or code, and is built from sequencing, selection and iteration.
In what three ways can a new algorithm be developed?
From an idea, by combining known algorithms, or by modifying a known one. Reusing correct algorithms reduces development and testing time.
How do you find the largest of three numbers a, b, c?
Start with big ← a. If b is greater than big, replace it. If c is greater than big, replace it. Test ties and the case where the first is largest.
How do you find the range of a list of numbers?
Combine two standard algorithms: find the largest, find the smallest, then subtract: largest − smallest.
How do you show that two algorithms are equivalent?
They must give the same result for every input. A few matching tests are not enough; explain why using the structure of the code, and look for a different result with ties and boundaries.
Why does IF(x > y) { big ← x } IF(y > x) { big ← y } fail when x equals y?
Neither condition is true, so big keeps its starting value, which is wrong. Use an ELSE, or ≥ in one of the tests.

3.10 Lists

What do INSERT, APPEND and REMOVE do?
INSERT(aList, i, value) shifts elements at i and above right and adds 1 to the length. APPEND adds at the end and adds 1. REMOVE(aList, i) shifts later elements left and subtracts 1.
What is the list after INSERT(aList, 2, 15) on [10, 20, 30]?
[10, 15, 20, 30]. The elements 20 and 30 shift right, so 20 is now at index 3.
What is FOR EACH item IN aList?
A traversal in which item is given the value of each element in turn, from first to last. item is a copy, so assigning to item does not change the list.
When do you need an index loop instead of FOR EACH?
When the position matters (the index of the largest value) or you want only part of the list. Use a counter from 1 to LENGTH(aList) and read aList[i].
How do you find the maximum of a list?
best ← aList[1], then FOR EACH item IN aList, replace best when item > best. Starting at 0 would fail for an all-negative list.
How does linear search work?
Check the elements in order until the target is found or all have been checked. It works on unsorted lists.
How do you swap two list elements?
temp ← aList[i], aList[i] ← aList[j], aList[j] ← temp. The temporary variable keeps the first value from being overwritten.

3.11 Binary Search

How does binary search work?
Start at the middle of a sorted list, compare with the target and eliminate half of the remaining data, then repeat until the target is found or no elements remain.
What must be true before binary search is used?
The list must be sorted. On unsorted data it can wrongly report that a present value is not found.
How do you find the greatest number of checks for n items?
Write the doubling sequence 1, 2, 4, 8 ... and find the first power of two greater than n. Its exponent is the answer. For 100 items 128 = 2 to the power 7, so 7 checks.
What happens to the number of binary-search checks when the list size doubles?
It rises by only one. A linear search would need twice as many checks.
When is linear search a better choice than binary search?
When the data are unsorted, or when the target is likely at the very front. Binary search is often more efficient on large sorted data, but not always.
What is the greatest number of checks for 1,000 and for 1,000,000 sorted items?
10 checks for 1,000 (2 to the power 10 is 1,024) and 20 checks for 1,000,000. Linear search could need all of them.

3.12 Calling Procedures

What is the difference between a parameter and an argument?
A parameter is an input variable in the procedure definition. An argument is the value given in the call, matched to parameters by position.
What does RETURN(expression) do?
It sends the value back to the caller and ends the procedure at once. Statements after it do not run, and control continues just after the call.
What is the difference between DISPLAY and RETURN?
DISPLAY shows a value during the call and returns nothing. RETURN sends a value back that the caller can store or use in an expression.
What is displayed? PROCEDURE f(n) { DISPLAY(n), RETURN(n + 1) }, DISPLAY(f(7))
7 8. The call f(7) runs first, displaying 7 and returning 8. Then the outer DISPLAY shows the returned 8.
How do you trace a procedure call?
Write the parameters with the argument values beside them, run the body line by line noting any DISPLAY output in order, stop at the first RETURN that runs, then replace the call by its value.
Does a procedure definition run by itself?
No. A definition does nothing until the procedure is called. Arguments are evaluated before the body runs, and a nested call is evaluated from the inside out.

3.13 Developing Procedures

What is procedural abstraction?
Giving a name to a process so that users need to know what it does, not how. The inside can change without notice if what it does stays the same.
How do procedures manage complexity?
By splitting a problem into subproblems, making the program modular, reusing shared code and making it more readable.
Why does a procedure have parameters?
Parameters generalise it so that it works with a range of arguments, such as a list or a score that changes from call to call.
What is the explanation pattern for how a procedure manages complexity?
Name the procedure and what it does, say how its parameter lets it work for many inputs, say where it is reused, and say what the program would be like without it.
What does bigger(bigger(4, 9), 6) return if bigger(a, b) returns the larger of a and b?
9. The inner call bigger(4, 9) returns 9, and bigger(9, 6) returns 9. Reusing bigger finds the largest of three without new comparison code.
When is a procedure's change safe for its callers?
When what it does is preserved for every possible argument. Callers rely only on the documented behavior, not on the code inside.

3.14 Libraries

What is a software library, and what is an API?
A library is a collection of procedures that can be used in new programs. An API is the specification of how those procedures behave and how to use them.
Why is documentation essential when using a library?
The library code is usually hidden, so the documentation (name, parameters, return value and conditions) is all you know. Use only what it says.
What is the difference between internal and external code?
Internal code is your own earlier code, such as a grade procedure from last project. External code is written by others, such as a graphics library.
How do libraries help a programmer?
They simplify complex programs and save development time and testing, because the procedures are already written and tested.
What do clamp(-8, 0, 100), clamp(250, 0, 100) and clamp(40, 0, 100) return if clamp keeps a value between low and high?
0, 100 and 40. The first value is below low so low is returned; the second is above high so high is returned; the third lies between them and is returned unchanged.
How should you use a library procedure safely?
Check that your arguments meet the documented conditions (guard with an IF if needed), store the returned value, and still test with typical, boundary and special inputs.

3.15 Random Values

What does RANDOM(a, b) return?
A random integer from a to b inclusive, each value equally likely. Each execution may give a different result.
How many values can RANDOM(a, b) return?
b − a + 1, because both end values are included. RANDOM(1, 6) has 6 possible values.
What are the possible results of RANDOM(1, 4) × 3?
3, 6, 9 and 12, each with probability 1/4. The result is never 4, 5 or 10.
How do you pick a random element of a list?
aList[RANDOM(1, LENGTH(aList))]. This reaches every element and never gives an index error, because the first index is 1.
How do you simulate an event with a 30% chance?
RANDOM(1, 10) ≤ 3. Three of the ten equally likely values make the condition true, so the probability is 3/10.
Is the sum of two RANDOM calls equally likely across its range?
No. A sum such as RANDOM(1, 6) + RANDOM(1, 6) is not uniform, because some totals can happen in more ways. Count the ways each result can occur.

3.16 Simulations

What is a simulation?
An abstraction of a complex object or phenomenon for a specific purpose. It removes specific details or simplifies functionality and uses varying sets of values to reflect changing state.
When is a simulation more useful than a real experiment?
When the real event is too big, small, fast, slow, expensive or dangerous to test. It lets you draw inferences without real-world constraints.
How do simulations model chance?
They use a random number generator, such as RANDOM(1, 10) ≤ 3 for a 30% event. One run is only one possible outcome, so run it many times.
How can bias get into a simulation?
Through the choices of what to include and leave out. A bridge model that ignores wind may say 40 lorries are safe when the real number is lower, an optimistic bias.
How should you evaluate a simulation in an answer?
State its purpose, list what is included and left out, say how each omission would push results higher or lower, and suggest checking it against real data.
Why are simulation results not facts about the real world?
They are predictions from the model. Simulations help form and refine hypotheses, but need comparing with reality.

3.17 Algorithmic Efficiency

What is the difference between a decision problem and an optimization problem?
A decision problem has a yes or no answer. An optimization problem seeks the best solution among many possible ones. A problem is a general task; an instance has specific input.
How is the efficiency of an algorithm measured informally?
By counting how many times statements execute, as a function of the input size n. Count executions, not lines of code.
What are reasonable and unreasonable running times?
Reasonable: polynomial or slower growth (constant, linear n, square n², cube n³). Unreasonable: exponential (2 to the power n) and factorial (n!).
What happens to the work when n doubles for one loop and for a loop inside a loop?
A single loop does twice the work. A loop inside a loop does four times the work: for n = 8 the inner statement runs 64 times, and for n = 16 it runs 256 times.
What is a heuristic?
A method that gives a solution that is not guaranteed to be optimal. It is used when exact methods would take unreasonable time.
Does a faster computer solve an unreasonable-time problem?
No. It changes the time for each step but not the growth pattern. At n = 20, 2 to the power n is 1,048,576 steps and n! is over two quintillion.

3.18 Undecidable Problems

What is a decidable problem?
A decision problem for which an algorithm can produce a correct yes or no output for every input, such as 'Is the number even?'.
What is an undecidable problem?
A decision problem for which no algorithm is always capable of a correct yes or no answer for every input.
What is the halting problem?
The standard undecidable problem: 'Does this program stop?'. No algorithm can decide it correctly for every program and input.
Can some instances of an undecidable problem be solved?
Yes. A program with only assignment statements and no loops always stops. But no single algorithm solves all instances.
What is the difference between undecidable and unreasonable time?
Unreasonable time: an algorithm exists but is too slow. Undecidable: no algorithm exists for all inputs. A faster computer cannot make an undecidable problem decidable.

Study Unit 3 further

AP® and Advanced Placement® are trademarks registered by the College Board, which is not affiliated with, and does not endorse, this website. Marlbridge is an independent tuition provider. It is not an authorized AP course provider, an AP school or an exam centre, and these resources are not official College Board materials. Reading them or doing simulations does not meet the laboratory requirement of an AP science course.