NZ Scholarship Digital Technologies 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 algorithm's asymptotic upper bound on growth rate, ignoring constants and lower-order terms, so 3n^2 + 5n + 7 is classified as O(n^2).

Binary search complexity

Searching sorted data by halving the interval each step, giving O(log n) comparisons. It requires sorted input and random access, so it is unsuitable for linked lists.

Hash table average lookup

With a good hash function and low load factor, lookup, insert and delete average O(1). Collisions degrade this toward O(n) worst case.

Stack versus queue

A stack is last-in-first-out, with push and pop at one end. A queue is first-in-first-out, with enqueue at the rear and dequeue at the front.

Breadth-first search

A graph traversal using a queue that explores vertices level by level. On unweighted graphs it finds shortest paths in O(V+E) with adjacency lists.

Dijkstra's algorithm

Finds single-source shortest paths on graphs with non-negative edge weights using a priority queue, running in O((V+E) log V) with a binary heap.

Minimum spanning tree

A subset of V-1 edges connecting all vertices with minimum total weight. Kruskal sorts edges and uses union-find; Prim grows from a start vertex.

Dynamic programming memoisation

Caching results of overlapping subproblems so each is computed once, converting exponential naive recursion into polynomial time at the cost of extra memory.

Third normal form

A relational table is in 3NF when it is in 2NF and no non-key attribute depends transitively on the primary key, reducing redundancy and update anomalies.

ACID properties

Atomicity, consistency, isolation and durability: transactions either complete fully or not at all, preserve valid states, do not interfere, and persist after failure.

SQL HAVING versus WHERE

WHERE filters individual rows before grouping, while HAVING filters groups after GROUP BY, typically applied to aggregate results such as COUNT or SUM.

TCP versus UDP

TCP is connection-oriented with ordered, reliable delivery and flow control. UDP is connectionless with no delivery guarantee, favoured for low-latency streaming and DNS.

CIDR /24 host count

A /24 IPv4 prefix leaves 8 host bits, giving 2^8 = 256 addresses; subtracting network and broadcast leaves 254 usable host addresses.

Encoding versus encryption

Encoding such as Base64 is reversible without a key and provides no secrecy. Encryption is reversible only with a key and protects confidentiality.

Digital signature mechanism

The sender hashes the message and encrypts the hash with their private key; anyone verifies using the sender's public key, giving integrity and authenticity.

TLS handshake

TLS uses asymmetric cryptography to authenticate and exchange a session key, then symmetric encryption for bulk data, providing confidentiality and integrity in transit.

Agile versus Scrum

Agile is a set of values favouring working software and responding to change. Scrum is a framework implementing them with timeboxed sprints, a backlog and defined roles.

Kanban WIP limits

Kanban caps work in progress to expose bottlenecks and improve flow. Little's Law states average lead time equals WIP divided by throughput.

Usability heuristics

General interface principles including visibility of system status, consistency, error prevention, user control, and recognition over recall, used to evaluate designs.

Git commit graph

Commits form a directed acyclic graph where each commit points to its parent. Branches are movable pointers; merging preserves history while rebasing rewrites it.

Cryptographic hash properties

A secure hash is deterministic, fast to compute, and collision-resistant. MD5 and SHA-1 are deprecated for security because practical collisions exist.

Moore's Law

An empirical trend that transistor count on integrated circuits doubles roughly every two years. It is an observation about manufacturing, not a physical law.

Finite state machine

A model with finite states, transitions, an initial state and accepting states. It recognises regular languages but cannot model unbounded memory like a Turing machine.

Halting problem

The undecidable problem of determining whether an arbitrary program halts on a given input. Turing proved no general algorithm can decide it for all cases.

Stable sorting

A sort is stable when equal keys keep their original relative order. Merge sort is stable and O(n log n); quicksort is typically unstable and O(n^2) worst case.

Greedy algorithm correctness

A greedy strategy is correct only if the problem has optimal substructure and the greedy-choice property; otherwise dynamic programming or exhaustive search is required.

Primary versus foreign key

A primary key uniquely identifies each row in a table. A foreign key references another table's primary key, enforcing referential integrity between related tables.

Database index trade-off

Indexes speed up reads and lookups but slow inserts and updates and consume storage. A composite index supports queries on its leading column first.

Symmetric versus asymmetric encryption

Symmetric encryption uses one shared key and is fast, suitable for bulk data. Asymmetric encryption uses a public/private pair, solving key distribution and enabling signatures.

IPv6 address size

IPv6 uses 128-bit addresses versus IPv4's 32 bits, providing a vastly larger address space and removing the need for NAT in most deployments.

Version control branching

Branches are pointers to commits allowing parallel work. Merging combines divergent histories into one, while rebasing reapplies commits onto a new base and rewrites history.

Recursion space cost

Each recursive call consumes a stack frame, so recursion depth n uses O(n) space. A base case is required to terminate, and deep recursion risks stack overflow.