VCE Algorithmics (HESS) flashcards
VCE Algorithmics (HESS) · Build recall with a focused review session.
32 cards. Read the term and the definition here. The deck at the top of this page is optional.
- Big-O notation
- An asymptotic upper bound on an algorithm's growth rate: f(n) = O(g(n)) means f grows no faster than a constant multiple of g for large n.
- Big-Theta notation
- A tight asymptotic bound: f(n) = Θ(g(n)) means f is bounded both above and below by constant multiples of g for sufficiently large n.
- Linear search complexity
- Scanning each element in turn until a match is found. Worst case Θ(n) comparisons and works on unsorted data, unlike binary search which needs sorted input.
- Binary search precondition
- The array must be sorted. Each iteration compares the target with the middle element and discards half the remaining range, giving O(log n) comparisons.
- Merge sort
- A divide-and-conquer sort that splits the array in half, sorts each half recursively, then merges them. Θ(n log n) in all cases, using O(n) extra space.
- Quicksort worst case
- Θ(n²) comparisons, occurring when the pivot is repeatedly the smallest or largest element, such as choosing the first element of already-sorted input.
- Insertion sort best case
- Θ(n) comparisons on already-sorted input, because each new element needs only one comparison to confirm it is in place; worst case is Θ(n²).
- Stack data structure
- A last-in-first-out collection supporting push and pop at one end. Both operations are O(1) when implemented with a linked list or array with a top index.
- Queue data structure
- A first-in-first-out collection: elements are enqueued at the rear and dequeued from the front. A circular array or linked list gives O(1) operations.
- Hash table collision
- Two distinct keys mapping to the same bucket. Collisions are resolved by chaining or open addressing, and excessive collisions degrade average O(1) operations toward O(n).
- Breadth-first search
- A graph traversal using a queue that explores all vertices at distance k before distance k+1, finding shortest unweighted paths in O(V + E) time.
- Depth-first search
- A graph traversal using a stack or recursion that follows one path as far as possible before backtracking, enabling cycle detection and topological sorting in O(V + E).
- Adjacency list
- A graph representation storing each vertex's neighbours in a list. Space is O(V + E), making it efficient for sparse graphs compared with an O(V²) adjacency matrix.
- Master theorem case
- For T(n) = aT(n/b) + f(n), compare f(n) with n^log_b a; if f is polynomially smaller the solution is Θ(n^log_b a), if equal it gains a log factor.
- Amortised analysis
- Averaging an operation's cost over a worst-case sequence of operations. Dynamic array append is O(1) amortised despite occasional O(n) resizing copies.
- Loop invariant
- A property true before the loop, preserved by every iteration, and true at termination. These three conditions together prove the algorithm's correctness.
- Class P
- The set of decision problems solvable by a deterministic algorithm in polynomial time, such as sorting, shortest path and primality testing. P is contained in NP.
- Class NP
- Decision problems whose yes-instances have a certificate verifiable in polynomial time. Every problem in P is in NP, since the solution itself can be checked.
- NP-complete problem
- A problem in NP to which every NP problem reduces in polynomial time. Examples include SAT, 3-SAT, Hamiltonian cycle and subset sum.
- NP-hard problem
- A problem at least as hard as every problem in NP, but not necessarily itself in NP because its solutions may be unverifiable in polynomial time.
- Polynomial-time reduction
- A transformation from instances of problem A to instances of problem B computable in polynomial time, such that answers are preserved. It transfers hardness from A to B.
- Proving NP-completeness
- Two steps: show the problem lies in NP by giving a polynomial-time verifier, then reduce a known NP-complete problem to it in polynomial time.
- Boolean satisfiability (SAT)
- Deciding whether some assignment of true/false to variables makes a Boolean formula true. SAT was the first problem proved NP-complete.
- Travelling salesman problem
- Finding the shortest tour visiting every city exactly once. The decision version is NP-complete; exact solutions require exponential time in the worst case.
- Halting problem
- Deciding whether an arbitrary program halts on a given input. Turing proved no algorithm can decide this for all program-input pairs, so it is undecidable.
- Decidable language
- A language for which some Turing machine halts on every input, accepting strings in the language and rejecting those outside it. Undecidable languages lack such a machine.
- Turing machine
- An abstract computer with finite states, an unbounded tape and a read/write head. It defines the limits of what any algorithm can compute.
- Approximation algorithm
- An algorithm returning a feasible solution within a proven factor of optimal in polynomial time, used when the exact problem is NP-hard.
- Heuristic method
- A strategy such as greedy selection or local search that seeks good solutions quickly without guaranteeing optimality, often applied to intractable optimisation problems.
- Branch and bound
- An exact search that prunes partial solutions whose optimistic bound cannot beat the best found, often solving hard instances far faster than brute force.
- Greedy algorithm failure
- Greedy choice works only when the problem has optimal substructure and the greedy-choice property; coin change with arbitrary denominations is a standard counterexample.
- Algorithmic bias
- Systematic unfair outcomes produced when training data or design choices encode existing inequities, a key ethical concern when algorithms decide on people's lives.