AP Computer Science Principles Flashcards: Developing Algorithms

What this deck covers

This deck focuses on Developing Algorithms, giving you a quick way to review the definitions, rules, and examples that matter most for AP Computer Science Principles.

How to use these flashcards

Work through these flashcards in short sessions. Try to answer each prompt before flipping the card, then revisit any cards you miss until the explanation feels automatic.

Flashcard 1: Find the result of the algorithm: Input: 3, Output: $x^2$.

Answer:

1. Substituting $x=3$ into $x^2$ gives $3^2 = 9$.

Flashcard 2: What is an invariant in the context of algorithms?

Answer: A condition that remains true throughout the execution. Property that helps prove algorithm correctness and termination.

Flashcard 3: Which data structure is used in a breadth-first search algorithm?

Answer: Queue. FIFO structure explores nodes level by level in graphs.

Flashcard 4: What does the acronym LIFO stand for in data structures?

Answer: Last In, First Out. Stack behavior where most recent item is removed first.

Flashcard 5: What is recursion in the context of algorithms?

Answer: A process where a function calls itself. Breaks complex problems into smaller, similar subproblems.

Flashcard 6: Find the output of the algorithm: Input: 4, Output: $x^3$.

Answer:

1. Substituting $x=4$ into $x^3$ gives $4^3 = 64$.

Flashcard 7: What is the purpose of using flowcharts in algorithm design?

Answer: To visually represent the sequence of steps in an algorithm. Shows decision points, loops, and flow direction graphically.

Flashcard 8: What is dynamic programming in algorithms?

Answer: A method for solving complex problems by breaking them down. Stores solutions to subproblems to avoid redundant calculations.

Flashcard 9: Identify the algorithm that uses a queue to explore nodes in a graph.

Answer: Breadth-first search. Queue ensures level-by-level exploration of graph nodes.

Flashcard 10: Which search algorithm operates efficiently on sorted arrays?

Answer: Binary search. Halves search space each iteration, requiring sorted input.

Flashcard 11: What is the purpose of using flowcharts in algorithm design?

Answer: To visually represent the sequence of steps in an algorithm. Shows decision points, loops, and flow direction graphically.

Flashcard 12: What does 'pseudocode' refer to in algorithm development?

Answer: A high-level description of an algorithm using plain language. Uses structured English to outline algorithm logic before coding.

Flashcard 13: Identify the main components of a typical algorithm.

Answer: Input, process, output. The basic flow: receive data, manipulate it, produce results.

Flashcard 14: Which search algorithm operates efficiently on sorted arrays?

Answer: Binary search. Halves search space each iteration, requiring sorted input.

Flashcard 15: What is the purpose of a loop in an algorithm?

Answer: To repeat a block of code multiple times. Enables efficient processing of collections and repetitive tasks.

Flashcard 16: What is the main advantage of using recursion in algorithms?

Answer: Simplifies the code for problems that have a recursive structure. Natural fit for tree traversals and mathematical expressions.

Flashcard 17: What does 'pseudocode' refer to in algorithm development?

Answer: A high-level description of an algorithm using plain language. Uses structured English to outline algorithm logic before coding.

Flashcard 18: What is the primary use of a hash table in algorithms?

Answer: Efficiently store and retrieve data. Provides constant-time average access using hash functions.

Flashcard 19: Identify the algorithm that builds a sorted array one item at a time.

Answer: Insertion sort. Inserts each new element into its correct sorted position.

Flashcard 20: What is the primary use of a hash table in algorithms?

Answer: Efficiently store and retrieve data. Provides constant-time average access using hash functions.

Flashcard 21: Which data structure is used in depth-first search algorithms?

Answer: Stack. LIFO structure enables deep exploration before backtracking.

Flashcard 22: What is the space complexity of an algorithm?

Answer: The amount of memory used by the algorithm. Measures additional memory required beyond input storage.

Flashcard 23: What is the definition of an algorithm?

Answer: A step-by-step procedure for solving a problem. Algorithms are systematic solutions with clear steps to solve problems.

Flashcard 24: Identify the sorting algorithm with the best average-case performance.

Answer: Heapsort, Mergesort, or Quicksort. All three achieve $O(n \log n)$ average performance consistently.

Flashcard 25: Identify the algorithm that sorts by repeatedly dividing the array.

Answer: Merge sort. Divide-and-conquer approach splits arrays until single elements.

Flashcard 26: Which algorithmic concept involves repeating a process?

Answer: Iteration. Loops and repetition structures implement iterative processes.

Flashcard 27: What is the purpose of a sentinel value in algorithms?

Answer: To denote the end of a data structure. Special marker value indicating boundary or termination condition.

Flashcard 28: Which data structure is used in depth-first search algorithms?

Answer: Stack. LIFO structure enables deep exploration before backtracking.

Flashcard 29: Which structure helps in making decisions in an algorithm?

Answer: Conditional statements (e.g., if-else). Allows algorithms to branch based on true/false conditions.

Flashcard 30: What is a heuristic in algorithm design?

Answer: A technique to find solutions faster when classic methods fail. Approximation method when optimal solutions are computationally expensive.

Flashcard 31: What is the time complexity of the quicksort algorithm in the average case?

Answer: $O(n \, \log n)$. Divides array and partitions around pivot efficiently on average.

Flashcard 32: What is the big-O notation for the worst-case scenario of bubble sort?

Answer: $O(n^2)$. Requires $n(n-1)/2$ comparisons when array is reverse sorted.

Flashcard 33: What is the big-O notation for the worst-case scenario of bubble sort?

Answer: $O(n^2)$. Requires $n(n-1)/2$ comparisons when array is reverse sorted.

Flashcard 34: What is the base case in a recursive algorithm?

Answer: A condition that stops the recursion. Prevents infinite recursion by providing an exit condition.

Flashcard 35: What is the role of a break statement in a loop?

Answer: To terminate the loop prematurely. Exits loop immediately when specific condition is met.

Flashcard 36: Identify the algorithm that sorts by repeatedly dividing the array.

Answer: Merge sort. Divide-and-conquer approach splits arrays until single elements.

Flashcard 37: Identify the algorithm used for finding the minimum spanning tree.

Answer: Prim's or Kruskal's algorithm. Finds minimum cost to connect all vertices in graph.

Flashcard 38: Which sorting algorithm is not based on comparisons?

Answer: Counting sort. Counts frequency of elements rather than comparing values.

Flashcard 39: Identify the sorting algorithm with the best average-case performance.

Answer: Heapsort, Mergesort, or Quicksort. All three achieve $O(n \log n)$ average performance consistently.

Flashcard 40: What is the primary characteristic of a greedy algorithm?

Answer: It makes the locally optimal choice at each step. Chooses the best immediate option without considering future consequences.

Flashcard 41: Which sorting algorithm is not based on comparisons?

Answer: Counting sort. Counts frequency of elements rather than comparing values.

Flashcard 42: Find the big-O notation for the worst-case of linear search.

Answer: $O(n)$. Must check every element when target is last or absent.

Flashcard 43: What is the primary characteristic of a greedy algorithm?

Answer: It makes the locally optimal choice at each step. Chooses the best immediate option without considering future consequences.

Flashcard 44: What is the big-O notation for the best-case scenario of binary search?

Answer: $O(1)$. Best case occurs when target is the middle element immediately.

Flashcard 45: Which algorithmic concept involves repeating a process?

Answer: Iteration. Loops and repetition structures implement iterative processes.

Flashcard 46: What is the main advantage of using recursion in algorithms?

Answer: Simplifies the code for problems that have a recursive structure. Natural fit for tree traversals and mathematical expressions.

Flashcard 47: Which data structure follows the LIFO principle?

Answer: Stack. Used for function calls, undo operations, and backtracking.

Flashcard 48: What is the purpose of a loop in an algorithm?

Answer: To repeat a block of code multiple times. Enables efficient processing of collections and repetitive tasks.

Flashcard 49: Which algorithm strategy uses a divide-and-conquer approach?

Answer: Merge sort. Recursively splits problems into smaller, manageable subproblems.

Flashcard 50: Find the output of the algorithm: Input: 4, Output: $x^3$.

Answer:

1. Substituting $x=4$ into $x^3$ gives $4^3 = 64$.

Flashcard 51: What is the time complexity of the insertion sort in the best case?

Answer: $O(n)$. Already sorted arrays require minimal comparisons and shifts.

Flashcard 52: What is an invariant in the context of algorithms?

Answer: A condition that remains true throughout the execution. Property that helps prove algorithm correctness and termination.

Flashcard 53: What is the purpose of a sentinel value in algorithms?

Answer: To denote the end of a data structure. Special marker value indicating boundary or termination condition.

Flashcard 54: Find the result of the algorithm: Input: 3, Output: $x^2$.

Answer:

1. Substituting $x=3$ into $x^2$ gives $3^2 = 9$.

Flashcard 55: Which type of loop guarantees execution at least once?

Answer: Do-while loop. Condition checked after execution, ensuring one iteration minimum.

Flashcard 56: What is dynamic programming in algorithms?

Answer: A method for solving complex problems by breaking them down. Stores solutions to subproblems to avoid redundant calculations.

Flashcard 57: What is recursion in the context of algorithms?

Answer: A process where a function calls itself. Breaks complex problems into smaller, similar subproblems.

Flashcard 58: What is the time complexity of the insertion sort in the best case?

Answer: $O(n)$. Already sorted arrays require minimal comparisons and shifts.

Flashcard 59: Identify the algorithm that uses a queue to explore nodes in a graph.

Answer: Breadth-first search. Queue ensures level-by-level exploration of graph nodes.

Flashcard 60: Which data structure follows the LIFO principle?

Answer: Stack. Used for function calls, undo operations, and backtracking.

Flashcard 61: Which type of loop guarantees execution at least once?

Answer: Do-while loop. Condition checked after execution, ensuring one iteration minimum.

Flashcard 62: What is the time complexity of the quicksort algorithm in the average case?

Answer: $O(n \, \log n)$. Divides array and partitions around pivot efficiently on average.

Flashcard 63: What is the definition of an algorithm?

Answer: A step-by-step procedure for solving a problem. Algorithms are systematic solutions with clear steps to solve problems.

Flashcard 64: Which data structure is used in a breadth-first search algorithm?

Answer: Queue. FIFO structure explores nodes level by level in graphs.

Flashcard 65: Identify the algorithm used for finding the minimum spanning tree.

Answer: Prim's or Kruskal's algorithm. Finds minimum cost to connect all vertices in graph.

Flashcard 66: Identify the main components of a typical algorithm.

Answer: Input, process, output. The basic flow: receive data, manipulate it, produce results.

Flashcard 67: Identify the algorithm that sorts by repeatedly finding the minimum.

Answer: Selection sort. Finds smallest element and swaps to correct position repeatedly.

Flashcard 68: Find the big-O notation for the worst-case of linear search.

Answer: $O(n)$. Must check every element when target is last or absent.

Flashcard 69: Which algorithm strategy uses a divide-and-conquer approach?

Answer: Merge sort. Recursively splits problems into smaller, manageable subproblems.

Flashcard 70: What is the base case in a recursive algorithm?

Answer: A condition that stops the recursion. Prevents infinite recursion by providing an exit condition.

Flashcard 71: Which structure helps in making decisions in an algorithm?

Answer: Conditional statements (e.g., if-else). Allows algorithms to branch based on true/false conditions.

Flashcard 72: Identify the algorithm that finds the shortest path in a weighted graph.

Answer: Dijkstra's algorithm. Uses priority queue to find minimum distances from source.

Flashcard 73: Identify the algorithm that sorts by repeatedly finding the minimum.

Answer: Selection sort. Finds smallest element and swaps to correct position repeatedly.

Flashcard 74: Identify the algorithm that builds a sorted array one item at a time.

Answer: Insertion sort. Inserts each new element into its correct sorted position.

Flashcard 75: What is the role of a break statement in a loop?

Answer: To terminate the loop prematurely. Exits loop immediately when specific condition is met.

Flashcard 76: Identify the algorithm that finds the shortest path in a weighted graph.

Answer: Dijkstra's algorithm. Uses priority queue to find minimum distances from source.

Flashcard 77: What is the big-O notation for the best-case scenario of binary search?

Answer: $O(1)$. Best case occurs when target is the middle element immediately.

Flashcard 78: What is a heuristic in algorithm design?

Answer: A technique to find solutions faster when classic methods fail. Approximation method when optimal solutions are computationally expensive.

Flashcard 79: What does the acronym LIFO stand for in data structures?

Answer: Last In, First Out. Stack behavior where most recent item is removed first.