Developing Algorithms - AP Computer Science Principles

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Stack. LIFO structure enables deep exploration before backtracking.

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

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

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

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

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

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

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

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