Developing Algorithms - AP Computer Science Principles

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

9. Substituting $x=3$ into $x^2$ gives $3^2 = 9$ .
Which data structure is used in a breadth-first search algorithm?

Queue. FIFO structure explores nodes level by level in graphs.
What does the acronym LIFO stand for in data structures?

Last In, First Out. Stack behavior where most recent item is removed first.
Find the output of the algorithm: Input: 4, Output: $x^3$ .

64. Substituting $x=4$ into $x^3$ gives $4^3 = 64$ .
What is the purpose of using flowcharts in algorithm design?

To visually represent the sequence of steps in an algorithm. Shows decision points, loops, and flow direction graphically.
Which search algorithm operates efficiently on sorted arrays?

Binary search. Halves search space each iteration, requiring sorted input.
What does 'pseudocode' refer to in algorithm development?

A high-level description of an algorithm using plain language. Uses structured English to outline algorithm logic before coding.
Identify the main components of a typical algorithm.

Input, process, output. The basic flow: receive data, manipulate it, produce results.
What is the primary use of a hash table in algorithms?

Efficiently store and retrieve data. Provides constant-time average access using hash functions.
Which data structure is used in depth-first search algorithms?

Stack. LIFO structure enables deep exploration before backtracking.
What is the space complexity of an algorithm?

The amount of memory used by the algorithm. Measures additional memory required beyond input storage.
Identify the sorting algorithm with the best average-case performance.

Heapsort, Mergesort, or Quicksort. All three achieve $O(n \log n)$ average performance consistently.
Identify the algorithm that sorts by repeatedly dividing the array.

Merge sort. Divide-and-conquer approach splits arrays until single elements.
Which structure helps in making decisions in an algorithm?

Conditional statements (e.g., if-else). Allows algorithms to branch based on true/false conditions.
What is a heuristic in algorithm design?

A technique to find solutions faster when classic methods fail. Approximation method when optimal solutions are computationally expensive.
What is the big-O notation for the worst-case scenario of bubble sort?

$O(n^2)$ . Requires $n(n-1)/2$ comparisons when array is reverse sorted.
What is the base case in a recursive algorithm?

A condition that stops the recursion. Prevents infinite recursion by providing an exit condition.
Identify the algorithm used for finding the minimum spanning tree.

Prim's or Kruskal's algorithm. Finds minimum cost to connect all vertices in graph.
Which sorting algorithm is not based on comparisons?

Counting sort. Counts frequency of elements rather than comparing values.
Find the big-O notation for the worst-case of linear search.

$O(n)$ . Must check every element when target is last or absent.
What is the primary characteristic of a greedy algorithm?

It makes the locally optimal choice at each step. Chooses the best immediate option without considering future consequences.
Which algorithmic concept involves repeating a process?

Iteration. Loops and repetition structures implement iterative processes.
What is the main advantage of using recursion in algorithms?

Simplifies the code for problems that have a recursive structure. Natural fit for tree traversals and mathematical expressions.
What is the purpose of a loop in an algorithm?

To repeat a block of code multiple times. Enables efficient processing of collections and repetitive tasks.
Which algorithm strategy uses a divide-and-conquer approach?

Merge sort. Recursively splits problems into smaller, manageable subproblems.
What is an invariant in the context of algorithms?

A condition that remains true throughout the execution. Property that helps prove algorithm correctness and termination.
What is the purpose of a sentinel value in algorithms?

To denote the end of a data structure. Special marker value indicating boundary or termination condition.
Which type of loop guarantees execution at least once?

Do-while loop. Condition checked after execution, ensuring one iteration minimum.
What is dynamic programming in algorithms?

A method for solving complex problems by breaking them down. Stores solutions to subproblems to avoid redundant calculations.
What is recursion in the context of algorithms?

A process where a function calls itself. Breaks complex problems into smaller, similar subproblems.
What is the time complexity of the insertion sort in the best case?

$O(n)$ . Already sorted arrays require minimal comparisons and shifts.
Identify the algorithm that uses a queue to explore nodes in a graph.

Breadth-first search. Queue ensures level-by-level exploration of graph nodes.
Which data structure follows the LIFO principle?

Stack. Used for function calls, undo operations, and backtracking.
What is the time complexity of the quicksort algorithm in the average case?

$O(n \, \log n)$ . Divides array and partitions around pivot efficiently on average.
What is the definition of an algorithm?

A step-by-step procedure for solving a problem. Algorithms are systematic solutions with clear steps to solve problems.
Identify the algorithm that finds the shortest path in a weighted graph.

Dijkstra's algorithm. Uses priority queue to find minimum distances from source.
Identify the algorithm that sorts by repeatedly finding the minimum.

Selection sort. Finds smallest element and swaps to correct position repeatedly.
Identify the algorithm that builds a sorted array one item at a time.

Insertion sort. Inserts each new element into its correct sorted position.
What is the role of a break statement in a loop?

To terminate the loop prematurely. Exits loop immediately when specific condition is met.
What is the big-O notation for the best-case scenario of binary search?

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

Study these flashcards