Computer Science Level 3 flashcards

32 cards. Read the term and the definition here. The deck at the top of this page is optional.

Big-O notation

A notation describing an upper bound on how an algorithm's running time or space grows as input size increases, ignoring constants and lower-order terms.

Binary search precondition

The input array must be sorted, and elements must support direct index access. Each comparison halves the remaining interval, giving logarithmic time.

Undecidable problem

A decision problem for which no algorithm can always halt with a correct yes or no answer for every input, such as the halting problem.

Recursion base case

The condition that stops recursive calls and returns a value directly. Without it, recursion continues until the call stack overflows.

Greedy algorithm

An approach that repeatedly makes the locally best choice, correct only when the problem has the greedy-choice property and optimal substructure.

Pass by reference

A calling convention where the callee receives the address of the caller's variable, so modifications inside the function are visible to the caller.

Compiler versus interpreter

A compiler translates the whole source program to machine code before running it; an interpreter executes statements one at a time during runtime.

Unit test

An automated test that exercises a single function or class in isolation, checking that a specific input produces the expected output or error.

Exception propagation

When a raised exception is not handled locally, it travels up the call stack until a matching handler catches it or the program terminates.

Refactoring

Restructuring existing code to improve readability or design without changing its external behavior, so the test suite should still pass.

Array access complexity

Reading or writing an element by index takes constant time, but inserting or removing in the middle takes linear time because later elements shift.

Stack versus queue

A stack removes the most recently added item (last in, first out); a queue removes the oldest item (first in, first out).

Hash table load factor

The ratio of stored entries to buckets. A high load factor increases collisions and slows lookup, so implementations resize and rehash.

Balanced binary search tree

A search tree that automatically keeps its height logarithmic through rotations, guaranteeing logarithmic search, insertion, and deletion.

Breadth-first search

A graph traversal using a queue that visits all neighbors at the current distance before going deeper, finding shortest paths in unweighted graphs.

Foreign key

A column whose values must match a primary key in another table, enforcing referential integrity between related records.

Fetch-decode-execute cycle

The CPU repeatedly reads the instruction at the program counter, decodes its operation, executes it, and advances to the next instruction.

Memory hierarchy

The ordering of storage by speed and size, from registers and cache through RAM to disk, where each level is larger and slower.

Two's complement

A binary encoding of signed integers where the most significant bit carries negative weight, letting addition and subtraction share one circuit.

TCP versus UDP

TCP is connection-oriented and reliable, retransmitting lost segments; UDP is connectionless and unreliable, favored when low latency matters more.

DNS

The Domain Name System translates human-readable host names into IP addresses through a distributed hierarchy of resolvers and authoritative servers.

Symmetric versus asymmetric encryption

Symmetric encryption uses one shared secret key for both directions; asymmetric encryption uses a public key to encrypt and a private key to decrypt.

Median versus mean

The mean is the arithmetic average and shifts with extreme values; the median is the middle sorted value and resists outliers.

Standard deviation

A measure of how far values typically lie from the mean, equal to the square root of the variance and expressed in the data's units.

Correlation coefficient

A number between negative one and one measuring the strength and direction of a linear relationship between two variables, not causation.

p-value

The probability of observing data at least as extreme as the sample, assuming the null hypothesis is true; it is not the chance the null is true.

Overfitting

A model that fits noise in the training data and therefore performs poorly on new data; detected by comparing training and validation error.

Algorithmic bias

Systematically unfair outputs produced when training data, feature choices, or design decisions encode historical or social inequities.

Informed consent

The practice of telling users what data is collected, why, and with whom it is shared before collection, so agreement is voluntary and informed.

Digital divide

The gap between groups with reliable access to devices, connectivity, and digital skills and those without, which widens existing inequalities.

Copyleft license

An open-source license such as the GPL that requires derivative works distributed publicly to remain under the same open licensing terms.

WCAG

Web Content Accessibility Guidelines: standards requiring interfaces to be perceivable, operable, understandable, and robust for users with disabilities.