OAE Computer Science flashcards

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

Two's complement range

For n bits the representable signed range is -2^(n-1) through 2^(n-1)-1. The leftmost bit has place value -2^(n-1), so 8 bits span -128 to 127.

De Morgan's laws

The negation of a conjunction equals the disjunction of the negations: not (A and B) is (not A) or (not B). The dual form applies to disjunction.

Big-O definition

An upper bound on growth rate ignoring constants and lower-order terms. It describes how runtime scales as input size grows, not actual seconds of execution.

Master Theorem

Solves recurrences of the form T(n) = aT(n/b) + f(n) by comparing f(n) with n raised to log base b of a. The larger term dominates the asymptotic result.

Greedy algorithm

Builds a solution by repeatedly choosing the locally best option and never revisiting it. It is correct only when the problem has the greedy-choice property and optimal substructure.

Dynamic programming

Solves problems by combining solutions to overlapping subproblems, storing each result once to avoid recomputation. It requires optimal substructure and is often implemented with memoization or tabulation.

Boolean XOR

The exclusive-or operation returns true only when exactly one input is true. It equals (A and not B) or (not A and B) and is 1 when the bits differ.

Pass by value

The callee receives a copy of the argument, so reassigning the parameter never changes the caller's variable. Objects passed this way still share the referenced data.

Short-circuit evaluation

In a logical AND, the right operand is skipped when the left is false; in a logical OR, it is skipped when the left is true. This prevents needless or unsafe evaluation.

Compile-time vs runtime error

Compile-time errors violate language rules and block code generation, such as a missing semicolon. Runtime errors occur during execution, such as division by zero or a null dereference.

Variable scope

The region of a program where a name is visible. Block-scoped variables exist from declaration to the closing brace, and an inner declaration can shadow an outer one.

Unit vs integration test

A unit test exercises one function or class in isolation with controlled inputs. An integration test verifies that multiple components work together, often exposing interface mismatches.

While vs do-while loop

A while loop tests its condition before each pass, so it may run zero times. A do-while loop tests after the body, guaranteeing at least one execution.

Break vs continue

Break exits the innermost enclosing loop immediately. Continue skips the rest of the current iteration and proceeds to the loop's next condition check or increment.

Function return value

The result a function hands back to its caller via a return statement. A function without one returns a default or void, depending on the language.

Array access complexity

Indexed access to an array is constant time because the address is computed arithmetically from the base address. Inserting or deleting in the middle shifts elements and costs linear time.

Stack vs queue

A stack removes the most recently added item (LIFO), supporting push and pop. A queue removes the oldest item (FIFO), supporting enqueue at the rear and dequeue at the front.

Binary search precondition

The array must be sorted and support random access. Each comparison halves the search interval, giving logarithmic time; on unsorted data the result is unreliable.

BST in-order traversal

Visiting a binary search tree's left subtree, then node, then right subtree produces values in ascending sorted order. This property also underlies validation of a BST.

Hash table load factor

The ratio of stored entries to bucket count. A high load factor increases collisions and slows lookups, so tables resize and rehash when it crosses a threshold.

Min-heap property

Every parent node is less than or equal to its children, placing the smallest value at the root. Insert and extract-min cost logarithmic time while peek is constant time.

Merge sort properties

A stable divide-and-conquer sort that splits the array, sorts halves, and merges them. It runs in O(n log n) time in all cases but needs O(n) auxiliary space.

Quicksort worst case

Repeatedly choosing the smallest or largest element as pivot splits off one element per pass, degrading to quadratic time. Random or median pivots make this unlikely.

BFS vs DFS

Breadth-first search explores level by level with a queue and finds shortest unweighted paths. Depth-first search follows one branch deeply with a stack and detects cycles.

CPU fetch-decode-execute cycle

The processor fetches an instruction from memory, decodes its operation, executes it in the ALU or control unit, and writes the result back to registers or memory.

Cache locality

Temporal locality means recently used data is likely reused soon; spatial locality means nearby addresses are likely accessed next. Both raise cache hit rates and speed execution.

Virtual memory and paging

Each process sees a private virtual address space mapped to physical frames through page tables. A TLB caches recent translations to avoid extra memory accesses.

OSI layers

Seven layers: physical, data link, network, transport, session, presentation, application. Each layer provides services to the one above and uses the one below.

TCP vs UDP

TCP establishes a connection, acknowledges segments, and retransmits lost data, guaranteeing order. UDP sends datagrams without guarantees, suiting real-time and low-overhead traffic.

Symmetric vs asymmetric encryption

Symmetric encryption uses one shared secret key for both directions and is fast. Asymmetric encryption uses a public key to encrypt and a private key to decrypt, easing key distribution.

SQL injection defense

Untrusted input concatenated into a query can alter its logic. Parameterized queries and prepared statements separate code from data, preventing injected fragments from executing.

CIA triad

Confidentiality keeps data secret from unauthorized readers, integrity ensures it is unaltered and trustworthy, and availability ensures timely access to authorized users.