AP® Computer Science Principles Unit 3 flashcardsAlgorithms and Programming
40 cards · about 10 minutes for the whole deck
Flashcard drill
Space flips the card, arrow keys move, and keys 1 to 4 rate how well you knew it.
- Position
- 1 / 40
- Due
- 40
- Mastered
- 0 / 40
This card: New
Flip the card before you rate it.
Variable
A named place in a program that holds one value at a time. That value can be a number, a Boolean, a string or a whole list.
Topic 3.1: Variables and Assignments
Assignment (←)
a ← expressionworks out the expression and stores the result ina, replacing what was there. A variable holds the last value assigned to it.Topic 3.1: Variables and Assignments
Data type
The kind of value a variable holds, like a number, a Boolean, a string or a list. Some values fit one type better than another.
Topic 3.1: Variables and Assignments
List
An ordered collection of values, written like
[4, 7, 1]. On the exam, the first element is at index 1.Topic 3.2: Data Abstraction
Index
A whole number that gives an element's position. Exam lists run from index 1 to
LENGTH(aList); any other index stops the program with an error.Topic 3.2: Data Abstraction
Data abstraction
Giving a collection of data one name, like a list, so you can use it without worrying about the details. It makes programs easier to build and change.
Topic 3.2: Data Abstraction
String
Text stored as an ordered sequence of characters, like "hello" or "A7!".
Topic 3.4: Strings
Concatenation
Joining strings together, one after another, to make a new string: "sun" and "flower" make "sunflower".
Topic 3.4: Strings
Substring
A part of an existing string, like "flow" inside "sunflower".
Topic 3.4: Strings
Algorithm
A finite set of steps that does a specific job. Every algorithm can be built from sequencing, selection and iteration.
Topic 3.3: Mathematical Expressions
Expression
A value, variable, operator or procedure call (or a mix) that works out to a single value, like
x * 2 + 1.Topic 3.3: Mathematical Expressions
MOD
a MOD bis what's left over after dividing a by b, so17 MOD 5is 2. It ranks with*and/in the order of operations.Topic 3.3: Mathematical Expressions
Division on the exam
/is ordinary division, so17 / 5is 3.4, not 3. Use MOD when you want the remainder.Topic 3.3: Mathematical Expressions
Boolean value
A value that is either true or false. Comparisons like
x > 5produce one.Topic 3.5: Boolean Expressions
Relational operators
=,≠,>,<,≥and≤. They compare two values and give true or false.Topic 3.5: Boolean Expressions
Logical operators
NOTflips true and false.a AND bis true only if both are true.a OR bis true if at least one is true.Topic 3.5: Boolean Expressions
Selection
Choosing which steps run based on whether a condition is true. On the exam it's written with IF and ELSE.
Topic 3.6: Conditionals
IF / ELSE
IF (condition)runs its block only when the condition is true. With ELSE, exactly one of the two blocks runs.Topic 3.6: Conditionals
Nested conditional
An IF inside another IF. The inner check only happens when the outer condition sends the program that way.
Topic 3.7: Nested Conditionals
Iteration
Repeating part of an algorithm, either a set number of times or until a condition is met.
Topic 3.8: Iteration
REPEAT UNTIL (condition)
Checks the condition before each pass and stops once it's true. If it starts out true, the body never runs.
Topic 3.8: Iteration
Infinite loop
A loop that never stops, because its ending condition can never become true.
Topic 3.8: Iteration
Building on existing algorithms
Making a new algorithm from ones you know work, like finding a max, a sum or an average. It saves time and makes errors easier to find.
Topic 3.9: Developing Algorithms
List traversal
Visiting the elements of a list one at a time, all of them (complete) or only some (partial).
FOR EACH item IN aListvisits them first to last.Topic 3.10: Lists
List procedures
APPEND(aList, v)adds v to the end,INSERT(aList, i, v)puts v at index i,REMOVE(aList, i)deletes index i, andLENGTH(aList)counts the elements.Topic 3.10: Lists
Linear search
Checking each element in order until you find the value or run out of elements. It works on any list, sorted or not.
Topic 3.10: Lists
Binary search
Searching a sorted list by checking the middle and throwing away the half that can't hold the value. Much faster than linear search on big sorted lists.
Topic 3.11: Binary Search
Procedure
A named chunk of code that can take parameters and can return a value. Other languages call it a method or function.
Topic 3.12: Calling Procedures
Parameter vs. argument
A parameter is the input variable in a procedure's definition. An argument is the actual value you pass in when you call it.
Topic 3.12: Calling Procedures
RETURN
Sends a value back to where the procedure was called and ends the procedure right away.
Topic 3.12: Calling Procedures
Procedural abstraction
Using a procedure by knowing what it does, not how. You can change its insides without breaking the code that calls it.
Topic 3.13: Developing Procedures
Modularity
Splitting a program into separate procedures, each solving a smaller part of the problem. It makes code easier to test, fix and reuse.
Topic 3.13: Developing Procedures
Software library
A collection of procedures someone has already written that you can use in your own programs.
Topic 3.14: Libraries
API
Application program interface: the specification of how a library's procedures behave and how to call them. Its documentation is how you learn to use it.
Topic 3.14: Libraries
RANDOM(a, b)
Returns a random whole number from a to b, including both ends, each equally likely.
RANDOM(1, 6)can return 1, 2, 3, 4, 5 or 6.Topic 3.15: Random Values
Simulation
A program that models a real system with simplified details, often using random values. Good for things too slow, costly or dangerous to test for real.
Topic 3.16: Simulations
Reasonable vs. unreasonable time
Algorithms whose steps grow like a polynomial (n, n², n³) run in reasonable time. Exponential (2ⁿ) or factorial (n!) growth is unreasonable.
Topic 3.17: Algorithmic Efficiency
Heuristic
An approach that finds a good-enough answer when finding the best one would take far too long. It isn't guaranteed to be optimal.
Topic 3.17: Algorithmic Efficiency
Decision vs. optimization problem
A decision problem has a yes-or-no answer (Is there a path?). An optimization problem looks for the best answer (What's the shortest path?).
Topic 3.17: Algorithmic Efficiency
Undecidable problem
A yes-or-no problem that no algorithm can answer correctly for every input, though some instances may still be solvable.
Topic 3.18: Undecidable Problems