OAE Computer Science key terms

A finite, ordered set of unambiguous steps that transforms input into output and terminates. It must be definite, effective, and produce a result for every valid input.

A structured, informal language used to describe an algorithm's logic without the syntax rules of a real programming language. It emphasizes control flow and readability over compilability.

A diagram that represents an algorithm using standardized symbols such as ovals for start and end, parallelograms for input and output, diamonds for decisions, and rectangles for processes.

A technique where a function calls itself on a smaller version of the problem. It requires a base case that stops the calls and a recursive case that moves toward that base case.

The condition in a recursive function that is solved directly without another recursive call, ending the recursion. Missing or unreachable base cases cause infinite recursion and stack overflow.

Repetition of a block of statements using a loop construct such as for, while, or do-while. Each pass through the loop body is one iteration.

A construct that determines the order in which statements execute, such as sequence, selection (if/else, switch), and repetition (loops). It shapes an algorithm's flow of control.

An expression that evaluates to either true or false, typically built from comparison operators and combined with AND, OR, and NOT. It controls selection and loop conditions.

A table listing every combination of input truth values for a logical expression and the resulting output. It is used to verify logical equivalence and simplify conditions.

Two rules for negating compound conditions: NOT (A AND B) equals (NOT A) OR (NOT B), and NOT (A OR B) equals (NOT A) AND (NOT B). They simplify and correct logical expressions.

The region of a program where a declared identifier is visible and usable. Local scope limits access to a block or function, while global scope makes it accessible throughout the program.

The mechanism by which arguments are supplied to a function. Pass-by-value copies the argument, while pass-by-reference lets the function modify the caller's original data.

A runtime structure that tracks active function calls, storing return addresses and local data in stack frames. It grows with each call and shrinks on return.

A program that translates an entire source file into machine code or an intermediate form before execution. It reports syntax errors and typically produces faster-running executables than interpretation.

A program that reads and executes source code statement by statement at runtime rather than translating the whole program in advance. It simplifies testing but often runs slower than compiled code.

A violation of a language's grammar rules, such as a missing semicolon or unmatched parenthesis, detected during compilation or parsing. The program cannot run until it is fixed.

An error that occurs while a program is executing, such as division by zero, an out-of-bounds index, or a null reference. Compilation succeeds but execution fails abnormally.

A flaw in a program's reasoning that produces incorrect results without crashing or violating syntax. It is found through testing and tracing rather than by the compiler.

A mechanism using try, catch, and finally blocks to detect and respond to runtime errors without terminating the program. It separates error recovery from normal control flow.

The systematic process of locating and correcting defects in a program, using techniques such as breakpoints, stepping, print statements, and code review.

Testing individual functions or modules in isolation against expected inputs and outputs. It catches defects early and supports safe refactoring of code.

A specific set of inputs, preconditions, and expected results used to verify program behavior. Good suites include normal, boundary, and invalid inputs.

A fixed-size, indexed collection of elements of the same type stored in contiguous memory. Access by index is constant time, but insertion and deletion may require shifting elements.

A linear structure of nodes, each holding data and a reference to the next node. Insertion and deletion at a known position are constant time, but access requires traversal.

A last-in, first-out structure where insertion (push) and removal (pop) occur at the same end, called the top. It supports function calls, undo operations, and expression evaluation.

A first-in, first-out structure where elements are added at the rear (enqueue) and removed from the front (dequeue). It models scheduling, buffering, and breadth-first traversal.

A binary tree where every left descendant is smaller and every right descendant is greater than the node's key. Search, insert, and delete average O(log n) when balanced.

A structure that maps keys to values using a hash function to compute bucket indices, giving average constant-time lookup. Collisions are resolved by chaining or open addressing.

Systematically visiting every vertex of a graph, typically by depth-first search using a stack or breadth-first search using a queue. Both run in O(V + E) time.

Visiting each node of a tree in a defined order: preorder, inorder, postorder, or level order. Inorder traversal of a binary search tree yields sorted keys.

A notation describing an upper bound on how an algorithm's time or space grows as input size increases, ignoring constants. Common classes include O(1), O(log n), O(n), O(n log n), and O(n^2).

A measure of how the number of basic operations performed by an algorithm scales with input size. It is usually expressed with asymptotic notation such as Big-O.

A measure of the total memory an algorithm requires as a function of input size, including auxiliary structures and recursion depth. It is often traded against time complexity.

A procedure that arranges elements in a specified order. Comparison sorts such as merge sort run in O(n log n) worst case, while quicksort averages O(n log n) but can degrade to O(n^2).

A search on a sorted array that repeatedly halves the interval by comparing the target with the middle element. It runs in O(log n) time and requires sorted input.

Changing a numeral's representation between bases such as binary, octal, decimal, and hexadecimal while preserving its value. Grouping four bits per hex digit and three per octal digit simplifies conversion.

A binary encoding for signed integers in which the most significant bit indicates sign and negation is performed by inverting bits and adding one. It represents one more negative value than positive.

A condition where a computed value exceeds the range representable by its data type's fixed number of bits, causing wraparound or an error. Signed overflow is a common source of logic defects.

A 7-bit character encoding assigning numeric codes 0-127 to letters, digits, punctuation, and control characters. Its superset Unicode extends encoding to most of the world's writing systems.

A physical or abstract device implementing a Boolean function, such as AND, OR, NOT, NAND, or XOR. Gates combine into circuits that perform arithmetic and control operations.

Software that manages hardware resources, schedules processes, allocates memory, and provides file systems and interfaces for applications. Examples include Windows, Linux, and macOS.

A program in execution with its own address space, program counter, and resources. Processes are isolated from one another, unlike threads, which share memory within a process.

A memory-management technique giving each process an abstract address space mapped to physical memory or disk. It enables isolation and allows programs larger than available RAM.

A numeric label assigned to a device on a network for routing data. IPv4 uses 32 bits in dotted-decimal form; IPv6 uses 128 bits in hexadecimal groups.

A bit pattern that identifies which portion of an IP address denotes the network and which denotes the host. It supports routing decisions and network segmentation.

The Domain Name System translates human-readable hostnames into IP addresses through a distributed hierarchy of name servers. It is a foundational lookup service for most internet traffic.

A network device that forwards packets between networks by consulting routing tables and destination IP addresses. It connects distinct subnets and often performs address translation.

The layered protocol suite underlying the internet. TCP provides reliable, ordered, connection-oriented delivery, while IP handles addressing and best-effort packet routing between hosts.

The transformation of readable data into ciphertext using a key so that only authorized parties can recover it. Symmetric methods share one key; asymmetric methods use public and private key pairs.

A cryptographic value created with a sender's private key that verifies authenticity and integrity of a message. Recipients validate it using the corresponding public key.

A one-way function that maps data of any size to a fixed-length digest. It is used for integrity checks, password storage, and hash tables; good ones resist collisions.