ILTS Computer Science (205) 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 an algorithm's growth rate as input size grows, ignoring constants and lower-order terms, such as O(n log n) for merge sort.

Binary search precondition

The array must be sorted and support random access; the algorithm then halves the search interval each step, achieving O(log n) time.

Stable sort

A sorting algorithm that preserves the relative order of elements with equal keys, which matters when sorting records by multiple fields in sequence.

Two's complement

A signed binary representation in which negation inverts all bits and adds one; an n-bit value ranges from -2^(n-1) to 2^(n-1)-1.

Dijkstra's algorithm

A single-source shortest-path algorithm for graphs with non-negative edge weights that repeatedly settles the nearest unvisited vertex using a priority queue.

Pass by value

A parameter-passing method in which the procedure receives a copy of the argument, so assignments to the parameter do not affect the caller's variable.

While versus do-while

A while loop tests its condition before each iteration and may run zero times; a do-while tests after the body and always runs at least once.

Recursion base case

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

Polymorphism

The ability of a single interface or method call to invoke different implementations depending on the runtime type of the object being referenced.

Unit test

An automated test that exercises one small unit of code in isolation and asserts that actual results match expected results, enabling safe refactoring.

Encapsulation

Bundling data with the methods that operate on it and restricting direct access to internal state, typically through private fields and public accessors.

Stack data structure

A last-in-first-out collection supporting push and pop at one end; used for function calls, undo history, and expression evaluation.

Hash table load factor

The ratio of stored entries to available buckets; high load factors increase collisions and can degrade average lookup time from O(1) toward O(n).

Binary search tree inorder traversal

Visiting left subtree, then root, then right subtree of a binary search tree produces keys in ascending sorted order.

Primary key

A column or column set that uniquely identifies each row in a relation, must be unique, and cannot contain null values.

Foreign key

An attribute in one table that references the primary key of another table, enforcing referential integrity between related records.

Third normal form

A relation in second normal form with no transitive dependencies, meaning non-key attributes depend only on candidate keys, not on other non-key attributes.

ACID properties

Four transaction guarantees: atomicity (all or nothing), consistency (valid states), isolation (concurrent transactions do not interfere), and durability (committed changes persist).

Fetch-decode-execute cycle

The processor repeatedly fetches the instruction addressed by the program counter, decodes its operation, executes it, and stores any result.

TCP versus UDP

TCP is connection-oriented and reliable, using handshakes and retransmission; UDP is connectionless and unreliable but has lower latency and overhead.

DNS function

The Domain Name System translates human-readable hostnames into IP addresses through a hierarchical, distributed set of name servers.

Symmetric encryption

Encryption using a single shared secret key for both encryption and decryption; fast enough for bulk data but requires secure key distribution.

SQL injection

An attack in which untrusted input is concatenated into a query so it alters the statement's logic; prevented by parameterized queries and input validation.

Subnet mask

A 32-bit value that identifies which bits of an IPv4 address denote the network portion and which denote the host portion.

FERPA

A U.S. federal law protecting students' education records, restricting disclosure without consent and giving students and parents inspection rights.

Copyleft license

An open-source license, such as the GPL, requiring derivative works distributed to others to be released under the same license terms.

Fair use factors

A four-factor U.S. legal test weighing purpose of use, nature of the work, amount used, and effect on the market for the original.

Digital divide

Unequal access to computing devices, reliable internet, and digital skills across socioeconomic, geographic, or demographic groups.

Formative assessment

Assessment conducted during instruction to reveal current understanding and guide immediate teaching adjustments, typically low-stakes and feedback-focused.

Summative assessment

Assessment administered at the end of a unit or course to judge achievement against standards, such as a final exam or scored project.

Parsons problem

An exercise presenting shuffled lines of a correct program for students to reorder, assessing logic and sequencing while removing syntax transcription burden.

PRIMM model

A teaching sequence: Predict program behavior, Run it, Investigate the code, Modify it, then Make a new program, gradually shifting from reading to writing code.