Big Idea 3-Algorithms and Programming Flashcards
A _______is an abstraction inside a program that can hold a value. Each _______ has associated data storage that represents one value at a time, but that value can be a list or other collection that in turn contains multiple values.
variable
Using _________ variable names helps with the readability of program code and understanding of what values are represented by the variables.
meaningful
Some programming languages provide types to represent data, which are referenced using variables. These types include ___________________.
numbers, Booleans, lists, and strings
A _______ is an ordered sequence of elements. For example, [value1, value2, value3, …] describes a ________ where value1 is the first element, value2 is the second element, value3 is the third element, and so on.
Warning! AP Exam starts index at 1.
list
An ________ is an individual value in a list that is assigned a unique index.
element
An _______ is a common method for referencing the elements in a list or string using natural numbers.
index
A _______ is an ordered sequence of characters.
string
________ provides a separation between the abstract properties of a data type and the concrete details of its representation.
Data abstraction
Data abstractions manage _______ in programs by giving a collection of data a name without referencing the specific details of the representation.
complexity
Data abstractions can be created using _______.
lists
Developing a data abstraction to implement in a program can result in a program that is easier to __________.
develop and maintain
The use of ______ allows multiple related items to be treated as a single value.
lists
An _______ is a finite set of instructions that accomplish a specific task.
algorithm
Algorithms executed by programs are implemented using __________.
programming languages
Every algorithm can be constructed using combinations of ________, _________, and _______.
sequencing, selection, and iteration.
_________ is the application of each step of an algorithm in the order in which the code statements are given.
Sequencing
A __________ is a part of program code that expresses an action to be carried out.
code statement
An _________ can consist of a value, a variable, an operator, or a procedure call that returns a value.
expression
Expressions are evaluated to produce a ________.
single value
True or False: Sequential statements execute in the order they appear in the code segment.
True
Comment: Clarity and readability are important considerations when expressing an algorithm in a programming language.
Arithmetic operators are part of most programming languages and include _______, _______, _______, _______, and _______ operators.
addition, subtraction, multiplication, division, and modulus
Comment: The exam reference sheet provides a MOD b, which evaluates to the remainder when a is divided by b.
Assume that a is an integer greater than or equal to 0 and b is an integer greater than 0. For example, 17 MOD 5 evaluates to ___.
2
__________ joins together two or more strings end-to-end to make a new string.
String concatenation
A _________ is part of an existing string.
substring
A ______ is either true or false.
Boolean value
_______ determines which parts of an algorithm are executed based on a condition being true or false.
Selection
_______________ affect the sequential flow of control by executing different statements based on the value of a Boolean expression.
Conditional statements, or “if-statements,”
_______ conditional statements consist of conditional statements within conditional statements.
Nested
_________ is a repeating portion of an algorithm. Iteration repeats a specified number of times or until a given condition is met.
Iteration
Comment: Iteration statements change the sequential flow of control by repeating a set of statements zero or more times, until a stopping condition is met.
True or False: Algorithms can be written in different ways and still accomplish the same tasks.
True
True or False: Algorithms can be written in different ways and still accomplish the same tasks.
True: Also, different algorithms can be developed or used to solve the same problem.
True or False: Algorithms that appear similar should yield the same result or effect?
False: Algorithms that appear similar can yield different side effects or results.
Comment: Algorithms can be created from an idea, by combining existing algorithms, or by modifying existing algorithms.
Comment: Knowledge of existing algorithms can help in constructing new ones. Some existing algorithms include:
determining the maximum or minimum value of two or more numbers
computing the sum or average of two or more numbers
identifying if an integer is or is not evenly divisible by another integer
determining a robot’s path through a maze
Comment: Using existing correct algorithms as building blocks for constructing another algorithm has benefits such as reducing development time, reducing testing, and simplifying the identification of errors.
Comment: Traversing a list can be a complete traversal, where all elements in the list are accessed, or a partial traversal, where only a portion of elements are accessed.
Iteration statements can be used to ______ a list.
traverse
Comment: Knowledge of existing algorithms that use iteration can help in constructing new algorithms. Some examples of existing algorithms that are often used with lists include:
determining a minimum or maximum value in a list
computing a sum or average of a list of numbers
Linear search or sequential search algorithms check each element of a list, in ______, until the desired value is found or all elements in the list have been checked.
order
The _________ search algorithm starts in the middle of a sorted data set of numbers and eliminates half of the data; this process repeats until the desired value is found or all elements have been eliminated.
binary
Data must be in _______ order to use the binary search algorithm.
sorted
Binary search is often more _______ than sequential/linear search when applied to sorted data.
efficient
A _________ is a named group of programming instructions that may have parameters and return values.
procedure
Comment: Procedures are referred to by different names, such as method or function, depending on the programming language.
________ are input variables of a procedure.
Parameters
__________ specify the values of the parameters when a procedure is called.
Arguments
Comment: A procedure call interrupts the sequential execution of statements, causing the program to execute the statements within the procedure before continuing. Once the last statement in the procedure (or a return statement) has been executed, flow of control is returned to the point immediately following where the procedure was called
One common type of abstraction is ___________, which provides a name for a process and allows a procedure to be used only knowing what it does, not how it does it.
procedural abstraction
Comment: Procedural abstraction allows a solution to a large problem to be based on the solutions of smaller subproblems. This is accomplished by creating procedures to solve each of the subproblems.
The subdivision of a computer program into separate subprograms is called _________.
modularity
A procedural abstraction may extract shared features to generalize functionality instead of duplicating code. This allows for program code reuse, which helps manage __________.
complexity
Using _________ allows procedures to be generalized, enabling the procedures to be reused with a range of input values or arguments.
parameters
A _________ contains procedures that may be used in creating new programs.
software library
Comment: The use of libraries simplifies the task of creating complex programs.
Existing code segments can come from internal or external sources, such as _____________.
libraries or previously written code
Using ____________ in a program means each execution may produce a different result.
random number generation
___________ are abstractions of more complex objects or phenomena for a specific purpose.
Simulations
A _________ is a representation that uses varying sets of values to reflect the changing state of a phenomenon.
simulation
Comment: Simulations often mimic real-world events with the purpose of drawing inferences, allowing investigation of a phenomenon without the constraints of the real world.
The process of developing an abstract simulation involves removing specific details or simplifying functionality.
Simulations can contain ________ derived from the choices of real-world elements that were included or excluded.
bias
Comment: Simulations are most useful when real-world events are impractical for experiments (e.g., too big, too small, too fast, too slow, too expensive, or too dangerous).
____________ can be used to simulate the variability that exists in the real world.
Random number generators
A __________ is a general description of a task that can (or cannot) be solved algorithmically.
problem
An ____________ also includes specific input. For example, sorting is a problem; sorting the list (2,3,1,7) is an ________________.
instance of a problem
A _____________ is a problem with a yes/no answer (e.g., is there a path from A to B?).
decision problem
An __________ is a problem with the goal of finding the “best” solution among many (e.g., what is the shortest path from A to B?).
optimization problem
_________ is an estimation of the amount of computational resources used by an algorithm. _________ is typically expressed as a function of the size of the input.
Efficiency
Comment: An algorithm’s efficiency is determined through formal or mathematical reasoning.
An algorithm’s efficiency can be informally measured by determining the number of times a statement or group of statements executes.
True or False: Different correct algorithms for the same problem can have different efficiencies.
True
Algorithms with a ________ efficiency or slower (constant, linear, square, cube, etc.) are said to run in a reasonable amount of time. Algorithms with ________ or factorial efficiencies are examples of algorithms that run in an unreasonable amount of time.
polynomial, exponential
Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for solving them. In these cases, ________ solutions are sought.
approximate
A __________ is 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.
heuristic
A __________ is a decision problem for which an algorithm can be written to produce a correct output for all inputs (e.g., “Is the number even?”).
decidable problem
An ___________ is one for which no algorithm can be constructed that is always capable of providing a correct yes-or-no answer.
undecidable problem
Comment: An undecidable problem may have some instances that have an algorithmic solution, but there is no algorithmic solution that could solve all instances of the problem.
