ILTS Computer Science (205) key terms

A finite, ordered set of unambiguous steps that transforms an input into an output and terminates. Candidates should distinguish it from a program, which is one concrete implementation in a specific language.

A notation describing an upper bound on how an algorithm's resource use grows as input size increases, ignoring constants and lower-order terms. It characterizes growth rate, not measured runtime on a particular machine.

A technique where a function solves a problem by calling itself on smaller inputs, requiring a base case to stop and a recursive case to progress. Each pending call consumes stack space until it returns.

The condition in a recursive function that is answered directly without another recursive call, ending the chain of calls. A missing or unreachable base case produces infinite recursion and stack overflow.

A search that repeatedly halves a sorted array by comparing the target with the middle element, running in logarithmic time. It requires random access and correctly maintained low and high bounds.

A procedure that rearranges elements into a defined order. Candidates should compare selection, insertion, merge, and quicksort by typical time complexity, stability, and whether they sort in place.

A structured, language-neutral description of an algorithm using indentation and keywords rather than strict syntax. It lets candidates reason about logic and complexity without worrying about compiler rules.

A manual debugging and teaching tool that records variable values after each step of an algorithm. Filling one in reveals off-by-one errors, incorrect loop bounds, and faulty conditional logic.

The algebra of true and false values using AND, OR, and NOT, evaluated by truth tables. It underlies conditional statements, circuit design, and search expressions, and follows precedence and distributive laws.

A table listing every combination of input truth values for a logical expression alongside the resulting output. It is used to verify equivalence, define gates, and test conditional expressions exhaustively.

Hiding implementation detail behind a simpler interface so users reason at a higher level. In computing it appears in functions, classes, and layered protocols, and it is a core concept in standards for CS education.

Bundling data with the methods that operate on it and restricting direct outside access, usually through private fields and public methods. It protects invariants and reduces coupling between parts of a program.

A relationship in which a class acquires fields and methods from a parent class and may override or extend them. It models an is-a relationship and supports polymorphism but can create tight coupling.

The ability of one interface or method name to work with multiple underlying types, resolved at compile time by overloading or at run time by overriding. It lets client code treat related objects uniformly.

A declared set of method signatures with no implementation that a class promises to provide. It defines a contract enabling substitution and testing without depending on a concrete class.

A defined set of functions, protocols, and data formats through which one software component requests services from another. Good APIs document inputs, outputs, errors, and versioning so callers need not know internals.

A system that records changes to files over time so prior states can be inspected, compared, and restored. Distributed tools let each developer hold a full repository and merge branches.

An automated check that exercises one small piece of code in isolation and asserts an expected result. Tests document intent, catch regressions, and drive design toward smaller, testable units.

The process of locating, understanding, and correcting defects in software. It combines reproducing the fault, forming hypotheses, inspecting state with breakpoints or print output, and confirming the fix.

A rule in which the second operand of AND or OR is evaluated only when the first does not already determine the result. It enables guarded checks such as testing for null before dereferencing.

A fixed-size, indexed collection of elements of one type stored in contiguous memory, giving constant-time access by position. Insertion and deletion in the middle require shifting elements.

A linear structure of nodes, each holding data and a reference to the next node, with no contiguous storage requirement. Insertion and deletion are cheap once a position is found, but access is sequential.

A last-in, first-out collection supporting push and pop at one end. It models call management, expression evaluation, and undo history, and is often implemented over an array or linked list.

A first-in, first-out collection that adds at the rear and removes at the front. It models scheduling, buffering, and breadth-first traversal, and a circular array or linked list implements it efficiently.

A structure mapping keys to values through a hash function that computes an index, giving average constant-time lookup. Collisions are handled by chaining or open addressing and degrade performance when severe.

A binary tree where each node's left subtree holds smaller keys and its right subtree larger keys. Ordered traversal yields sorted output, and operations cost logarithmic time only when the tree stays balanced.

Systematically visiting graph vertices, using a queue for breadth-first order or a stack or recursion for depth-first order. Traversals support reachability, path finding, cycle detection, and topological sorting.

A database that stores data in tables of rows and columns and enforces relationships through keys and constraints. Queries use SQL, and normalization reduces redundancy and update anomalies.

A column or column set that uniquely identifies each row in a table and cannot be null. It enforces entity integrity and is commonly referenced by foreign keys in other tables.

A column or column set whose values must match a primary key in another table, or be null. It enforces referential integrity and expresses relationships between tables.

A declarative language for defining, querying, and modifying relational data. Statements such as SELECT, INSERT, UPDATE, and DELETE specify what result is wanted, leaving execution planning to the database engine.

A binary representation of signed integers in which the most significant bit carries negative weight. Negation is performed by inverting bits and adding one, and it avoids separate circuits for subtraction.

A condition where a computed result exceeds the range representable in the allocated bits, silently wrapping or raising an error depending on the language. It is a classic source of security and logic bugs.

A runtime structure holding one frame per active function call, with parameters, local variables, and return addresses. Deep or unbounded recursion exhausts it and causes a stack overflow.

Software that manages hardware, schedules processes, allocates memory, and provides file and device abstractions to applications. It enforces protection between processes and handles interrupts and system calls.

An abstraction giving each process its own contiguous address space mapped to physical frames by the memory management unit. It enables protection, sharing, and use of disk when RAM is short.

A state where processes each hold a resource and wait for another held by a peer, so none can proceed. It requires mutual exclusion, hold and wait, no preemption, and circular wait.

An agreed set of rules governing message format, timing, and meaning between communicating systems. Layered protocols such as TCP/IP separate concerns so each layer relies on the services below it.

A numeric label assigned to a network interface that identifies it for routing, in IPv4 or IPv6 form. It works with subnet masks and routing tables to deliver packets between networks.

A distributed hierarchical service that translates human-readable domain names into IP addresses through recursive and authoritative queries. It also stores mail routing and other record types.

Transforming readable data into ciphertext with a key so only authorized parties can recover it. Symmetric schemes share one key; asymmetric schemes use a public and private key pair.

A value computed with a sender's private key that a receiver verifies with the public key, proving origin and integrity. It provides authentication and non-repudiation but not confidentiality by itself.

A social-engineering attack that impersonates a trusted party through email, messages, or fake sites to steal credentials or install malware. Defenses include user training, sender verification, and multi-factor authentication.

Legal rights protecting creations of the mind, including copyright, patents, trademarks, and trade secrets. Software may be covered by copyright and, for some inventions, by patents.

A license granting rights to use, study, modify, and redistribute source code under stated conditions. Permissive licenses allow proprietary reuse; copyleft licenses require derivative works to stay under the same terms.

A family of standardized public licenses letting creators grant reuse rights with combinations of attribution, share-alike, and non-commercial or no-derivatives conditions. It is common for educational and media content, not software.

Unequal access to devices, reliable connectivity, and the skills to use them, often along income, geography, or disability lines. It shapes how equitably computing education and digital services can be delivered.

Systematic unfair outcomes produced by automated systems, arising from biased training data, flawed labels, or proxy variables. It raises ethical and legal questions about transparency, accountability, and auditing of deployed models.

A framework that plans instruction with multiple means of engagement, representation, and action so varied learners can succeed. In CS it suggests offering text and video explanations and choices in how projects are demonstrated.

Ongoing checks during instruction that reveal student understanding and guide immediate teaching adjustments. Examples include exit tickets, live coding observation, and ungraded peer review of programs.

Evaluation at the end of a unit or course that measures achievement against standards and often assigns a grade. Projects, written tests, and performance tasks are typical forms in computer science courses.

A scoring guide listing criteria and descriptions of performance levels, used to judge open-ended work consistently. Well-written rubrics share criteria with students in advance and separate correctness from style.

Temporary support such as worked examples, starter code, or guided prompts that helps students complete a task they could not yet do alone. Support is gradually removed as competence grows.

A collaborative practice where two students share one workstation, one typing and the other reviewing and planning, with roles swapped regularly. It supports communication and code quality when both partners stay engaged.