Computer Science

Data Structures

Arrays and Linked Lists

• Array — contiguous block of memory; random access O(1); insertion/deletion at arbitrary index O(n) due to shifting; fixed size in static variants, amortized O(1) append in dynamic arrays.
• Dynamic array (ArrayList / vector) — doubles capacity when full; amortized O(1) append; underlying copies are O(n) but infrequent.
• Linked list (singly) — each node stores a value and a pointer to the next node; O(1) head insertion/deletion; O(n) search and arbitrary access; no wasted capacity.
• Doubly linked list — each node stores prev and next pointers; O(1) deletion given the node; used in LRU cache implementations.

Stacks and Queues

• Stack — LIFO; push/pop/peek all O(1); implemented with array or linked list; used for function call frames, expression parsing, DFS.
• Queue — FIFO; enqueue/dequeue O(1) with circular array or linked list; used for BFS, scheduling.
• Deque (double-ended queue) — O(1) insertion and deletion at both ends; sliding-window problems.
• Priority queue — element with the highest (or lowest) priority is dequeued first; typically implemented as a heap; O(log n) push/pop.

Trees

• Binary tree — each node has at most two children; a complete binary tree fills levels left to right; a perfect binary tree has all leaves at the same level.
• Binary search tree (BST) — left child < parent < right child; search/insert/delete O(h) where h is height; degenerates to O(n) for sorted input.
• AVL tree — self-balancing BST; height difference between subtrees ≤ 1; rotations maintain O(log n) operations.
• Red-black tree — self-balancing BST with node coloring; guarantees O(log n); used in C++ std::map, Java TreeMap, Linux scheduler.
• B-tree — generalized balanced tree with branching factor > 2; nodes can hold many keys; minimizes disk I/O; standard in database index structures; B+ tree variant stores all data in leaves with leaf-to-leaf linked list.
• Trie (prefix tree) — tree where each path from root to node encodes a string prefix; O(m) search where m is string length; used in autocomplete, spell-check.
• Segment tree — binary tree over an array; supports range queries (sum, min, max) and point updates in O(log n); a Fenwick tree (binary indexed tree) is a simpler structure for prefix sums.

Heaps

• Min-heap / max-heap — complete binary tree where parent ≤ children (min) or parent ≥ children (max); stored compactly in an array: left child at 2i+1, right child at 2i+2; insert O(log n), extract-min/max O(log n), peek O(1), build from array O(n).
• Heap applications — priority queues, heap sort, Dijkstra’s algorithm, scheduling.

Hash Tables

• Hash table — key-value store; hash function maps keys to bucket indices; average O(1) insert, delete, search; worst case O(n) with collisions.
• Collision resolution — separate chaining (each bucket is a linked list); open addressing (linear probing, quadratic probing, double hashing); load factor λ = n/m; rehashing triggered at high load.
• Hash function properties — deterministic, uniform distribution, fast to compute; cryptographic hashes additionally require preimage resistance and collision resistance.

Graphs

• Representations — adjacency matrix: O(V²) space, O(1) edge lookup; adjacency list: O(V + E) space, standard for sparse graphs.
• Directed (digraph) vs undirected — edges have direction or not; in-degree / out-degree vs degree.
• Weighted vs unweighted — weighted edges carry a numeric cost; used in shortest-path and MST algorithms.
• DAG (directed acyclic graph) — no cycles; enables topological sort; used in dependency resolution, build systems.

Other Key Structures

• Disjoint-set / union-find — data structure tracking a partition of elements into disjoint sets; supports find (which set does x belong to?) and union (merge two sets); with path compression and union by rank, both operations are nearly O(1) amortized (inverse Ackermann time); critical for Kruskal’s MST algorithm.
• Skip list — probabilistic data structure; layered linked lists with “express lanes”; supports search, insert, delete in O(log n) expected time; used in Redis sorted sets; invented by William Pugh (1990).
• Bloom filter — probabilistic set-membership structure; uses k hash functions and a bit array; false positives possible, false negatives impossible; space-efficient; used in databases, caches, and CDNs to avoid expensive lookups.
• Fenwick tree (binary indexed tree) — compact array-based structure for prefix-sum queries and point updates, both O(log n); simpler implementation than a segment tree for sum queries.

Structure	Access	Search	Insert	Delete	Space
Array	O(1)	O(n)	O(n)	O(n)	O(n)
Linked list	O(n)	O(n)	O(1)	O(1)*	O(n)
Hash table (avg)	—	O(1)	O(1)	O(1)	O(n)
BST (balanced)	O(log n)	O(log n)	O(log n)	O(log n)	O(n)
Min/Max heap	O(n)	O(n)	O(log n)	O(log n)	O(n)

*O(1) deletion given a pointer to the node.

• Circular buffer (ring buffer) — fixed-size array treated as circular; head and tail pointers advance with wrap-around; O(1) enqueue and dequeue; used in I/O buffering, producer-consumer pipelines.
• Adjacency matrix — V×V matrix; entry [i][j] = 1 (or weight) if edge i→j exists; O(V²) space; O(1) edge lookup; preferred for dense graphs.
• Adjacency list — array of lists, one per vertex; O(V + E) space; the standard representation for sparse graphs; used by BFS, DFS, Dijkstra.
• Sparse matrix — matrix with mostly zero entries; compressed representations (CSR, COO) store only non-zero values; key in scientific computing, graph algorithms, and neural-network layers.
• LRU cache — Least Recently Used eviction policy; implemented with a doubly linked list + hash map achieving O(1) get and put; frequent interview problem; used in OS page replacement and CPU caches.

Sorting and Searching

Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable?
Bubble sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Selection sort	O(n²)	O(n²)	O(n²)	O(1)	No
Insertion sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No
Heap sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No
Counting sort	O(n+k)	O(n+k)	O(n+k)	O(k)	Yes
Radix sort	O(nk)	O(nk)	O(nk)	O(n+k)	Yes

• Comparison-sort lower bound — any comparison-based sorting algorithm requires Ω(n log n) comparisons in the worst case; information-theoretic argument: n! possible orderings require at least log₂(n!) ≈ n log n comparisons to distinguish; applies to mergesort, heapsort, quicksort; non-comparison sorts (radix, counting) bypass this by exploiting integer structure.
• Stable sort — equal elements maintain their original relative order; merge sort and insertion sort are stable; quicksort and heap sort typically are not.
• Quicksort pivot strategies — first element (bad on sorted input), random pivot, median-of-three; introsort (used in C++ STL) switches to heap sort to avoid worst case.
• Lower bound — comparison-based sorting cannot beat O(n log n) in the worst case (information-theoretic argument: ⌈log₂(n!)⌉ comparisons required to distinguish all n! orderings, by Stirling’s approximation Θ(n log n)); non-comparison sorts (counting, radix) bypass this with integer keys.
• Quicksort — divide-and-conquer; choose a pivot, partition into smaller/larger, recurse; average O(n log n), worst O(n²) on sorted input with bad pivot choice; in-place (O(log n) stack); Hoare’s original partition (1959); introsort (C++ STL) switches to heapsort after recursion depth exceeds 2 log n.
• Merge sort — guaranteed O(n log n) all cases; stable; O(n) auxiliary space; recursive split-and-merge; preferred for linked lists; John von Neumann credited (1945); basis of Timsort (Python/Java default), which exploits natural runs in data.
• Heapsort — in-place O(n log n) sort; build a max-heap in O(n), then repeatedly extract maximum; not stable; constant O(1) space advantage over merge sort; poor cache performance compared to quicksort.
• Counting sort — integer keys only; create a frequency array of size k; O(n + k) time and space; stable; efficient when k = O(n).
• Radix sort — sort by individual digits/characters from least significant to most significant (LSD) or reverse (MSD); O(nk) where k is number of digits; uses counting sort as subroutine; stable.

Searching

• Linear search — O(n); works on unsorted data.
• Binary search — O(log n); requires sorted array; halves the search space each step; classic source of off-by-one errors (use mid = lo + (hi - lo) / 2 to avoid overflow).
• Interpolation search — O(log log n) average for uniformly distributed sorted data; O(n) worst case.

String Algorithms

• Knuth-Morris-Pratt (KMP) — string search in O(n + m) time (n = text length, m = pattern length); precomputes a failure function (partial match table) encoding the longest proper prefix that is also a suffix; avoids re-examining text characters; Donald Knuth, James Morris, Vaughan Pratt (1977).
• Rabin-Karp algorithm — string search using rolling hashes; O(n + m) expected, O(nm) worst case (hash collisions); particularly useful for multi-pattern search (detecting plagiarism); Michael Rabin and Richard Karp (1987).
• Boyer-Moore algorithm — right-to-left pattern comparison with bad-character and good-suffix heuristics; O(n/m) best case (sublinear); common in practical text editors and grep.
• Z-algorithm — linear O(n + m) string matching; builds Z-array where Z[i] = length of longest substring starting at position i that is also a prefix of the string; alternative to KMP.

Algorithms

Recursion and Divide-and-Conquer

• Recursion — a function that calls itself on a smaller subproblem; requires a base case; each call uses stack frame space, so O(n) space for depth n.
• Tail recursion — recursive call is the last operation; some languages/compilers optimize to iteration (tail-call optimization); Python does NOT.
• Divide-and-conquer — split into subproblems, solve recursively, combine; merge sort, quicksort, binary search, Strassen’s matrix multiplication follow this pattern.
• Master theorem — gives O-notation for recurrences of the form T(n) = aT(n/b) + f(n).

Dynamic Programming

• Dynamic programming (DP) — solve overlapping subproblems once, store results; two approaches: top-down (memoization) with recursion + cache; bottom-up (tabulation) fills a table iteratively.
• Optimal substructure — optimal solution to the whole contains optimal solutions to subproblems; required for DP.
• Classic DP problems — Fibonacci, 0/1 knapsack, longest common subsequence (LCS), longest increasing subsequence (LIS), edit distance (Levenshtein), matrix chain multiplication, coin change.
• Memoization — top-down DP; cache results of recursive calls so each subproblem is solved at most once; straightforward to implement from a recursive solution; may have call-stack overhead vs tabulation.
• Edit distance (Levenshtein) — minimum number of single-character insertions, deletions, substitutions to transform one string to another; O(nm) DP; used in spell-check, bioinformatics sequence alignment.
• Longest common subsequence (LCS) — O(nm) DP classic; not the same as longest common substring (contiguous); DNA sequence comparison, diff utilities.
• Euclidean algorithm — finds GCD of two integers by repeated remainder; GCD(a, b) = GCD(b, a mod b); terminates in O(log min(a,b)) steps; one of the oldest known algorithms (Euclid’s Elements, ~300 BCE); extended Euclidean algorithm finds Bezout coefficients.

  Greedy Algorithms

• Greedy — make the locally optimal choice at each step; does not always yield global optimum but works for some problems; requires proof of greedy choice and optimal substructure.
• Greedy examples — activity selection, Huffman coding, Kruskal’s and Prim’s MST, Dijkstra’s shortest path (non-negative weights only).

Graph Algorithms

• Huffman coding — greedy algorithm for optimal prefix-free compression; builds a binary tree by repeatedly merging the two lowest-frequency symbols; produces variable-length codes where frequent symbols get shorter codes; O(n log n); used in JPEG, MP3, ZIP; David Huffman (1952).

• Activity selection / interval scheduling — greedy: always pick the activity that finishes earliest; proves that greedy is optimal for maximizing non-overlapping intervals; classic proof of greedy correctness.

• BFS (Breadth-First Search) — explores level by level using a queue; O(V + E); finds shortest paths in unweighted graphs; detects bipartiteness.
• DFS (Depth-First Search) — explores as deep as possible using a stack (or recursion); O(V + E); used for cycle detection, topological sort, strongly connected components.
• Dijkstra’s algorithm — single-source shortest paths in non-negative weighted graphs; uses a min-heap; O((V + E) log V) with binary heap; fails with negative edge weights.
• Kruskal’s algorithm — minimum spanning tree (MST); sort edges by weight; add edge if it doesn’t create a cycle (union-find); O(E log E).
• Prim’s algorithm — MST starting from a node; greedy; O((V + E) log V) with binary heap.
• Topological sort — linear ordering of vertices in a DAG such that all edges go forward; Kahn’s algorithm (BFS-based) or DFS-based (reverse finish order).
• Strongly Connected Components (SCC) — Tarjan’s algorithm (O(V + E)) and Kosaraju’s algorithm find SCCs in directed graphs.
• A* search — BFS/Dijkstra variant using a heuristic h(n) to guide search; optimal when h is admissible (never overestimates); used in pathfinding/game AI.
• Fast Fourier Transform (FFT) — computes the Discrete Fourier Transform in O(n log n) instead of O(n²); Cooley-Tukey algorithm (1965); key to polynomial multiplication, signal processing, image compression (JPEG); used to multiply large integers.
• Bellman-Ford — single-source shortest paths tolerating negative edge weights; relaxes all edges V-1 times; O(VE); can detect negative cycles (a V-th relaxation pass changes a distance); slower than Dijkstra but more general.
• Floyd-Warshall — all-pairs shortest paths via O(V³) DP; d[i][j][k] = shortest path from i to j using only vertices 1..k as intermediates; handles negative weights but not negative cycles; produces a distance matrix.
• Two-pointer / sliding window — linear-time techniques for array/string problems; two pointers move toward each other or both move right; avoids nested loops; examples: sorted pair sums, subarray problems.
• Bit manipulation — exploiting binary representations; XOR tricks (find single number, swap without temp), AND/OR masking, left/right shifts; bitmask DP for subset enumeration; O(1) operations.
• Network flow (max-flow / min-cut) — find maximum flow through a directed capacity graph; Ford-Fulkerson method (augmenting paths); Edmonds-Karp uses BFS for O(VE²); max-flow min-cut theorem: maximum flow equals minimum cut capacity.

Complexity Theory

Big-O Notation

• Big-O O(f) — upper bound on growth rate; O(g) means the function grows no faster than g asymptotically; constant factors dropped.
• Big-Omega Ω(f) — lower bound; Big-Theta Θ(f) — tight bound (both upper and lower).
• Common complexities — O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!).
• Amortized analysis — averages cost over a sequence of operations; dynamic array append is O(1) amortized despite occasional O(n) copies.
• Space complexity — memory used as a function of input size; important alongside time complexity; O(1) in-place (heapsort), O(log n) stack (quicksort), O(n) auxiliary (mergesort).
• NP-hardness reduction technique — to prove problem X is NP-hard, reduce a known NP-hard problem (often 3-SAT) to X in polynomial time; if you can solve X, you can solve 3-SAT; the direction of reduction matters.
• Approximation algorithms — polynomial-time algorithms for NP-hard optimization problems guaranteed to return a solution within a factor of optimal; e.g., 2-approximation for vertex cover; greedy (1 - 1/e)-approximation for set cover; PTAS = polynomial-time approximation scheme.
• Randomized algorithms — use random choices; Las Vegas algorithms always correct (expected fast, e.g., randomized quicksort); Monte Carlo algorithms always fast (may be wrong with small probability, e.g., Miller-Rabin primality test).

Complexity Classes

• P — decision problems solvable in polynomial time by a deterministic Turing machine; considered “tractable.”
• NP (Nondeterministic Polynomial time) — decision problems whose solutions can be verified in polynomial time; every problem in P is in NP.
• NP-complete — hardest problems in NP; a problem is NP-complete if (1) it is in NP and (2) every NP problem reduces to it in polynomial time; if any NP-complete problem is in P, then P = NP.
• NP-hard — at least as hard as the hardest NP problems; need not be in NP (may not be decidable); optimization versions of NP-complete problems are NP-hard.
• Classic NP-complete problems — Boolean satisfiability (SAT, Cook’s theorem 1971), 3-SAT, vertex cover, clique, independent set, subset sum, 0/1 knapsack, Hamiltonian cycle, graph coloring (k ≥ 3), traveling salesman (decision form).
• P vs NP — whether P = NP is the most famous open problem in computer science; a $1 million Millennium Prize Problem; most researchers believe P ≠ NP.
• PSPACE — problems solvable in polynomial space; PSPACE ⊇ NP; PSPACE-complete problems include TQBF.
• co-NP — complement class of NP; problems where “no” instances can be verified in polynomial time; graph non-isomorphism is in co-NP.
• EXP / EXPTIME — problems solvable in exponential time 2^{poly(n)}; strictly contains PSPACE by the time-hierarchy theorem; chess on an n×n board is EXPTIME-complete.
• #P (sharp-P) — counting complexity class; asks how many solutions exist (not just whether one exists); #P-hard problems include counting satisfying assignments to a 3-CNF formula; proved by Valiant (1979).
• Time-hierarchy theorem — more time strictly enlarges the class of solvable problems; proves P ≠ EXPTIME and similar separations; does NOT prove P ≠ NP.
• Oracle / relativization — a technique attaching a black-box oracle subroutine to a TM; Baker-Gill-Solovay (1975) showed there exist oracles A and B with P^A = NP^A and P^B ≠ NP^B; this means P vs NP cannot be resolved by relativizing proof techniques alone.
• Cook-Levin theorem — SAT (Boolean satisfiability) is NP-complete; proven independently by Stephen Cook (1971) and Leonid Levin; the first problem shown to be NP-complete; established the foundation for NP-completeness theory.
• SAT and 3-SAT — SAT asks whether a Boolean formula has a satisfying assignment; 3-SAT restricts to CNF clauses of exactly 3 literals; 3-SAT is NP-complete and serves as the standard starting point for NP-hardness reductions; 2-SAT is in P (solvable via SCCs).
• Polynomial-time reduction — transformation from problem A to problem B computable in polynomial time; if A reduces to B and B is in P, then A is in P; if A is NP-hard and reduces to B, then B is NP-hard; the mechanism of NP-completeness proofs.
• Space complexity classes — L (logspace, deterministic) and NL (nondeterministic logspace) sit below P; PSPACE contains NP and co-NP; EXPTIME contains PSPACE; hierarchy: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXPTIME.

Computability and Automata

• Turing machine — abstract model of computation: infinite tape, read/write head, state transitions; defines what is computable.
• Church-Turing thesis — any function computable by an algorithm can be computed by a Turing machine; a thesis, not a theorem.
• Halting problem — given a program and input, does it halt? Proven undecidable by Alan Turing (1936) via diagonalization; no algorithm can solve it for all inputs.
• Rice’s theorem — all non-trivial semantic properties of programs are undecidable; generalizes the halting problem.
• Decidable vs recognizable — a decidable language has a TM that always halts; a recognizable (recursively enumerable) language has a TM that halts on “yes” instances but may loop on “no.”
• Finite automaton (DFA/NFA) — models recognizing regular languages; DFA and NFA accept the same class (regular languages); both weaker than pushdown automata.
• Context-free grammar (CFG) — generates context-free languages (e.g., balanced parentheses); recognized by pushdown automata; relevant to parsing programming languages.
• Chomsky hierarchy — regular < context-free < context-sensitive < recursively enumerable; each class strictly contains the previous; Noam Chomsky formalized this (1956).
• Pushdown automaton (PDA) — finite automaton augmented with a stack; recognizes context-free languages; nondeterministic PDAs = deterministic PDAs in power (unlike finite automata).

• Regular expressions — formal notation for regular languages; operators: concatenation, union (

  ), Kleene star (*); every regex corresponds to an NFA by Thompson’s construction; used in text processing, compilers (lexical analysis).

• Pumping lemma — necessary condition for a language to be regular (or context-free); used to prove languages are NOT regular; for regular: if

  w

  ≥ pumping length p, then w can be split so that the middle part can be pumped (repeated) and stay in the language.

• Lambda calculus — formal system for expressing computation via function abstraction (λx.body) and application; Alonzo Church (1930s); equivalent in power to Turing machines (Church-Turing thesis); theoretical basis of functional programming; beta reduction is the computation rule.
• NFA (Nondeterministic Finite Automaton) — finite automaton that can be in multiple states simultaneously (or take epsilon transitions); accepts if any branch accepts; equivalent in expressive power to DFA; exponential blowup possible in determinization (subset construction).
• Undecidability examples — halting problem; Post correspondence problem; whether a CFG generates all strings; whether two CFGs are equivalent; whether a program has a bug (Rice’s theorem); all proven by reduction from the halting problem.
• Post correspondence problem (PCP) — undecidable problem: given tiles with two strings, does some sequence make both sides equal? Standard target for undecidability reductions; Emil Post (1946).
• Universal Turing machine — a TM that simulates any other TM given its description as input; the theoretical basis for stored-program computers; proves that a single machine can compute anything computable.
• Diagonalization — proof technique used by Turing (halting problem) and Cantor (uncountability of reals); construct an object that differs from every element of an enumerated list at the diagonal position; key tool in computability and complexity.
• Entscheidungsproblem — Hilbert’s “decision problem” asking for an algorithm to determine the truth of any mathematical statement; proven unsolvable by Church and Turing (1936), giving birth to computability theory.
• Context-sensitive language — Chomsky hierarchy level 2; recognized by linear bounded automata; more expressive than context-free; example: {aⁿbⁿcⁿ}.
• Kleene star — closure operation in formal language theory: L* = all finite concatenations of strings from L, including the empty string ε; fundamental in regular expressions and automata theory; Stephen Kleene (1956).

Programming Paradigms and Languages

• Imperative — step-by-step instructions changing program state; C, Pascal.
• Object-oriented (OOP) — organizes code around objects with encapsulation, inheritance, polymorphism; key languages: Java, C++, Python, C#.
• Functional — treats computation as evaluation of mathematical functions; avoids mutable state; first-class and higher-order functions; Haskell (purely functional), Lisp, Erlang, Clojure; functional features in Python, Scala, Kotlin.
• Declarative — describes what to compute, not how; SQL is the canonical example; Prolog (logic programming).
• Interpreted vs compiled — compiled languages (C, C++) translate to machine code ahead of time; interpreted languages (Python, Ruby) run via a runtime interpreter; JVM languages (Java, Kotlin) compile to bytecode, then JIT-compile.
• Static vs dynamic typing — static: types checked at compile time (Java, C, Rust); dynamic: types checked at runtime (Python, JavaScript, Ruby).
• Strong vs weak typing — strong typing prevents implicit type coercion (Python, Java); weak typing allows it (C, JavaScript).
• Garbage collection — automatic memory management; used in Java, Python, Go; GC algorithms: mark-and-sweep, reference counting, generational GC; contrasts with manual memory management (C/C++) and ownership systems (Rust).
• Pointer / reference — a variable holding a memory address; direct memory manipulation in C/C++; a source of bugs (null pointer, dangling pointer, buffer overflow).
• Pass by value vs pass by reference — pass by value copies the argument; pass by reference passes the memory address, allowing mutation.
• Lambda calculus in PL — anonymous functions (lambdas/closures) in modern languages derive from Church’s lambda calculus; closures capture their lexical environment; key to functional programming in Python, JavaScript, Haskell, Scala.
• Type systems — static typing: types checked at compile time, catches errors early (Java, C, Rust, Haskell); dynamic typing: types checked at runtime (Python, JavaScript, Ruby); gradual typing: optional type annotations (TypeScript, mypy for Python).
• Compiler pipeline — lexical analysis (tokenizing) → parsing (AST construction) → semantic analysis (type checking) → optimization → code generation; LLVM is a widely-used compiler infrastructure.
• Interpreter vs compiler — interpreters execute source directly (Python CPython, early BASIC); compilers translate to machine code or bytecode ahead of time; JIT (just-in-time) compilation compiles at runtime (JVM HotSpot, V8 JavaScript engine, PyPy).
• Garbage collection algorithms — mark-and-sweep: trace reachable objects, collect the rest; reference counting: count references, free at zero (problem: cycles; Python uses cycle detector); generational GC: most objects die young, promote long-lived objects to older generations (JVM, CPython).
• Call stack and stack frame — each function call pushes a frame containing local variables, parameters, and return address; stack grows downward on x86; stack overflow occurs when recursion is too deep; heap is used for dynamically allocated objects.
• Recursion vs iteration — recursion is cleaner for tree/graph traversal but uses O(depth) stack space; iterative solutions use explicit stacks; tail-call optimization (TCO) converts tail recursion to iteration; Scheme mandates TCO, Python explicitly does not.
• First-class functions and higher-order functions — in functional languages, functions are values that can be passed to/returned from other functions; map, filter, reduce (fold) are canonical higher-order functions.
• Logic programming — programs are logical clauses; computation is inference; Prolog is the canonical language; uses unification and backtracking search; applied in AI, natural language processing, constraint solving.
• Closure — a function that captures variables from its enclosing lexical scope; allows functions to be returned as values while retaining access to outer-scope bindings; central to functional programming and JavaScript.
• Currying — transforming a function of multiple arguments into a chain of single-argument functions; f(x, y) becomes f(x)(y); named after Haskell Curry; fundamental in Haskell and functional languages.
• Monad — design pattern in functional programming (especially Haskell) for chaining computations with context (e.g., handling failure, I/O, state) while maintaining purity; a monad must satisfy left-identity, right-identity, and associativity laws.
• Type inference — compiler/interpreter deduces types without explicit annotations; Hindley-Milner algorithm (ML, Haskell); distinct from dynamic typing, which checks types at runtime.
• Abstract syntax tree (AST) — tree representation of the syntactic structure of source code produced during parsing; nodes represent constructs (expressions, statements); used in compilers, linters, and code analysis tools.
• Memory management: stack vs heap — stack holds local variables and call frames (fast, automatic, fixed size per frame); heap holds dynamically allocated objects (flexible size, managed by GC or manual free); stack overflow from deep recursion; heap fragmentation from dynamic allocation.
• Ownership and borrowing (Rust) — Rust’s memory safety model: each value has exactly one owner; references (borrows) must not outlive the owner; prevents dangling pointers and data races without garbage collection; enforced at compile time by the borrow checker.
• Event loop — JavaScript’s concurrency model; single-threaded; I/O callbacks queued in the event loop while the call stack is empty; Node.js uses libuv for async I/O; microtask queue (Promises) drains before macrotasks (setTimeout).
• Concurrency vs parallelism — concurrency: multiple tasks make progress by interleaving (single core); parallelism: tasks execute simultaneously on multiple cores; Go’s goroutines are concurrent; SIMD/GPU kernels are parallel.
• Amdahl’s law — speedup from parallelizing a program is limited by the serial fraction s: Speedup ≤ 1/(s + (1-s)/p) where p is processor count; diminishing returns; Gene Amdahl (1967).

Key Languages (Brief)

• C — low-level, compiled, manual memory; basis for UNIX and most operating system kernels; Dennis Ritchie (Bell Labs, early 1970s).
• C++ — extends C with OOP and templates; Bjarne Stroustrup (1979).
• Java — “write once, run anywhere” via JVM bytecode; strong static typing, garbage collected; James Gosling (Sun, 1995).
• Python — dynamic, interpreted, emphasis on readability; Guido van Rossum (1991); dominant in data science, scripting, and ML.
• JavaScript — prototype-based, event-driven; the language of web browsers; Brendan Eich (Netscape, 10 days, 1995); Node.js brings it server-side.
• Rust — memory-safe without garbage collection via ownership/borrow checker; Mozilla Research (Graydon Hoare), 1.0 in 2015.
• Lisp — one of the oldest high-level languages (John McCarthy, 1958); homoiconicity (code is data); dialects include Common Lisp, Scheme, Clojure.

Software Engineering

Software engineering applies systematic methods to building, operating, and changing software under constraints of cost, schedule, quality, safety, and security. The IEEE Computer Society’s SWEBOK Guide V4.0 (2024) spans requirements, architecture, design, construction, testing, operations, maintenance, configuration management, management, process, models and methods, quality, security, professional practice, and economics.¹

• Origins of the discipline — the NATO Software Engineering Conference at Garmisch, Germany, in October 1968 promoted engineering discipline for software development. Participants described chronically late, over-budget, and unreliable projects as a “software crisis.”²
• Requirements and abstraction — requirements specify what a system must do and its constraints; interfaces state what a component provides while hiding implementation details. Modularity helps changes remain local. Version control records changes so collaborators can review and recover earlier versions.³
• Quality attributes — functional requirements state behavior, while quality attributes such as performance, security, reliability, usability, and maintainability constrain how well that behavior must be delivered. Because requirements are often incomplete, conflicting, or changing, elicitation, validation, prioritization, and traceability continue throughout development.
• Life-cycle models — plan-driven models sequence requirements, design, implementation, verification, and maintenance, whereas iterative and incremental models deliver working increments and revise them with feedback. Winston Royce’s 1970 paper, commonly cited as the source of the “waterfall,” called a single linear pass risky and recommended feedback and repeated work; the spiral model organizes iterations around risk.⁴
• Agile methods and DevOps — the Manifesto for Agile Software Development, written at Snowbird, Utah, in February 2001, values individuals and interactions, working software, customer collaboration, and responding to change over processes and tools, comprehensive documentation, contract negotiation, and following a plan, while affirming that the latter still have value. Scrum and Extreme Programming are common agile approaches; DevOps extends short feedback loops into deployment and operations through automation, continuous integration and delivery, and monitoring.⁵
• Architecture and modular design — software architecture defines major components, their responsibilities, interfaces, and deployment. David Parnas’s 1972 Communications of the ACM paper argued that modules should hide design decisions likely to change, the principle of information hiding. Low coupling between modules and high cohesion within them keep changes local; design patterns record reusable solutions to recurring design problems.⁶
• Software testing — unit tests examine individual components, integration tests examine their interactions, and system tests examine complete behavior. Regression tests check that a change preserves required behavior. Passing tests demonstrates the cases checked; it does not prove a program has no defects. Reviews and static analysis can detect problems without executing the program.³
• Verification beyond testing — inspections, static analysis, model checking, and mathematical proof can establish properties for all executions within a model, whereas tests sample particular cases. Formal methods are applied selectively, most often where failures are costly, because precise specifications and proofs require substantial expertise.
• Configuration management and release — version control, dependency management, reproducible builds, and release records identify which source, libraries, and settings produced a deployed system. Without them, defects are hard to reproduce, audit, or roll back.
• Maintenance, evolution, and technical debt — long-lived software changes to correct defects, adapt to new platforms, and add capabilities. Ward Cunningham’s 1992 technical-debt metaphor compares expedient code to borrowing: it can speed delivery, but unrepaid shortcuts make later change more expensive. Refactoring improves internal structure without changing external behavior.⁷
• Estimation and team scale — Fred Brooks’s The Mythical Man-Month (1975) argued from IBM OS/360 experience that adding people to a late project can make it later, because newcomers need time to become productive and communication overhead grows. His 1986 essay “No Silver Bullet” argued that no single technology or management technique promised an order-of-magnitude improvement within a decade, because much of software’s complexity is essential rather than accidental.⁸
• Failure analysis — software failures often involve specifications, assumptions, reuse, and review practices as well as code. Ariane 5’s first flight on 4 June 1996 was lost when its inertial reference software, essentially the Ariane 4 design, raised an unhandled exception in an alignment function that served no purpose after lift-off: a 64-bit floating-point value related to horizontal velocity was too large to convert into a 16-bit signed integer. The inquiry board found that the specifications and equipment tests had not included Ariane 5 trajectory data.⁹
• Professional ethics — the Software Engineering Code of Ethics and Professional Practice, approved by the IEEE Computer Society and ACM in 1999, organizes obligations under eight principles: public, client and employer, product, judgment, management, profession, colleagues, and self. Security, privacy, accessibility, and safety requirements affect people well beyond a development team.¹⁰
• Evidence and open questions — the effectiveness of practices such as pair programming, test-driven development, or a particular process model depends on team, domain, and context, so evidence from one setting transfers imperfectly. AI-assisted code generation raises unresolved questions about verification, security, licensing, maintainability, and accountability.

Computer Graphics

• Computer graphics — methods for representing geometry, materials, lighting, and cameras to construct images. A scene description is converted into an image through rendering. The Cornell box provides a standard scene for comparing calculated light transport with measured photographs.¹¹
• Rasterization and ray tracing — rasterization projects geometric primitives, often triangles, onto an image and determines which samples they cover. Ray tracing finds intersections between rays and scene geometry; secondary rays can test shadows or follow reflections. Both approaches still need shading rules to determine the resulting colors.¹¹
• Phong reflection and shading — the Phong reflection model combines ambient, diffuse, and specular contributions; the specular exponent controls highlight concentration. Phong shading interpolates surface normals across a polygon and evaluates lighting at image samples. The reflection model and interpolation method are distinct, although they share Bui Tuong Phong’s name.¹¹

Computer Architecture

Computer architecture studies the interface between hardware and software and the organization of processors, memory, and input/output to meet goals for performance, energy, cost, reliability, and security. Historical machines appear in Computing History; operating-system memory management appears under Operating Systems.¹²

• Instruction execution — a processor fetches an instruction from memory, decodes it, and carries out the specified operation. Registers hold working values; the program counter identifies an instruction address. An instruction set defines the machine-level operations visible to software; different processor implementations can execute the same instruction set.¹³
• Pipelining and parallelism — a pipeline overlaps stages of different instructions, improving throughput without necessarily reducing the latency of one instruction. Data dependencies and branches can interrupt that overlap. Multiple cores can run work concurrently, but synchronization and the serial part of a task limit speedup.¹³
• Abstraction layers — an instruction set architecture (ISA) is the contract visible to compilers and operating systems; a microarchitecture is one hardware implementation of that contract, built from digital logic. IBM announced System/360 on 7 April 1964 as a family of machines sharing one ISA across different price and performance levels, separating software compatibility from hardware implementation.¹⁴
• Stored-program and Harvard organization — in a stored-program organization, instructions and data share memory and the processor fetches instructions by address; a Harvard organization separates instruction and data memories, a distinction still visible in some microcontrollers and in separate instruction and data caches. Attribution of the stored-program idea is discussed in Computing History.¹²
• Data representation — hardware stores information as bit patterns whose meaning depends on interpretation. Two’s-complement encoding lets one adder handle signed and unsigned addition; fixed-width integers can overflow; floating-point formats such as IEEE 754 trade exact representation for range, so a value like 0.1 is only approximated in binary.¹²
• Processor performance equation — the time a program takes equals its instruction count times the average clock cycles per instruction times the clock period. Architecture, compiler, and program all affect these terms, so clock rate or core count alone does not predict performance; benchmarks compare systems on stated workloads.
• RISC and CISC — reduced instruction set computers use simple, regular instructions suited to pipelining and optimizing compilers, while complex instruction set designs such as x86 offer richer instructions. Berkeley’s RISC-I and Stanford’s MIPS processors of 1982 and 1983 demonstrated the RISC approach; later x86 processors translate complex instructions into simpler internal operations, so the modern contrast concerns instruction-set design more than internal execution.¹⁴
• Memory hierarchy and locality — programs tend to reuse recently accessed data (temporal locality) and nearby data (spatial locality), so small fast caches in front of larger, slower memory can deliver much of the speed of fast memory at lower cost. Cache misses and data movement can dominate time and energy use; paging and virtual memory appear under Operating Systems.¹²
• Speculation and side channels — processors predict branches and execute instructions ahead of certainty, discarding wrong-path work. Speculation raises performance but wastes work on mispredictions, and the Meltdown and Spectre attacks disclosed in 2018 showed that speculative and out-of-order execution can leak protected data through side channels.¹⁵
• Input/output and interrupts — devices are controlled through registers, interrupts signal events without constant polling, and direct memory access lets devices move data without the processor copying every byte. These mechanisms link architecture to operating-system design.¹²
• Flynn’s taxonomy — Michael Flynn’s 1966 classification distinguishes single and multiple instruction and data streams: SISD, SIMD, MISD, and MIMD. Vector instructions and graphics processors exploit data parallelism, while multicore processors and clusters are MIMD systems; Amdahl’s law, under Programming Paradigms and Languages, limits speedup when part of a workload remains serial.¹⁶
• End of Dennard scaling — Dennard scaling described how shrinking transistors could hold power density roughly constant; Hennessy and Patterson describe it slowing significantly from 2007, as transistor-density growth also fell behind Moore’s projections. Because power must leave a chip as heat, designers shifted from faster single cores toward multicore processors and specialization.¹⁴
• Domain-specific architectures — accelerators such as graphics processors, neural-network processors like Google’s Tensor Processing Unit, and network processors gain performance and energy efficiency by tailoring memory use, numeric precision, and parallelism to one class of workloads. They depend on domain-specific languages and compilers and trade generality for efficiency.¹⁴
• Open instruction sets, security, and sustainability — RISC-V, begun at UC Berkeley in 2010, is an open, royalty-free ISA that anyone can implement without licensing a proprietary instruction set. Current curricula also treat hardware support for isolation and memory protection, heterogeneous and quantum architectures, and the energy and environmental costs of computing as part of architecture.¹⁷¹²

Operating Systems

• Process vs thread — a process is an independent execution environment with its own memory space; threads share memory within a process; lighter-weight context switching for threads.
• Scheduling — OS decides which process/thread runs on the CPU; algorithms: FCFS (first-come-first-served), SJF (shortest job first), round-robin (time slices), priority scheduling.
• Context switch — saving and restoring CPU state when switching between processes/threads; overhead degrades performance at high frequency.
• Virtual memory — abstraction giving each process its own address space; paging maps virtual to physical addresses via a page table; a TLB (translation lookaside buffer) caches recent translations.
• Page fault — a process accesses a page not in physical memory; OS loads it from disk; thrashing occurs when excessive page faults dominate CPU time.
• Deadlock — four necessary conditions (Coffman, 1971): mutual exclusion, hold-and-wait, no preemption, circular wait; prevention requires denying at least one condition; detection via resource-allocation graph; Dining Philosophers problem (Dijkstra) illustrates deadlock and starvation with five philosophers alternating eating/thinking.
• Dining Philosophers problem — five philosophers sit at a round table; each needs two forks to eat; naive solution deadlocks when all pick up left fork simultaneously; solutions include resource ordering, Chandy/Misra approach, or an arbitrator; classic concurrency textbook problem.
• Memory hierarchy and cache — registers → L1 cache → L2 cache → L3 cache → RAM → SSD/HDD; each level trades speed for size; cache hit serves data from fast cache; cache miss fetches from slower memory; cache coherence is the challenge in multi-core systems.
• Cache replacement policies — LRU (Least Recently Used): evict the item unused longest; LFU (Least Frequently Used); FIFO; LRU implemented efficiently with a doubly linked list + hash map.
• CPU scheduling — FCFS: simple, convoy effect; SJF (Shortest Job First): optimal average wait time, requires knowing burst times; Round Robin: time slices (quantum), good for interactive systems; Priority scheduling: can cause starvation (solved by aging).
• Thrashing — when a process spends more time swapping pages than executing; occurs when working set does not fit in RAM; addressed by working-set model or page-fault frequency control.
• Semaphore — synchronization primitive invented by Edsger Dijkstra; integer counter with atomic P (wait/down) and V (signal/up) operations; binary semaphore (0/1) = mutex; counting semaphore controls a pool of N resources; prevents race conditions and coordinates producer-consumer.
• Mutex (mutual exclusion lock) — only one thread holds the lock at a time; prevents race conditions on shared data; a thread that cannot acquire a mutex blocks (sleeps) until the holder releases it; distinct from a spinlock, which busy-waits.
• Race condition — output depends on the non-deterministic interleaving of concurrent operations; prevented by synchronization.
• Spinlock — busy-wait synchronization; thread loops checking a flag rather than sleeping; avoids context-switch overhead for very short critical sections; wastes CPU if the wait is long; common in OS kernel code.
• Condition variable — synchronization primitive used with a mutex; threads wait (sleep) until another thread signals a condition (e.g., pthread_cond_wait/signal); used in monitor-based concurrency; avoids busy-waiting.
• Monitor — high-level synchronization construct combining a mutex and one or more condition variables; ensures mutual exclusion automatically; Java’s synchronized keyword implements monitors; C. A. R. Hoare (1974).
• Livelock — two or more threads keep changing state in response to each other but make no progress; distinct from deadlock (where threads are blocked); example: two people in a hallway each stepping aside in the same direction.
• IPC (inter-process communication) — mechanisms for processes to exchange data: pipes, message queues, shared memory, sockets, semaphores, signals; shared memory is fastest (no kernel copy); pipes are simplest for parent-child processes.
• File system — organizes data on disk; UNIX uses an inode-based structure; ext4, NTFS, HFS+ are common; journaling file systems log changes before committing to prevent corruption.
• System call — interface between user programs and the OS kernel; transitions CPU from user mode to kernel mode; examples: read(), write(), fork(), exec().

Databases

• Relational database — data organized in tables (relations) with rows and columns; SQL is the query language; primary keys uniquely identify rows; foreign keys enforce referential integrity.
• ACID — properties of a reliable transaction: Atomicity (all-or-nothing), Consistency (data integrity invariants preserved), Isolation (concurrent transactions do not interfere), Durability (committed data persists).
• Normalization — process of eliminating redundancy; 1NF (atomic values), 2NF (no partial dependencies), 3NF (no transitive dependencies), BCNF (Boyce-Codd).
• Index — auxiliary data structure (typically B+ tree) speeding up lookups at the cost of write overhead and storage; a clustered index dictates physical row order.
• JOIN types — INNER JOIN (matching rows only), LEFT/RIGHT OUTER JOIN (all rows from one side), FULL OUTER JOIN, CROSS JOIN (Cartesian product).
• Transaction isolation levels — Read Uncommitted, Read Committed, Repeatable Read, Serializable; higher levels prevent more anomalies (dirty reads, non-repeatable reads, phantom reads) at the cost of concurrency.
• CAP theorem — during a network partition, a distributed read/write service cannot guarantee both linearizable consistency and a response to every request received by a non-failing node. Linearizability makes operations behave as if they occurred in one order consistent with real time. A service can preserve that consistency by delaying or refusing some operations, or keep serving requests while accepting weaker consistency. The tradeoff applies during a partition, not as an unrestricted “pick any two” rule.¹⁸
• BASE — alternative to ACID for distributed/NoSQL: Basically Available, Soft state, Eventually consistent.
• NoSQL categories — key-value (Redis), document (MongoDB), column-family (Cassandra, HBase), graph (Neo4j); trade normalization and ACID for horizontal scalability.
• ORM (Object-Relational Mapper) — maps OOP objects to relational tables; examples: Hibernate (Java), SQLAlchemy (Python), ActiveRecord (Ruby).
• View (SQL) — virtual table defined by a SELECT query; stored query, not stored data; simplifies complex queries; materialized view physically stores the result for performance.
• Stored procedure — named, precompiled SQL routine stored in the database; reduces round trips; can accept parameters; common in enterprise databases; debated in modern architectures.
• Query optimization — RDBMS parses SQL into a query plan; the optimizer chooses join order, index use, and execution strategy using cost estimates; EXPLAIN shows the chosen plan.
• Sharding — horizontal partitioning of a database across multiple servers by a shard key (e.g., user ID); scales writes; complicates joins and transactions; used by large-scale web applications.
• Replication — copying data to multiple database replicas; primary-replica model: writes to primary, reads from replicas; improves read throughput and fault tolerance; introduces replication lag.
• Relational model and Codd — Edgar F. Codd (IBM) proposed the relational model in 1970 (“A Relational Model of Data for Large Shared Data Banks”); introduced relations (tables), keys, and relational algebra; Turing Award 1981; prior systems were hierarchical (IMS) or network-based.
• SQL — Structured Query Language; declarative language for relational databases; ANSI standard since 1986; DDL (CREATE, ALTER, DROP), DML (SELECT, INSERT, UPDATE, DELETE), DCL (GRANT, REVOKE); first implemented in IBM System R (1974).
• Two-phase commit (2PC) — distributed transaction protocol ensuring all-or-nothing commit across multiple nodes; Phase 1 (prepare): coordinator asks all participants to vote; Phase 2 (commit/abort): coordinator sends final decision; blocks on coordinator failure.
• Eventual consistency — distributed systems guarantee that if no new updates are made, all replicas will eventually converge; weaker than strong consistency but allows higher availability and partition tolerance; common in NoSQL (Cassandra, DynamoDB).
• CAP theorem proof / Brewer’s theorem — stated by Eric Brewer (2000), proved by Gilbert and Lynch (2002); in the presence of a network partition, a distributed system cannot be both consistent and available; modern systems acknowledge CP vs AP trade-offs.

Cryptography Fundamentals

• Symmetric encryption — the same key encrypts and decrypts; fast; key distribution is a challenge; AES (Advanced Encryption Standard) is the current standard (128/192/256-bit keys).
• Asymmetric (public-key) encryption — mathematically linked key pair: a public key encrypts, a private key decrypts; solves key distribution; examples: RSA (factoring hardness), Elliptic Curve Cryptography (ECC) (discrete log over elliptic curves).
• RSA — Rivest-Shamir-Adleman (1977); security rests on the difficulty of factoring the product of two large primes; key sizes typically 2048–4096 bits.
• Diffie-Hellman key exchange — allows two parties to establish a shared secret over a public channel without transmitting the secret; basis for TLS/SSL key agreement.
• Cryptographic hash function — maps arbitrary input to a fixed-length digest; properties: deterministic, fast to compute, preimage resistant, collision resistant; examples: SHA-256 (256-bit), SHA-3, MD5 (128-bit, broken).
• Digital signature — hash of a message encrypted with the sender’s private key; recipient verifies with public key; ensures authenticity and non-repudiation.
• TLS/SSL — Transport Layer Security; cryptographic protocol securing web (HTTPS) and other traffic; combines asymmetric exchange with symmetric session keys.
• Quantum threat — Shor’s algorithm (polynomial time on a quantum computer) would break RSA and ECC; post-quantum cryptography (lattice-based, etc.) is under active standardization (NIST).
• AES (Advanced Encryption Standard) — symmetric block cipher standardized by NIST (2001); replaced DES; key sizes 128, 192, or 256 bits; block size 128 bits; uses SubBytes, ShiftRows, MixColumns, AddRoundKey rounds; selected from the Rijndael cipher (Joan Daemen and Vincent Rijmen).
• Block cipher modes — AES alone encrypts a single 128-bit block; modes chain blocks: ECB (insecure, patterns visible), CBC (chained XOR), CTR (turns block cipher into stream cipher), GCM (authenticated encryption); CTR/GCM are preferred.
• Message authentication code (MAC) — keyed checksum ensuring integrity and authenticity; HMAC uses a cryptographic hash (e.g., HMAC-SHA256); distinct from a digital signature (which uses asymmetric keys).
• Elliptic curve cryptography (ECC) — public-key cryptography over elliptic curve groups; same security as RSA with much smaller keys (256-bit ECC ≈ 3072-bit RSA); used in TLS, Bitcoin (secp256k1); discrete logarithm problem over elliptic curves is the hard problem.
• Zero-knowledge proof — interactive protocol where a prover convinces a verifier they know a secret without revealing the secret; properties: completeness, soundness, zero-knowledge; modern SNARKs enable non-interactive variants; used in privacy-preserving cryptocurrencies (Zcash).
• Diffie–Hellman and ECDH — classical finite-field Diffie–Hellman uses a suitable subgroup of the nonzero residues modulo a prime; elliptic-curve Diffie–Hellman uses an elliptic-curve group. Computing the shared secret from the public values is the Diffie–Hellman problem; solving the corresponding discrete logarithm problem would solve it. Unauthenticated key exchange alone does not prevent a man-in-the-middle attack.¹⁹
• AES cryptanalysis — distinguish full-round key recovery from reduced-round, related-key, or known-key results. The 2011 biclique paper reported costs of approximately 2¹²⁶·¹, 2¹⁸⁹·⁷, and 2²⁵⁴·⁴ operations for AES-128, AES-192, and AES-256 respectively; these are theoretical shortcuts, not practical decryptions. AES remains specified by NIST; implementation security and correct modes are separate questions.²⁰

Networking Basics

• OSI model — 7-layer reference model: Physical, Data Link, Network, Transport, Session, Presentation, Application; TCP/IP model collapses to 4 layers.
• IP (Internet Protocol) — connectionless, best-effort delivery; IPv4 (32-bit addresses, ~4.3 billion), IPv6 (128-bit, effectively unlimited).
• TCP vs UDP — TCP provides reliable, ordered, connection-oriented delivery (three-way handshake: SYN, SYN-ACK, ACK); UDP is connectionless, unreliable, faster; used for DNS, streaming, gaming.
• DNS — Domain Name System; translates hostnames to IP addresses; hierarchical distributed database.
• HTTP/HTTPS — HyperText Transfer Protocol; stateless, application-layer; HTTPS adds TLS encryption.
• Router vs switch vs hub — hub broadcasts to all ports; switch learns MAC addresses and forwards frames to the correct port (Layer 2); router routes packets between networks using IP addresses (Layer 3).
• Subnet and CIDR — Classless Inter-Domain Routing partitions IP space with prefix notation (e.g., 192.168.1.0/24 = 256 addresses); subnetting divides a network into smaller blocks; NAT allows multiple hosts to share one public IP.
• Port and socket — IP address identifies a host; port (16-bit integer) identifies a process; a socket is a (IP, port) pair; well-known ports: HTTP 80, HTTPS 443, SSH 22, DNS 53, SMTP 25.
• Three-way TCP handshake — SYN (client → server), SYN-ACK (server → client), ACK (client → server); establishes sequence numbers and connection state; four-way FIN handshake tears down the connection.
• CDN (Content Delivery Network) — geographically distributed servers cache and serve static content close to users; reduces latency; examples: Cloudflare, Akamai, AWS CloudFront.
• Load balancer — distributes incoming requests across multiple backend servers; algorithms: round-robin, least connections, IP hash; Layer 4 (transport) vs Layer 7 (application/HTTP) balancers.

Human-Computer Interaction

Human-computer interaction (HCI) studies how people use, experience, and are affected by interactive systems, drawing on computer science, psychology, design, and the social sciences. The history of graphical interfaces is covered in Computing History.²¹

• Usability and accessibility — usability concerns how people complete tasks with a system; accessibility addresses barriers faced by people with disabilities. User research, prototypes, and task-based evaluation reveal problems that technical correctness alone misses. Keyboard operation, meaningful text alternatives, clear labels, and visible focus help people use the same content through different forms of input and perception.²²
• Human-centered design — design proceeds through repeated cycles of understanding users and contexts, specifying needs, creating designs, and evaluating them with people. Designers are not their users, so interviews, surveys, observation, personas, journey maps, and needs assessments help teams test their own assumptions.²¹
• Usability attributes — Jakob Nielsen describes usability through learnability, efficiency, memorability, errors, and satisfaction, and distinguishes it from utility, whether a system provides the functions people need. A useful system needs both.²³
• Perception, cognition, and movement — attention, perception, memory, and recognition shape interaction; interfaces that let people recognize options generally demand less memory than those requiring recall. Fitts’s law, derived from Paul Fitts’s 1954 experiments on aimed movement, predicts that pointing takes longer as target distance increases and target width decreases.²⁴
• Affordances, signifiers, and mental models — the psychologist James J. Gibson coined “affordance” in 1977 for the action possibilities an environment offers. Don Norman adapted the idea for design in The Design of Everyday Things (1988) and later emphasized signifiers, perceivable cues that show which actions are possible. Feedback and consistent structure help users form accurate mental models of system state.²⁵
• Interaction styles — command languages, menus, forms, direct manipulation, windows and pointing, touch and gesture, voice, and virtual or augmented reality distribute effort differently among recall, recognition, precision, and speed. Suitability depends on task, expertise, setting, and ability rather than on one universally superior style.
• Prototyping — sketches and paper prototypes explore concepts cheaply, while interactive high-fidelity prototypes test detailed flows, timing, and visual design. Rough prototypes tend to invite critique of the concept; polished ones can narrow feedback to surface details.
• Heuristic evaluation and walkthroughs — in heuristic evaluation, which Jakob Nielsen developed with Rolf Molich in 1990, evaluators inspect an interface against principles; Nielsen’s ten heuristics, refined in 1994, include visibility of system status, error prevention, and recognition rather than recall. Cognitive walkthroughs step through tasks from a new user’s perspective. Inspection is fast but can miss problems that only representative users reveal.²⁶
• Usability testing and experiments — representative users attempt realistic tasks while researchers observe success, errors, time, and think-aloud comments. Nielsen recommends frequent small iterative tests, often about five users per round, to find major problems; estimating differences between designs requires controlled experiments or A/B tests with adequate samples.²³
• Accessibility standards and assistive technology — the W3C Web Content Accessibility Guidelines (WCAG) 2.2 organize testable success criteria under four principles, perceivable, operable, understandable, and robust, with conformance levels A, AA, and AAA. Screen readers, switch access, captions, magnification, and voice control depend on content that exposes structure and meaning to software; conformance is a baseline, and testing with disabled users can reveal barriers a checklist misses.²⁷
• Inclusive and cross-cultural design — ability, age, language, culture, literacy, and experience shape how people interpret interfaces. Internationalization, universal design, and evaluation with diverse participants reduce the risk that findings from convenient samples fail to generalize.²¹
• Collaboration and social computing — computer-supported cooperative work and social computing study synchronous and asynchronous communication, online communities, social media, and shared tools, where coordination, awareness of others, and community norms matter alongside individual efficiency.²¹
• Values, persuasion, and deceptive design — value-sensitive design identifies direct and indirect stakeholders and the values a system affects. Persuasive design can support goals such as health, but manipulative “dark patterns” disguise advertising, obstruct cancellation, bury key terms, or trick people into sharing data; a September 2022 U.S. Federal Trade Commission staff report documented such practices in e-commerce, cookie banners, children’s apps, and subscriptions.²⁸
• History and current directions — Douglas Engelbart’s 9 December 1968 demonstration of the NLS system showed a mouse, hypertext, windows, and real-time collaboration; later graphical interfaces made such ideas widespread. Mobile, ubiquitous, and AI-based systems extend HCI to automation, explanation, privacy, trust, and appropriate reliance.²⁹

Key Figures and Turing Award Context

• Alan Turing — foundational theorist: Turing machine, computability, halting problem (1936); codebreaking at Bletchley Park; died 1954. The Turing Award is named for him but he never received it.
• John von Neumann — von Neumann architecture (CPU, memory, I/O bus, stored-program concept); also contributed to game theory and quantum mechanics.
• Edsger Dijkstra — shortest-path algorithm (1956), structured programming, semaphores, Dijkstra’s algorithm and the “GOTO statement considered harmful” letter; Turing Award 1972.
• Donald Knuth — The Art of Computer Programming series; developed TeX; Turing Award 1974; coined the term “literate programming.”
• John McCarthy — invented Lisp (1958); coined the term “artificial intelligence”; Turing Award 1971.
• Grace Hopper — pioneered compilers; developed COBOL; coined “debugging” after removing a literal moth from the Mark II computer (1947).
• Dennis Ritchie and Ken Thompson — created UNIX (1969) and the C programming language at Bell Labs; Turing Award 1983.
• Linus Torvalds — created the Linux kernel (1991) and Git (2005).
• Tim Berners-Lee — invented the World Wide Web (1989–1991) at CERN; proposed HTTP, HTML, and URLs.
• Claude Shannon — founder of information theory; A Mathematical Theory of Communication (1948); defined bit and entropy.
• Turing Award — highest honor in computer science, awarded annually by the ACM since 1966; first recipient was Alan Perlis.
• Niklaus Wirth — designed Pascal (1970), Modula-2, Oberon; Turing Award 1984; proposed “Wirth’s law” — software gets slower faster than hardware gets faster; championed structured programming.
• Tony Hoare — invented Quicksort (1959); designed Communicating Sequential Processes (CSP); Turing Award 1980; introduced the null reference and called it his “billion-dollar mistake.”
• Barbara Liskov — Liskov Substitution Principle (LSP): if S is a subtype of T, objects of type T may be replaced by objects of type S without altering program correctness; Turing Award 2008; designed CLU (first language with abstract data types as a linguistic construct).
• Leslie Lamport — distributed systems pioneer; Paxos consensus algorithm; logical clocks (“Time, Clocks, and the Ordering of Events in a Distributed System,” 1978); LaTeX document system; Turing Award 2013.
• John Backus — designed FORTRAN (1957), the first widely used high-level programming language; invented BNF (Backus-Naur Form) notation for grammars; Turing Award 1977; also proposed “function-level programming.”
• Peter Naur — formalized BNF with Backus; co-editor of the ALGOL 60 report; Turing Award 2005; his name appears in “Backus-Naur Form.”
• Marvin Minsky — co-founder of MIT AI Lab; Perceptrons book (with Papert) showed limits of single-layer networks; Turing Award 1969; built the first neural network simulator (SNARC, 1951).
• Tony Hoare: Quicksort and CSP — Hoare’s Quicksort article appeared in The Computer Journal 5(1), 10–16 (1962); the algorithm had already appeared as a short Communications of the ACM algorithm in 1961. His Communicating Sequential Processes article appeared in Communications of the ACM 21(8), 666–677 (1978); distinguish it from the later 1985 book.³⁰
• Paxos / The Part-Time Parliament — Leslie Lamport’s consensus paper was written in 1989, first submitted in 1990, and published in ACM Transactions on Computer Systems 16(2), 133–169 (1998). Its publication history explains the multiple dates; Paxos concerns agreement despite failures, rather than a single universally applicable implementation.³¹