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: 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 2: Identify the main components of a typical algorithm.

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

Flashcard 3: 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 4: 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 5: 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 6: 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 7: 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 8: 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 9: Find the output of the algorithm: Input: 4, Output: $x^3$.

Answer:

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

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 role of a break statement in a loop?

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

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

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

Flashcard 13: 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 14: 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 15: 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 16: 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 17: Which data structure follows the LIFO principle?

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

Flashcard 18: 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 19: Identify the algorithm that sorts by repeatedly finding the minimum.

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

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: 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 22: Which data structure is used in depth-first search algorithms?

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

Flashcard 23: 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 24: 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 25: Which sorting algorithm is not based on comparisons?

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

Flashcard 26: 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 27: Which algorithm strategy uses a divide-and-conquer approach?

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

Flashcard 28: 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 29: 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 30: Find the result of the algorithm: Input: 3, Output: $x^2$.

Answer:

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