ADS Logs

An algorithm is a step-by-step instruction that solves a problem in bounded time; its cost is measured by counting primitive operations — the small steps whose duration does not depend on the input size. The definition carries a requirement that is easy to read past: bounded time...

Quiz: ADS / Asymptotic Analysis, O-Notation and Recursion | updated: Oct 13, 2026

An array-list wraps a plain array and resizes it automatically; an add into a free slot is $O(1)$, but an add into a full array first copies every element into a bigger one, which is $O(n)$. * The fourth add fits; the fifth finds the array full and pays for copying all four firs...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Oct 13, 2026

Doubling makes the expensive copies so rare that their total cost is proportional to the number of adds — on average each add costs $O(1)$ (amortised). Growing by a constant amount makes every few adds pay a full copy, giving $O(n^2)$ for $n$ adds. * The spikes get taller but tw...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026

Remember u's old successor w ← u.next, point v at both neighbours (v.prev ← u, v.next ← w), then point the neighbours at v (w.prev ← v, u.next ← v) — four reference writes, $O(1)$. * v is wired to both neighbours first; only then are u and w redirected to v. * Algorithm addAfter...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026

pop() → 3, top() → 9, pop() → 9, pop() → 7; the stack ends as (5). * Each pop takes the most recent push that is still there. * Trace it, bottom on the left, top on the right: Operation Returns Stack push(5) — (5) push(3) — (5, 3) pop() 3 (5) push(7) — (5, 7) push...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026

A deque ("deck") allows inserting and removing at both ends: addFirst, addLast, removeFirst, removeLast, plus first() and last() to look without removing; reading from an empty deque returns null. * A stack uses one end, a queue uses each end for one job, a deque uses both ends...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026

The height of a leaf is 0; the height of an internal node is 1 + the maximum height of its children. The height of a tree is the height of its root, which equals the depth of its deepest node. * Depth is measured down from the root; height is measured up from the deepest leaf be...

Quiz: ADS / Trees: Structure, Storage and Traversals | updated: Sep 29, 2026

Strengths: no references to store, and every child or parent is found by index arithmetic in $O(1)$. Weakness: the array needs a slot for every rank up to the highest one, so an unbalanced tree wastes enormous amounts of space — up to $2^n$ slots for $n$ nodes. The rank of a node...

Quiz: ADS / Trees: Structure, Storage and Traversals | updated: Sep 29, 2026

Recursively: a leaf returns its number; an internal node first evaluates its left and right subtree, then applies its operator to the two results. The node is handled after its children — postorder. For $((2 × (5 − 1)) + (3 × 2))$ the result is 14. * Values flow upwards: 5 − 1 =...

Quiz: ADS / Trees: Structure, Storage and Traversals | updated: Sep 29, 2026

A chain of nodes where each node holds one element and a reference to the next node; the last node points to null, and the list keeps a reference to the first node (the head) as its entry point. A node is a tiny object with exactly two fields: public class Node { private Elemen...

Quiz: ADS / Linear Data Structures: Lists, Stacks, Queues, Deques, Iterators | updated: Sep 29, 2026