OSAT Computer Science (OK181) flashcards

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

Computational thinking pillars

Decomposition breaks problems into parts, pattern recognition finds similarities, abstraction ignores irrelevant detail, and algorithm design produces ordered steps. Together they frame problem solving before any code is written.

Two's complement negation

To negate a binary integer, invert every bit and add one. An n-bit signed value ranges from negative two to the n minus one power up to two to the n minus one, minus one.

De Morgan's laws

The negation of A and B equals not-A or not-B; the negation of A or B equals not-A and not-B. These identities let you rewrite and simplify Boolean conditions and gate circuits.

UTF-8 encoding

A variable-length Unicode encoding using one to four bytes per code point. Code points below 128 match ASCII exactly, so ASCII text is valid UTF-8, which made adoption widespread.

Finite state machine

An abstract model with a fixed set of states, an input alphabet, a transition function, a start state, and accepting states. It has no memory beyond its current state.

Pass by value vs reference

Passing by value copies the argument so the function cannot change the caller's variable. Passing by reference shares the original object, so mutations inside the function are visible outside.

Loop invariant

A condition true before and after every iteration of a loop. Establishing it before the loop and preserving it each pass proves correctness, and together with a variant it supports termination arguments.

Recursion base case

The condition that stops recursive calls and returns a value directly. Every recursive case must move toward the base case, otherwise the call stack grows until a stack overflow occurs.

Binary search precondition

Binary search runs in logarithmic time but requires the data to be sorted and directly indexable. It compares the target with the middle element and discards half the remaining range each step.

Merge sort complexity

Merge sort divides the array in half, sorts each half recursively, then merges them. It runs in n log n time in best, average, and worst cases but needs extra space proportional to n.

Hash table load factor

The ratio of stored entries to buckets. As it approaches one, collisions increase and lookups degrade from constant toward linear time, so implementations resize and rehash when it crosses a threshold.

Binary search tree ordering

For every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. In-order traversal then visits keys in sorted order; balance determines logarithmic versus linear performance.

Stack versus queue

A stack removes the most recently added item (last in, first out) and supports push and pop. A queue removes the oldest item (first in, first out) and supports enqueue and dequeue.

Adjacency list tradeoff

A graph representation storing each vertex's neighbors as a list. It uses space proportional to vertices plus edges, suiting sparse graphs, but checking whether a specific edge exists takes linear time.

Breadth-first search

A traversal using a queue that visits all vertices at distance one, then distance two, and so on. On unweighted graphs it finds shortest paths measured in edge count.

Heap priority queue

A complete binary tree stored in an array where each parent outranks its children. Peeking at the top is constant time, while insertion and removal cost logarithmic time, making it ideal for priority queues.

CPU fetch-decode-execute

The instruction cycle: fetch the instruction at the program counter, decode its operation, execute it using the arithmetic logic unit or memory, then store results and advance the counter.

TCP versus UDP

TCP is connection-oriented, acknowledges segments, retransmits losses, and preserves order. UDP is connectionless and best-effort with lower overhead, chosen for streaming, gaming, and DNS queries.

CIA triad

Confidentiality keeps data secret from unauthorized parties, integrity keeps it unaltered and trustworthy, and availability keeps it accessible to authorized users when needed. Security controls map to these goals.

SQL injection defense

An attack where untrusted input alters a database query. Defenses are parameterized queries or prepared statements, input validation, least-privilege database accounts, and avoiding string concatenation of queries.

Primary versus foreign key

A primary key uniquely identifies each row and cannot be null. A foreign key holds a value matching a primary key in another table, enforcing referential integrity between related tables.

Third normal form

A table is in third normal form when it is in second normal form and no non-key attribute depends transitively on the primary key. This removes redundancy that causes update and deletion anomalies.

ACID transaction properties

Atomicity means all operations succeed or none do; consistency preserves valid database states; isolation prevents concurrent transactions from interfering; durability keeps committed changes after failures.

SQL WHERE versus HAVING

WHERE filters individual rows before grouping and cannot test aggregate results. HAVING filters groups after GROUP BY and can reference aggregates such as COUNT or SUM.

Correlation versus causation

Correlation means two variables vary together; causation means one produces change in the other. Confounding variables can create correlation without causation, so experiments or careful controls are needed.

ACM Code of Ethics

A professional code whose general principles include contributing to society and human well-being, avoiding harm, being honest and trustworthy, being fair, and respecting privacy and intellectual property.

Copyright versus patent

Copyright protects original expression such as source code once fixed in a medium. A patent protects a novel, useful invention or process and must be applied for and granted.

Digital divide

Unequal access to computing devices, reliable connectivity, and the skills to use them. It affects educational opportunity and economic outcomes, and is addressed through access and training programs.

WCAG accessibility principles

Web content should be perceivable, operable, understandable, and robust. Practical measures include captions, alternative text, keyboard navigation, and sufficient color contrast for readability.

Formative versus summative

Formative assessment happens during learning to adjust instruction, such as exit tickets and peer review. Summative assessment happens at the end to measure achievement, such as unit tests and projects.

PRIMM instructional model

A sequence of predict, run, investigate, modify, and make. Students read and reason about existing code before editing it and finally write original programs, reducing cognitive load from syntax.

Parsons problem

An exercise giving students scrambled lines of a working program to reorder correctly. It focuses attention on program structure and logic while removing the burden of typing exact syntax.

AP CSA versus CSP

AP Computer Science A is a Java programming course with free-response coding questions. AP Computer Science Principles emphasizes computational thinking, impacts of computing, and a project-based performance task.