BCS Written Computer Science flashcards

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

Von Neumann bottleneck

The limited data transfer rate between CPU and memory when instructions and data share a single bus, capping throughput regardless of processor speed.

Amdahl's law

Speedup from improving one part is bounded by the sequential fraction: speedup = 1 / ((1 − f) + f/s), where f is the enhanced fraction and s the gain.

Cache write-back

A cache policy that updates main memory only when a modified block is evicted, tracked by a dirty bit, reducing memory traffic versus write-through.

Two's complement

A binary representation of signed integers where the most significant bit carries negative weight, giving a range of −2^(n−1) to 2^(n−1) − 1 for n bits.

DMA transfer

Direct memory access moves blocks between a device and memory without per-byte CPU control, raising one interrupt when the transfer completes.

Hash table load factor

The ratio of stored entries to buckets, n/m. Higher values raise collision probability and probe lengths; resizing keeps average lookup near constant time.

Binary search precondition

The array must be sorted; the algorithm then halves the interval each step, comparing the target with the middle element in O(log n) time.

Dijkstra's algorithm

A greedy single-source shortest-path algorithm for graphs with non-negative edge weights, repeatedly settling the nearest unsettled vertex using a priority queue.

Minimum spanning tree

A subset of a connected weighted graph's edges linking all vertices with minimum total weight and no cycles, found by Kruskal's or Prim's algorithm.

Stack versus queue

A stack removes the most recently added item (LIFO); a queue removes the earliest added item (FIFO). Both support constant-time insertion and deletion.

Merge sort complexity

A divide-and-conquer sort that splits, sorts halves recursively, and merges them in O(n log n) guaranteed time, requiring O(n) auxiliary space.

Static versus dynamic typing

Static typing checks type compatibility at compile time, catching errors early; dynamic typing defers checks to run time, allowing more flexible code.

Polymorphism

The ability of one interface to represent different underlying types: overloading resolves at compile time, overriding dispatches at run time.

Pass by reference

The callee receives the argument's address rather than a copy, so modifications inside the function are visible to the caller after return.

Recursion base case

The terminating condition that stops recursive calls. Without a reachable base case, recursion consumes stack frames until a stack overflow occurs.

ACID properties

Atomicity, Consistency, Isolation, and Durability: guarantees that transactions complete fully, preserve valid states, do not interfere, and persist once committed.

Third normal form

A relation in 2NF with no transitive dependency of a non-key attribute on the primary key; every non-key attribute depends only on candidate keys.

Foreign key

An attribute referencing a candidate key of another relation, enforcing referential integrity so referenced rows cannot be deleted while dependents exist.

Database view

A named stored query acting as a virtual table, used to restrict column and row access and simplify queries without duplicating stored data.

TCP versus UDP

TCP is connection-oriented with handshake, acknowledgements, and ordered reliable delivery; UDP is connectionless and best-effort, suited to latency-sensitive traffic.

Subnet host count

For an IPv4 prefix length p, total addresses are 2^(32−p); usable host addresses subtract two for the network and broadcast addresses.

DNS resolution

Translation of human-readable domain names into IP addresses through hierarchical name servers, caching results according to time-to-live values.

OSI model layers

Seven abstraction layers: Physical, Data Link, Network, Transport, Session, Presentation, and Application, each providing services to the layer above.

Context switch

The operating system saving the registers and program counter of a running process and restoring another's so execution can resume later.

Deadlock conditions

Four simultaneous conditions cause deadlock: mutual exclusion, hold-and-wait, no preemption, and circular wait. Breaking any one prevents it.

Thrashing

A state where excessive page faults consume most processor time because processes have too few frames, sharply reducing useful throughput.

Round robin scheduling

A preemptive CPU policy granting each ready process a fixed time quantum in turn, providing fairness and good response time for interactive workloads.

Coupling and cohesion

Cohesion measures how strongly a module's internal elements belong together; coupling measures interdependence between modules. Good design maximizes cohesion and minimizes coupling.

Verification versus validation

Verification confirms the product is built correctly according to specification; validation confirms the correct product was specified, meeting user needs.

Boundary value analysis

A black-box test technique selecting inputs at and just outside the edges of valid ranges, where defects cluster, complementing equivalence partitioning.

Digital signature

A hash of a message encrypted with the sender's private key; the recipient verifies it with the public key, proving integrity and origin.

Public key infrastructure

A framework of certificate authorities, policies, and certificates binding public keys to verified identities, enabling trusted encryption and digital signatures.

Role-based access control

An access control model granting permissions to roles rather than individuals; users acquire permissions by being assigned roles, simplifying administration.

Cloud service models

IaaS supplies virtualized infrastructure, PaaS supplies a managed application platform, and SaaS supplies complete applications, shifting management responsibility to the provider.

Blockchain immutability

Each block stores the previous block's hash, so altering any record breaks the chain and is detected by network participants holding copies.

G2C service delivery

Government-to-citizen digital services deliver information and transactions online, reducing queues and improving transparency and accessibility.

Digital divide

Unequal access to and skill in using information and communication technologies across regions, incomes, ages, and education levels.